Игорь только что вернулся со школы, где ему задали огромное количество домашней работы. Ему предстоит решить $$$x$$$ примеров по математике и прочитать $$$y$$$ страниц по литературе.
Игорь очень занятой человек и ему важно спланировать свое время. Помогите Игорю и подсчитайте сколько времени у него уйдет на выполнение домашней работы, если на решение одного примера у Игоря уходит $$$t_1$$$ минут, а на прочтение одной страницы — $$$t_2$$$ минут.
Единственная строка входных данных содержит четыре числа $$$x$$$, $$$y$$$, $$$t_1$$$, $$$t_2$$$ ($$$1 \le x, y, t_1, t_2 \le 100$$$).
Выведите единственное число — количество минут, которое уйдет у Игоря на выполнение домашней работы.
4 5 10 3
55
3 1 100 27
327
В первом примере Игорь потратит $$$55$$$ минут на выполнение домашней работы: $$$40$$$ минут на решение примеров и $$$15$$$ минут на чтение.
Во втором примере Игорь потратит $$$327$$$ минут на выполнение домашней работы: $$$300$$$ минут на решение примеров и $$$27$$$ минут на чтение.
Настя купила себе новую книгу «Как стать программистом за 7 минут». Она хотела прочитать эту книгу вечером, но случилась беда. Её младший брат изрисовал всю книгу каракулями.
К счастью, брат Насти рисовал только в свободных местах и все его каракули выглядят как звездочки. Другими словами, брат Насти нарисовал на месте каждого пробела один или несколько символов '*'. Также, Насте известно, что текст книги не содержал двух пробелов подряд. Помогите Насте восстановить исходный текст книги.
В первой строке входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — длина строки $$$s$$$.
Во второй строке входных данных находится строка $$$s$$$, которая содержит в себе исходный текст книги и каракули, которые нарисовал брат. Строка состоит из заглавных и строчных букв латинского алфавита, точек, запятых и звездочек ($$$s_i \in \{$$$'a'-'z', 'A'-'Z', ',', '.', '*'$$$\}, 1 \le i \le n$$$). Гарантируется, что первый и последний символ строки не являются звездочками ($$$s_1 \ne$$$ '*', $$$s_n \ne$$$ '*').
Выведите единственную строку — текст книги без каракуль.
9 No***way.
No way.
17 Yes,*****you*can.
Yes, you can.
12 qWe**,r*.Ry.
qWe ,r .Ry.
Владелец магазина «Тингам» столкнулся с проблемой. К нему в магазин пришли $$$n$$$ человек и всем нужен сахар: $$$i$$$-й ($$$1 \le i \le n$$$) хочет купить $$$a_i$$$ килограмм сахара. Владелец магазина не понимает зачем людям столько сахара, но он точно знает, что всем покупателям сахара не хватит, потому что у него в магазине есть только $$$m$$$ килограмм сахара. Если какой-то покупатель не сможет купить сахар, он расстроится и больше не будет ходить в магазин «Тингам».
Владелец магазина не хочет терять клиентов. Чтобы сахара хватило всем, он решил установить ограничение $$$k$$$ — максимальное количество килограмм сахара, которое может купить один человек. Таким образом, когда $$$i$$$-й ($$$1 \le i \le n$$$) человек приходит в магазин он покупает $$$min(a_i, k)$$$ килограмм сахара (не больше чем ему нужно, но и не больше чем $$$k$$$ килограмм).
Владелец магазина хочет продать как можно больше сахара. Помогите хозяину магазина и найдите такое $$$k$$$, при котором каждому покупателю достанется $$$min(a_i, k)$$$ килограмм сахара и при этом суммарное количество проданного сахара будет максимальным, но не будет превышать запаса сахара в магазине $$$m$$$.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5, n \le m \lt \sum_{i=1}^n a_i$$$) — количество покупателей и количество килограмм сахара, которое есть в магазине соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, ..., a_n$$$ ($$$1 \le a_i \le 10^9, \sum_{i=1}^n a_i \gt n$$$). Число $$$a_i$$$ — количество килограмм сахара, которое хочет купить $$$i$$$-й покупатель.
Выведите одно число $$$k$$$, при котором каждому покупателю достанется $$$min(a_i, k)$$$ килограмм сахара и при этом суммарное количество проданного сахара будет максимальным, но не будет превышать запаса сахара в магазине $$$m$$$. Гарантируется, что такое $$$k$$$ всегда найдётся.
5 12 3 1 4 2 5
3
2 17 23 65
8
В первом примере необходимо установить ограничение $$$k = 3$$$. Таким образом клиенты купят $$$3 + 1 +3 + 2 + 3 = 12$$$ килограмм сахара. Ответы $$$2$$$ и $$$4$$$ неверные, так как при $$$k = 2$$$ клиенты купят меньше сахара чем при $$$k = 3$$$, а при $$$k = 4$$$ один из клиентов не сможет купить $$$min(a_i, k)$$$ килограмм сахара.
Во втором примере $$$k = 8$$$ и клиенты суммарно купят $$$16$$$ килограмм сахара.
Милане на день рождения подарили два набора юного химика. Эти наборы содержат химические элементы, причем каждый химический элемент имеет номер. Первый набор содержит $$$n$$$ химических элементов $$$a_1, a_2, ..., a_n$$$, второй набор содержит $$$m$$$ элементов $$$b_1, b_2, ..., b_m$$$. Все элементы в наборах имеют номера, отличные от нуля, но не обязательно положительные.
Химические элементы можно смешивать. Если смешать элемент $$$x$$$ с элементом $$$y$$$, то получится элемент $$$x + y$$$. Все очень просто!
Милана хочет получить новый элемент, которого нет ни в первом, ни во втором наборе. Для этого она хочет взять элемент из первого набора и смешать его с элементом из второго набора.
Формально, Милана хочет найти номера $$$i$$$ и $$$j$$$ ($$$ 1 \le i \le n, 1 \le j \le m$$$), такие, что $$$a_i + b_j$$$ не содержится среди чисел $$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_m$$$.
Помогите Милане найти элементы, которые необходимо смешать.
Первая строка входных данных содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — количество элементов в первом и во втором наборе соответственно.
Вторая строка входных данных содержит $$$n$$$ чисел $$$a_1, a_2, ..., a_n$$$ ($$$-10^9 \le a_i \le 10^9, a_i \ne 0, 1 \le i \le n$$$) — элементы первого набора.
Третья строка входных данных содержит $$$m$$$ чисел $$$b_1, b_2, ..., b_m$$$ ($$$-10^9 \le b_i \le 10^9, b_i \ne 0, 1 \le i \le m$$$) — элементы второго набора.
Выведите два числа $$$i$$$ и $$$j$$$ ($$$ 1 \le i \le n, 1 \le j \le m$$$), такие что $$$a_i + b_j$$$ не содержится среди чисел $$$a_1, a_2, ..., a_n, b_1, b_2, ..., b_m$$$. Если существует несколько таких пар чисел, вы можете вывести любой вариант. Гарантируется, что ответ всегда существует.
3 2 3 -2 4 1 6
1 2
1 1 7 -7
1 1
4 3 -1 -2 -3 -4 -1 -2 -3
4 3
В первом примере ответ $$$1$$$ и $$$2$$$. Если смешать первый элемент из $$$a$$$ и второй элемент из $$$b$$$ получим $$$a_1 + b_2 = 3 + 6 = 9$$$. Элемент $$$9$$$ не содержится среди чисел из $$$a$$$ или $$$b$$$. Также, верными ответами являются пары: $$$(2, 1), (3, 1), (3, 2)$$$. Любая из этих пар чисел будет засчитана за верный ответ.
Во втором примере существует единственный способ смешать элементы: взять первый элемент из $$$a$$$ и первый элемент из $$$b$$$.
Саша играет в новую MMORPG игру. В этой игре вся сила персонажа зависит от единственного параметра — удачи. Удача измеряется целым числом. Сейчас у персонажа Саши параметр удачи равен $$$k$$$.
В игре есть зелья, которые могут изменять удачу как в большую, так и в меньшую сторону. Существуют зелья двух типов:
1) Зелье первого типа устанавливает параметр удачи у персонажа равным $$$x$$$. Формально, если перед использованием этого зелья удача была $$$k$$$, то после его использование удача станет равна $$$x$$$.
2) Зелье второго типа изменяет параметр удачи у персонажа на $$$x$$$ единиц. Формально, если перед использованием этого зелья удача была $$$k$$$, то после его использование удача станет равна $$$k + x$$$.
У Саши есть всего $$$n$$$ волшебных зелий и при помощи них Саша хочет сделать своего персонажа как можно сильнее. Саша может использовать зелья в любом порядке.
Саша ещё не решил сколько зелий он хочет использовать и поэтому он просит вас для каждого $$$i$$$ ($$$1 \le i \le n$$$) найти максимальную удачу персонажа, если он использует $$$i$$$ зелий.
Первая строка входных данных содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5, -10^9 \le k \le 10^9$$$) — количество зелий у Саши и изначальный параметр удачи у персонажа.
Следующие $$$n$$$ строк входных данных описывают зелья. Каждая строка содержит два числа $$$t$$$ и $$$x$$$ ($$$1 \le t \le 2, -10^9 \le x \le 10^9$$$) — тип зелья и параметр $$$x$$$ у зелья.
Выведите $$$n$$$ чисел через пробел: $$$i$$$-е число выходных данных должно быть равно максимальной удаче после использования $$$i$$$ зелий.
4 5 1 10 2 10 2 -5 1 -1
15 20 20 20
3 -1 2 -1 2 -1 2 -1
-2 -3 -4
3 7 1 10 2 -5 2 -3
10 10 10
В первом примере изначальный параметр удачи у персонажа равен $$$5$$$.
Если использовать одно зелье, то максимальная удача достигается при использовании второго зелья: $$$5 + 10 = 15$$$.
Если использовать два зелья, то для получения максимальной удачи, нужно сначала использовать первое зелье и получить удачу $$$10$$$, а после — второе зелье и получить удачу $$$10 + 10 = 20$$$.
Если использовать три зелья, то для получения максимальной удачи, нужно использовать зелья в следующем порядке: $$$4, 1, 2$$$. В таком случае, сначала показатель удачи станет равным $$$-1$$$, затем $$$10$$$ и поле третьего зелья $$$20$$$. В данном случае, можно вместо зелья №4 использовать зельe №3, но максимальный результат после трех зелий, все равно будет равен $$$20$$$.
Если использовать четыре зелья, то для получения максимальной удачи, нужно использовать зелья в следующем порядке: $$$3, 4, 1, 2$$$ и получить удачу равную $$$20$$$.
Во втором примере все зелья уменьшают текущую удачу на $$$1$$$, поэтому каждый следующий ответ на $$$1$$$ меньше чем предыдущий.
В третьем примере всегда выгодно использовать зелье №1 последним и тогда показатель удачи будет равен $$$10$$$.
Лера решила отправиться в путешествие. Она уже выбрала $$$n$$$ мест, которые она хочет посетить и определила порядок посещения мест $$$p_1, p_2, ..., p_n$$$. Каждое место задается его координатой — точкой в двумерном пространстве. Лера планировала сначала посетить место с координатой $$$p_1$$$, затем место с координатой $$$p_2$$$ и т.д. Из одного места в другое Лера будет путешествовать кратчайший маршрутом — по прямой.
После некоторых расчетов Лера поняла, что ее путешествие слишком длинное. Чтобы сократить своё путешествие, Лера готова отказаться от посещения ровно одного места. Помогите Лере и найдите номер места, которое ей стоит пропустить, чтобы её путешествие стало как можно короче. Под «длиной» путешествия понимается суммарное расстояние, которое предстоит преодолеть Лере. Для лучшего понимания условия смотрите примечание.
Первая строк содержит единственное целое число $$$n$$$ ($$$3 \le n \le 100000$$$) — количество мест, которая Лера хочет посетить.
Следующие $$$n$$$ строк описывают координаты мест: $$$i+1$$$-я строка входных данных содержит два целых числа $$$x$$$ и $$$y$$$ ($$$-1000 \le x, y \le 1000$$$) — координаты $$$i$$$-го места.
Выведите единственное число — номер места, которое Лере стоит пропустить, чтобы суммарное пройденное расстояние было минимально возможным. Если таких мест несколько, разрешается вывести любое из них.
Формально, пусть суммарное расстояние, которое пройдет Лера, согласно вашему ответу равно $$$a$$$, а согласно ответу жюри равно $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$, то есть абсолютная или относительная ошибка между вашим ответом и ответом жюри не должна превосходить $$$10^{-9}$$$.
5 0 0 3 5 3 0 8 5 7 1
2
4 0 0 0 1 1 1 1 0
1
3 5 5 5 5 5 5
1
В первом примере путь Леры выглядит следующим образом:
Если Лера уберет первое место из маршрута, суммарное расстояние которое она пройдет равно: $$$dist(p2, p3) + dist(p3, p4) + dist(p4, p5) = 5 + 7.07 + 4.12 = 16.19$$$.
Если Лера уберет второе место из маршрута, суммарное расстояние которое она пройдет равно: $$$dist(p1, p3) + dist(p3, p4) + dist(p4, p5) = 3 + 7.07 + 4.12 = 14.19$$$.
При исключении третьего места из маршрута получаем, что суммарное расстояние равно: $$$dist(p1, p2) + dist(p2, p4) + dist(p4, p5) = 5.83 + 5 + 4.12 = 14.95$$$.
Если пропустить четвертое места в маршруте, то суммарное расстояние равно: $$$dist(p1, p2) + dist(p2, p3) + dist(p3, p5) = 5.83 + 5 + 4.12 = 14.95$$$.
Если Лера уберет пятое места из маршрута, суммарное расстояние которое она пройдет равно: $$$dist(p1, p2) + dist(p2, p3) + dist(p3, p4) = 5.83 + 5 + 7.07 = 17.9$$$.
Таким образом, чтобы путешествие Леры стало как можно короче, ей следует пропустить второе место.
*$$$dist(p_i, p_j)$$$ — расстояние между точками $$$i$$$ и $$$j$$$ по прямой.
Во втором примере Лере следует пропустить $$$1$$$ или $$$4$$$ место (можно вывести как $$$1$$$, так и $$$4$$$ — оба ответа будут верными). Суммарное пройденное расстояние в таком случае равно $$$2$$$.
В третьем примере Лера собирается посетить одно и тоже место три раза, поэтому суммарное пройденное расстояние в любом случае будет $$$0$$$. Значит можно вывести любое число от $$$1$$$ до $$$3$$$.
Андрей пишет контрольную по математике. Одно из заданий на контрольной это найти x в уравнении.
Андрей совсем не знаком с уравнениями. Он решил, что фраза «найти x» означает, что ему нужно указать на каких позициях в уравнении расположено $$$x$$$. Например, в уравнении $$$4x+17+x=1$$$, неизвестная $$$x$$$ расположена на $$$2$$$-й и $$$7$$$-й позиции, поэтому Андрей в качестве ответа напишет $$$2$$$ и $$$7$$$.
Помогите Андрею и напишете программу, которая по строке, содержащей уравнение, найдет все позиции $$$x$$$.
В первой строке содержится единственное целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — длина строки $$$s$$$.
Во второй строке содержится строка $$$s$$$, которая представляет уравнение. Строка $$$s$$$ может состоять из цифр, знаков плюс, минус, равно и латинского символа 'x' ($$$s_i \in \{$$$'0'-'9', '+', '-', '=', 'x'$$$\}, 1 \le i \le n$$$).
Выведите все позиции $$$x$$$ в одну строку через пробел в возрастающем порядке. Обратите внимание, что входные данные могут не содержать $$$x$$$. В данном случае вам необходимо ничего не выводить или вывести пустую строку.
9 4x+17+x=1
2 7
4 3x=2
2
5 xx=x4
1 2 4