Маленькая Сафия только учится считать. Она умеет считать только до $$$k$$$ и очень часто забывает первые $$$t$$$ чисел. Поэтому она считает так: $$$t + 1, t + 2, t + 3, \dots, k, t + 1, t + 2, \dots$$$ У Сафии есть $$$n$$$ карандашей. Помогите ей подсчитать карандаши в ее системе подсчета.
В первой строке дано $$$n$$$ $$$(1 \le n \le 10^{18})$$$ – количество карандашей.
На второй строке дано $$$k$$$ $$$(k \le n)$$$.
На третьей строке дано $$$t$$$ $$$(0 \le t \lt k)$$$.
Вывести ответ на задачу.
В этой задаче две группы тестов.
| Группа | Баллы | Ограничения |
| $$$1$$$ | 50 | $$$n \le 10^6$$$ |
| $$$2$$$ | 50 | нет ограничений |
10 5 2
3
8 4 2
4
В первом тесте Сафия считает до $$$5$$$, но первые $$$2$$$ числа забывает, поэтому получается $$$3, 4, 5, 3, 4, 5, 3, 4, 5, 3$$$. Ответ: $$$3$$$.
После вкусного обеда в столовой ученикам приходится стоять в очереди, чтобы сдать посуду. Стоять в очереди никто не хочет, потому что тратится время бесполезно. Динислам смекнул, что можно встать не в самый конец очереди, а на много дальше от конца. Идея такая: он подходит к ученику стоящему дальше от конца, и забирает его посуду, сам при этом встает на его место. Ученику, который отдал посуду, стоять в очереди не нужно, а Динислам не в самом конце. В итоге посуду сдает только один человек. Все в плюсе!
В начальный момент времени в очереди стоят $$$n$$$ человек. Дальше приходит Динислам, который заражает своей супер идеей подходящих после него (ему самому, естественно, своя идея тоже нравится :-). Однако не все готовы воспользоваться этой супер идеей. У каждого ученика есть свой предел: он равен либо 1, либо 2, это означает сколько посуды ученик может нести с собой.
За 1 секунду времени 1 ученик может сдать всю посуду, которая у него имеется.
Замена одного ученика на другого происходит моментально, времени не занимает.
Динислам хочет узнать за какое минимальное время ученики сдадут всю свою посуду. В начальный момент времени считать, что очередь с Динисламом уже образовалась.
На первой строке даны $$$n$$$ и $$$k$$$ ($$$1 \le k, n \le 10^5$$$) – количество учеников в очереди в начальный момент времени и количество учеников, идущих к очереди вместе с Динисламом.
В следующей строке даны $$$k$$$ чисел ($$$a_1, a_2, ..., a_k$$$) – пределы учеников, т.е. количество посуды, которую они готовы нести. Каждое из чисел может быть либо $$$1$$$ либо $$$2$$$. Если $$$a_i = 1$$$, то ученик не собирается уходить со своего места, брать чужую посуду и вставать на другое место, иначе ученик может встать в основную очередь вместо другого ученика, либо захочет забрать посуду впереди стоящего, так как в этом случае время также экономится.
Минимальное время, за которое все ученики сдадут посуду.
| Группы | Баллы | Ограничения |
| $$$1$$$ | $$$25$$$ | $$$a_i = 1$$$ |
| $$$2$$$ | $$$25$$$ | $$$a_i = 2$$$ |
| $$$3$$$ | $$$50$$$ | нет ограничений |
6 4 1 2 1 2
8
3 6 2 2 2 2 2 2
5
2 5 1 1 1 1 1
7
В первом примере 2 и 4 ученики могут взять посуду, как у стоящих в первой очереди, так и во второй очереди и встать на их место.
Во втором примере 3 первых ученика из второй очереди перемещаются в первую, сдают посуду за 3 секунды, далее 5-й берет посуду у четвертого и сдает, и остается 6-му сдать свою. Получаем 5 секунд.
В третьем примере никто никуда перемещаться не хочет, поэтому ответ 7 секунд.
В начальный момент времени 
После того как ученики из второй очереди перегруппировались $$$ \\ $$$ (синего цвета человечки – это ученики, взявшие посуду и вставшие на другое место)
У Кузи скоро день рождения, поэтому он собирается позвать друзей. Но какой день рождения без торта?
Кузя знает, что в его городе есть $$$n$$$ пекарен, где он может заказать торт. $$$i$$$-я пекарня разрезает свой торт на какое-то $$$a_i$$$ количество кусочков. К сожалению, Кузя не знает, в какой пекарне его мама будет заказывать торт, поэтому он хочет позвать столько гостей, что всем, включая его самого, достанется одинаковое количество кусочков торта, и при этом ни один кусочек не останется лишним.
Помогите Кузе узнать, какое максимальное количество гостей смогут прийти к нему на день рождения?
Первая строка содержит одно целое число $$$n$$$ $$$(1 \le n \le 100\,000)$$$ - количество пекарен в городе Кузи.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, где $$$a_i$$$ - количество кусочков, на которое разрезает торт $$$i$$$-я пекарня.
Выведите одно число $$$x$$$ - максимальное количество гостей, которые смогут прийти к Кузе на день рождения.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Подзадача | Баллы | Дополнительные | Необходимые |
| ограничения | подзадачи | ||
| 0 | 0 | Тесты из условия | — |
| 1 | 10 | $$$n = 1$$$ | — |
| 2 | 10 | $$$n = 2$$$ | 1 |
| 3 | 10 | все $$$a_i$$$ одинаковы | — |
| 4 | 20 | $$$a_i \le 10^4, n \le 100$$$ | 0 |
| 5 | 20 | $$$a_i \le 10^6$$$ | 0, 4 |
| 6 | 30 | Нет | 0-5 |
2 5 10
4
5 2 7 8 10 5
0
Карим является управляющим одного небольшого города. Дорожная система в этом городе состоит из $$$n$$$ перекрёстков и $$$m$$$ дорог. Каждая дорога соединяет два различных перекрестка, и между двумя перекрестками проходит не более одной дороги. Все дороги являются двусторонними.
В городе обажают кататься на автомобилях. Поэтому если по дорогам можно наматывать круги, то любой автомобилист с удовольстивем будет кататься до самого вечера. Такая ситуация не устраивает Карима, так как дороги таким образом очень быстро портятся.
Карим понял, что он может ориентировать каждую дорогу в какую-то сторону и таким образом избавиться от циклом. Сам Карим не справился с этой задачей, поэтому просит вас ориентировать каждую дорогу так, чтобы в городе больше нельзя было бесконечно передвигаться по дорогам.
Если есть несколько вариантов ответа, то выведите любой из них.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le n \le 2 \cdot 10^5, n - 1 \le m \le min(\frac{n(n - 1)}{2}, 2 \cdot 10^5))$$$ — количество перескрестков и дорог соответственно.
Следующие $$$m$$$ строк входных данных содержат описание дорог, по два целых числа $$$u$$$ и $$$v$$$ $$$(1 \le u,v \le n, u \neq v)$$$ — номера перекрестков, соединённых дорогой. Гарантируется, каждая дорога соединяет разные перекрестки и любые два перекрестка соединяет максимум одна дорога.
Выведите $$$m$$$ пар чисел — получившиеся ориентированные дороги. Для каждой дороги выведите два числа — начало и конец дороги соответственно.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные | Необх. группы | Комментарий |
| ограничения | ||||
| 0 | 0 | – | – | Тесты из условия. |
| 1 | ? | – | ||
| 2 | ? | – | ||
| 3 | ? | – |
4 4 1 2 3 2 2 4 4 3
2 1 3 2 4 2 4 3
Иллюстрация к примеру:
Вчера Саша решил открыть чайный магазин на улице, где он живёт. У него есть $$$m$$$ вариантов расположения магазина. Вариант под номером $$$i$$$ задаётся натуральным числом $$$x_i$$$ — расстоянием от начала улицы.
На улице живёт $$$n$$$ человек. Человек под номером $$$j$$$ живёт на расстоянии $$$y_j$$$ от начала улицы. Саша узнал, что $$$j$$$-й человек купит одну чайную упаковку, если сумма расстояния, которое ему нужно пройти от дома до магазина, и цены чайной упаковки не будут превышать число $$$a_j$$$. То есть, если Саша выберет помещение под номером $$$i$$$ и установит цену на чай равную числу $$$c$$$, то $$$j$$$-й человек обязательно купит ровно одну упаковку чая, если $$$|x_i - y_j| + c \le a_j$$$. Человек не может купить больше одной упаковки.
Саша уже изготовил $$$k$$$ упаковок и собирается всё продать. Помогите ему установить максимальную цену упаковки чая, чтобы он смог продать все $$$k$$$ упаковок без остатка. Либо выведите $$$-1$$$, если это невозможно.
В первой строке дано три числа $$$n$$$, $$$m$$$, $$$k$$$ $$$(1 \le n, m, k \le 10^5)$$$ — количество людей, которые живут на улице (в своих домах, разумеется), количество вариантов площадок для расположения магазина и количество готовых упаковок чая соответственно.
В следующих $$$n$$$ строках даны $$$n$$$ пар чисел. В $$$j$$$-ой строке находятся два числа $$$y_j$$$ и $$$a_j$$$ $$$(1 \le y_j, a_j \le 10^9)$$$.
И в последней строке даны $$$m$$$ чисел $$$x_1, x_2, x_3, \dots, x_m$$$ $$$(1 \le x_i \le 10^9)$$$, где $$$x_i$$$ — расстояние $$$i$$$-й площадки для расположения магазина.
Выведите, какую максимальную цену одной упаковки чая нужно установить Саше, чтобы он смог продать все $$$k$$$ упаковок, или $$$-1$$$, если это невозможно.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные | Необх. группы | Комментарий |
| ограничения | ||||
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 13 | $$$1 \le n, m, a_i \le 100$$$ | – | |
| 2 | 19 | $$$1 \le n, m \le 1000$$$ | 1 | |
| 3 | 33 | $$$1 \le n \le 10^5, m = 1$$$ | – | Существует только одна |
| площадка для магазина | ||||
| 4 | 35 | – | 1, 2, 3 |
3 4 2 1 5 5 3 2 6 1 2 3 4
5
4 3 4 1 2 4 1 6 3 7 3 3 6 9
-1
5 1 3 2 1 3 2 5 3 7 4 8 5 3
0