Воскресным утром в кинотеатре в двух залах одновременно начался показ фильмов. Фильм, показываемый в первом зале, имеет длительность $$$a$$$ минут, а фильм, показываемый во втором зале — $$$b$$$ минут. В каждом из залов после окончания фильма его сразу начинают показывать сначала. Любой посетитель может войти в любой из залов.
Лука знает, что с момента начала показа фильмов прошло $$$t$$$ минут. Ему не важно, какой фильм посмотреть, так как Лука просто хочет весело провести время. Однако, он нетерпелив, поэтому мальчик хочет узнать, через какое минимальное время хотя бы в одном из залов начнут показывать фильм сначала.
Первая строка содержит одно целое число $$$a$$$ ($$$1 \le a \le 2 \cdot 10^9$$$) — длительность первого фильма в минутах.
Вторая строка содержит одно целое число $$$b$$$ ($$$1 \le b \le 2 \cdot 10^9$$$) — длительность второго фильма в минутах.
Третья строка содержит одно целое $$$t$$$ ($$$0 \le t \le 2 \cdot 10^{18}$$$) — время в минутах, прошедшее с начала показа фильмов.
Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Выведите одно целое число — минимальное время в минутах, через которое хотя бы в одном зале начнут показывать фильм сначала.
Решения, правильно работающие только для случаев, когда $$$t$$$ не превосходит $$$2 \cdot 10^9$$$, будут оцениваться в $$$60$$$ баллов.
3 7 10
2
5 5 10
0
3 9 8
1
2 4 1000000000000000000
0
Рассмотрим первый пример из условия. Фильм, показываемый в первом зале, имеет длительность $$$3$$$ минуты, а фильм, показываемый во втором зале — $$$7$$$ минут. Таким образом, первый фильм начинается спустя $$$0, 3, 6, 9, 12, \ldots$$$ минут после начала показа фильмов, а второй фильм — спустя $$$0, 7, 14, 21, 28, \ldots$$$ минут после начала показа фильмов. Лука знает, что с начала показа фильмов прошло $$$10$$$ минут. Для того, чтобы попасть на начало первого фильма, ему придется подождать $$$12 - 10 = 2$$$ минуты, а чтобы попасть на начало второго фильма — $$$14 - 10 = 4$$$ минуты.
Рассмотрим второй пример из условия. Оба фильма имеют длительность $$$5$$$ минут и начинаются спустя $$$0, 5, 10, 15, \ldots$$$ минут после начала показа фильмов. Так как с момента начала показа прошло $$$10$$$ минут, Луке не придется ждать.
Рассмотрим третий пример из условия. Оба фильма начнутся спустя $$$9$$$ минут после начала показа фильмов, поэтому вне зависимости от выбора фильма Луке придется подождать $$$9 - 8 = 1$$$ минуту.
На карте «Шестерочки» у Луки уже есть $$$t$$$ бонусных баллов, за которые он может покупать фигурки динозавров. Лука хочет купить всю коллекцию новых динозавров, состоящую из $$$r$$$ фигурок. Один динозавр стоит $$$l$$$ бонусных баллов.
Баллы в «Шестерочке» можно получить следующим образом: за покупку первого товара на карту начисляется $$$p_1$$$ баллов, за покупку второго товара — $$$p_2$$$ баллов, за покупку третьего товара — $$$p_3$$$ баллов, за покупку четвертого товара — снова $$$p_1$$$ баллов, за покупку пятого товара — $$$p_2$$$ баллов, и так далее. Какое минимальное количество товаров должен купить Лука, чтобы приобрести всю коллекцию динозавров?
Обратите внимание на то, что покупка товаров осуществляется не на бонусные баллы, а за настоящие деньги.
Первая строка содержит одно целое число $$$t$$$ ($$$0 \le t \le 10^{18}$$$) — изначальное количество баллов на карте.
Вторая строка содержит одно целое число $$$r$$$ ($$$0 \le r \le 10^{9}$$$) — количество динозавров в коллекции.
Третья строка содержит одно целое число $$$l$$$ ($$$0 \le l \le 10^{9}$$$) — стоимость одного динозавра.
Четвертая строка содержит одно целое число $$$p_1$$$ ($$$0 \le p_1 \le 10^{17}$$$) — количество баллов, начисляемых за покупку.
Пятая строка содержит одно целое число $$$p_2$$$ ($$$0 \le p_2 \le 10^{17}$$$) — количество баллов, начисляемых за покупку.
Шестая строка содержит одно целое число $$$p_3$$$ ($$$0 \le p_3 \le 10^{17}$$$) — количество баллов, начисляемых за покупку.
Гарантируется, что $$$p_1 + p_2 + p_3 \gt 0$$$.
Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Выведите одно число — минимальное количество товаров, которые должен купить Лука, чтобы приобрести всю коллекцию динозавров.
Решения, правильно работающие только для случаев, когда $$$t$$$ не превосходит $$$10^6$$$, $$$l$$$ и $$$r$$$ не превосходят $$$10^3$$$, а $$$p_1$$$, $$$p_2$$$ и $$$p_3$$$ не превосходят $$$10^6$$$, будут оцениваться в $$$35$$$ баллов.
Решения, правильно работающие только для случаев, когда Луке потребуется покупать по три товара, будут оцениваться в $$$25$$$ баллов.
8 2 22 58 70 31
1
2 2 5 2 1 3
4
66 83 57 54 78 98
62
Рассмотрим второй пример. Изначально у Луки есть два бонусных балла, при том что в коллекции два динозавра, каждый из которых стоит по пять баллов. Сначала Лука купит первый товар и получит два балла за первую покупку. Далее Лука купит второй товар, получит один бонусный балл, в сумме пять бонусных баллов. Далее он купит третий товар и получит еще еще три бонусных балла, в итоге восемь баллов. На покупку всех моделей из коллекции до сих пор не хватает, поэтому Луке придется сделать еще одну, четвертую покупку, после чего он получит два балла (потому что за четвертую покупку начисляется столько же, сколько и за первую). Теперь у Луки десять баллов, на которых он может купить всю коллекцию динозавров. Значит, ответ — четыре.
Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной $$$n$$$ метров.
Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на $$$k$$$ или $$$k + 1$$$ метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длина окружности в метрах.
Вторая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 10^9$$$) — характеристика длины прыжка кузнечика в метрах.
Гарантируется, что $$$1 \le n \cdot k \le 10^9$$$.
Выведите одно целое число — минимальное количество прыжков, которое придется сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Решения, правильно работающие только для случаев, когда $$$n$$$ не превосходит $$$100$$$, будут оцениваться в $$$60$$$ баллов.
10 3
3
10 1
5
11 7
3
Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:
Таким образом, суммарно кузнечик преодолеет $$$3 + 4 + 3 = 10$$$ метров, то есть вернется в исходную точку.
Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины $$$2$$$.
В третьем примере из условия можно выполнить один прыжок длины $$$8$$$ и два прыжка длины $$$7$$$. Таким образом, суммарно кузнечик преодолеет $$$8 + 7 + 7 = 22$$$ метра, то есть обойдет окружность дважды и вернется в исходную точку.
У Луки есть массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. К каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций:
Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива принимли значение, равное единице (то есть, $$$a_1 = a_2 = \ldots = a_n = 1$$$).
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$) — количество элементов массива.
Вторая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 10^5$$$) — количество энергии, необходимое для выполнения операции первого типа.
Каждая из следующих $$$n$$$ строк содержит одно целое число $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) — элементы массива.
Обратите внимание, что ответ может быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Выведите одно целое число — минимальное количество энергии, необходимое для требуемого преобразования массива.
Решения, правильно работающие только для случаев, когда $$$k = 1$$$, будут оцениваться в $$$25$$$ баллов.
Решения, правильно работающие только для случаев, когда все $$$a_i$$$ не превосходят $$$10^5$$$, будут оцениваться в $$$50$$$ баллов.
3 1 4 1 3
3
1 100 10
9
Рассмотрим первый пример из условия.
Во втором примере из условия применение первой операции расходует слишком много единиц энергии, поэтому выгодно применить вторую операцию девять раз.
Лука смог приобрести всю коллекцию динозавров из «Шестерочки» и обнаружил, что в динозаврах есть коммутаторы, поэтому ему захотелось их объединить в одну локальную сеть.
Он расставил на декартовой плоскости всю коллекцию, то есть местоположение каждого динозавра задано двумя числами — координатами по оси $$$x$$$ и $$$y$$$.
Лука хочет соединить их проводами так, чтобы между любыми двумя динозаврами существовал путь по этим проводам. Луку раздражают спутанные провода, поэтому никакие два провода не должны пересекаться (пересечения в концах отрезков разрешены). Кроме того, у Луки мало денег на покупку проводов, поэтому общее количество проведенных отрезков не должно превышать $$$2n$$$.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^3$$$) — количество динозавров.
В следующих $$$2n$$$ строках заданы координаты динозавров. В каждой строке записано одно целое число: первая строка содержит координату по оси $$$x$$$ для первого динозавра, вторая строка — координату по оси $$$y$$$ для первого динозавра, третья строка — координату по оси $$$x$$$ для второго динозавра, и так далее. Таким образом координата $$$x_i$$$ для $$$i$$$-го динозавра находится $$$(2i)$$$-й строке входных данных, координата $$$y_i$$$ для $$$i$$$-го динозавра находится в $$$(2i + 1)$$$-й строке входных данных. Гарантируется, что $$$(-10^9 \le x_i, y_i \le 10^9)$$$, а также никакие два динозавра не находятся в одной точке плоскости.
В первой строке выведите одно число $$$m$$$ — количество проведенных проводов, либо число $$$-1$$$, если соединить динозавров описанным в условии способом невозможно.
Если существует подходящее под условие соединение, то в следующих $$$m$$$ строках выведите по два целых числа — порядковые номера динозавров, соединенных очередным проводом.
Если решений несколько, можно вывести любое из них.
Решения, правильно работающие только для случаев, когда $$$n$$$ не превосходит $$$4$$$, будут оцениваться в $$$25$$$ баллов.
Решения, правильно работающие только для случаев, когда никакие три динозавра не лежат на одной прямой, будут оцениваться в $$$25$$$ баллов.
Решения, правильно работающие только для случаев, когда у всех динозавров координаты по оси $$$x$$$ различны, будут оцениваться в $$$25$$$ баллов.
6 8 7 -8 6 -7 -3 9 -3 6 2 4 1
7 1 2 1 5 2 3 2 6 3 6 3 4 4 5
3 -3 4 8 -4 -1 0
2 1 3 3 2
Иллюстрация ответа для первого примера из условия:
