Игорь начинает готовиться к олимпиаде, которая состоится через $$$N$$$ дней. Игорь готовится к олимпиаде по вечерам, после того, как возвращается из школы и делает всю домашнюю работу. Каждый вечер Игорь может либо учиться, либо лечь спать пораньше. Если Игорь сегодня ложится спать пораньше, его уровень бодрости повышается на $$$A$$$ единиц, если учится — снижается на $$$B$$$ единиц.
Игорь хочет составить себе расписание на каждый день — для каждого дня выбрать, будет ли он учиться или ляжет спать пораньше. При этом Игорь хочет составить расписание на $$$N$$$ дней таким образом, чтобы учиться как можно больше дней, а его уровень бодрости через $$$N$$$ дней должен быть таким же, как и сейчас.
Определите, сможет ли Игорь составить себе такое расписание, и, если сможет, вычислите, сколько дней Игорь будет учиться. Считается, что уровень бодрости может быть отрицательным.
В первой строке вводится натуральное число $$$N$$$ ($$$1 \le N \le 10^{18} $$$) — количество дней до олимпиады.
Во второй строке вводится натуральное число $$$A$$$ ($$$1 \le A \le 10^{18} $$$) — число единиц, на которое повышается бодрость Игоря за каждый день, когда он выбирает лечь спать пораньше.
В третьей строке вводится натуральное число $$$B$$$ ($$$1 \le B \le 10^{18} $$$) — число единиц, на которое понижается бодрость Игоря за каждый день, когда он выбирает учиться.
Гарантируется, что $$$ N \cdot A \le 10^{18} $$$
Если Игорь не сможет составить себе расписание, удовлетворяющее условиям, выведите $$$-1$$$.
Если Игорь сможет составить себе расписание, удовлетворяющее условиям, выведите количество дней учебы в этом расписании.
Гарантируется, что решения, работающие корректно при $$$n \le 10^5$$$, будут получать не менее 50 баллов.
462
3
212
-1
В первом примере из условия Игорь может учиться 3 дня, а отдыхать один. За каждый день учебы его бодрость уменьшается на 2, то есть всего уменьшается на 6, а за день отдыха — увеличивается на 6. Таким образом, его уровень бодрости через 4 дня останется таким же.
Во втором примере из условия если Игорь один день отдыхает, а второй учится, его уровень бодрости сначала увеличится на 1, а потом уменьшится на 2. Таким образом, через 2 дня он будет на 1 меньше, чем был изначально. В случае, если Игорь будет 2 дня учится, его уровень бодрости уменьшится на 4, а если будет 2 дня отдыхать, его уровень бодрости увеличится на 2. Таким образом, не существует сценария, при котором его уровень бодрости не изменится за 2 дня. Поэтому, в этом примере ответ на задачу $$$-1$$$.
Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему.
Для отправки на Codeforces создайте файлы с ответами 01.out, 02.out и так далее до 10.out, а затем сожмите их в архив ZIP.
Однажды всемирно известный Доцент, вновь доказывая Великую теорему Ферма, обнаружил удивительное свойство! Взяв 4 различных простых числа $$$A, B, C, D$$$, он заметил, что произведение $$$A \cdot B$$$ и произведение $$$C \cdot D$$$ дают одинаковые остатки от деления на некоторое натуральное число $$$K$$$.
Как настоящий Доцент, он решил узнать, при каком максимальном $$$K$$$ может выполняться такое равенство. К сожалению, сейчас Доцент слишком занят доказательством теоремы Ферма, поэтому он поручил эту задачу Вам.
| Номер теста | Балл | $$$A$$$ | $$$B$$$ | $$$C$$$ | $$$D$$$ |
| 1 | 10 | $$$2$$$ | $$$3$$$ | $$$5$$$ | $$$7$$$ |
| 2 | 10 | $$$2$$$ | $$$5$$$ | $$$3$$$ | $$$7$$$ |
| 3 | 10 | $$$19$$$ | $$$17$$$ | $$$5$$$ | $$$13$$$ |
| 4 | 10 | $$$23$$$ | $$$5$$$ | $$$3$$$ | $$$13$$$ |
| 5 | 10 | $$$139$$$ | $$$431$$$ | $$$311$$$ | $$$181$$$ |
| 6 | 10 | $$$521$$$ | $$$409$$$ | $$$821$$$ | $$$433$$$ |
| 7 | 10 | $$$691$$$ | $$$379$$$ | $$$66972713$$$ | $$$987460057$$$ |
| 8 | 10 | $$$569$$$ | $$$443$$$ | $$$461047751$$$ | $$$307341751$$$ |
| 9 | 10 | $$$1335991$$$ | $$$6344003$$$ | $$$3226781$$$ | $$$1341701$$$ |
| 10 | 10 | $$$928625227$$$ | $$$746772233$$$ | $$$698464181$$$ | $$$555887491$$$ |
Выведите единственное число — максимальное K, при котором выполняется равенство.
Каждый тест оценивается независимо в 10 баллов.
Рассмотрим пример, при котором $$$A = 3, B = 5, C = 11, D = 2$$$.
$$$A \cdot B = 15$$$, $$$C \cdot D = 22$$$. Тогда можно заметить, что при $$$K \gt 22$$$ остатки от деления на $$$K$$$ не будут меняться и будут различны. Легко убедиться, что для $$$K \le 22$$$ максимальное значение, при котором выполняется нужное равенство, будет $$$K=7$$$.
Эта задача с открытым тестированием. Решения по этой задаче тестируются «в открытую», во время олимпиады. Вы можете не дожидаться окончания олимпиады, чтобы узнать итоговый балл вашего решения по этой задаче.
Как известно, Тимур — лучший поставщик продуктов во всей Московской области. В Московской области существует всего $$$n$$$ ресторанов, в $$$c$$$ из которых Тимур уже поставляет продукты. Также, $$$m$$$ пар ресторанов являются соседями друг для друга, при этом ресторан не может быть соседом сам себе и никакие два ресторана не могут быть соседями дважды.
Так как Тимур не разбирается в рекламе, то новости о его качественной работе распространяются только с помощью сарафанного радио, а именно — ресторан решает нанять Тимура как поставщика, если хотя бы в $$$k$$$ соседей этого ресторана Тимур уже поставляет продукты.
Тимур очень дальновидный, поэтому его интересует, какие из ресторанов однажды наймут его как поставщика. Но так как сейчас он занят развозом товара, он поручил эту непростую задачу Вам!
Первая строка содержит три целых числа $$$n, m, k$$$ $$$(1 \leq k \leq n \leq 2 \cdot 10^5, 1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5))$$$, обозначающие количество ресторанов, количество пар соседей и количество соседей, необходимое для того, чтобы ресторан нанял Тимура, соответственно.
В следующих $$$m$$$ строчках содержится описание пар соседних ресторанов. Каждая строка содержит два различных целых числа $$$u_i, v_i$$$ — номера двух ресторанов, соседних друг другу $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$. Гарантируется что одна и та же пара не встречается в этом списке дважды.
В следующей строке содержится целое число $$$c$$$ $$$(0 \leq c \leq n)$$$, обозначающее количество ресторанов, в которые Тимур с самого начала поставляет продукты.
В следующей строке содержится $$$c$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера ресторанов, в которые Тимур уже поставляет продукты.
В первой строке выведите целое число $$$a$$$ — количество ресторанов, которые однажды наймут Тимура как поставщика.
Во второй строке выведите $$$a$$$ целых чисел — номера всех ресторанов, в которые Тимур будет поставлять продукты, в любом порядке .
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся при прохождении всех тестов этой группы, а также при прохождении тестов необходимых подгрупп. Баллы за соответствующие группы указаны в таблице.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий | |
| $$$n, m$$$ | $$$k$$$ | ||||
| 0 | 0 | – | – | – | Тест из условия |
| 1 | 10 | $$$1 \leq n, m \leq 500$$$ | $$$k = 1$$$ | – | – |
| 2 | 10 | – | $$$k = 1$$$ | 1 | – |
| 3 | 20 | $$$1 \leq n, m \leq 500$$$ | – | 0, 1 | – |
| 4 | 20 | $$$1 \leq n, m \leq 2000$$$ | – | 0, 1, 3 | – |
| 5 | 40 | – | – | 0, 1, 2, 3, 4 | – |
5 5 21 21 32 33 44 531 2 5
5 1 2 3 4 5
Пояснение к тесту из условия выглядит следующим образом:
 |  |  |
Изначально только в три ресторана с номерами 1, 2 и 5 Тимур поставляет продукты. После этого ресторан с номером 3 также решает нанять Тимура, ведь у него есть двое соседей, в которые Тимур уже поставляет продукты. Далее ресторан под номером 4 тоже решает нанять Тимура, ведь его соседи с номерами 3 и 5 уже работают с Тимуром. Таким образом, все 5 ресторанов будут сотрудничать с Тимуром.
Эта задача с открытым тестированием. Решения по этой задаче тестируются «в открытую», во время олимпиады. Вы можете не дожидаться окончания олимпиады, чтобы узнать итоговый балл вашего решения по этой задаче.
Однажды Саше попалась последовательность $$$a$$$, состоящая из $$$10^9$$$ целых неотрицательных чисел. Ему известны значения первых $$$n$$$ элементов последовательности, остальные элементы равны нулю. Саша любит битовые операции и структуры данных, поэтому он решил дать Вам следующую задачу: необходимо выполнить $$$q$$$ запросов. Запросы бывают двух типов:
1 $$$i$$$ $$$v$$$ — заменить элемент с индексом $$$i$$$ на число $$$v$$$, т.е. присвоить $$$a_{i}$$$ = $$$v$$$.
2 $$$z$$$ — вычислить количество целых неотрицательных чисел $$$x$$$, таких что $$$(a_{1}$$$ $$$or$$$ $$$a_{2}$$$ $$$or$$$ ... $$$or$$$ $$$a_{10^9}$$$ $$$or$$$ $$$x) \leq z$$$
Напишите программу, которая сможет обработать эти запросы достаточно быстро.
В первой строке входных данных содержится одно целое число $$$n$$$ (1 $$$\leq$$$ $$$n$$$ $$$\leq$$$ $$$100$$$ $$$000$$$) — количество первых элементов массива $$$a$$$, которые знает Саша.
Во второй строке содержится $$$n$$$ целых чисел $$$a_1$$$, $$$a_{2}$$$, ... $$$a_{n}$$$ ($$$0$$$ $$$\leq$$$ $$$a_{i}$$$ $$$\leq$$$ $$$2^{30} - 1$$$).
В третьей строке входных данных содержится одно целое число $$$q$$$ ($$$1$$$ $$$\leq$$$ $$$q$$$ $$$\leq$$$ $$$100$$$ $$$000$$$) — количество запросов.
Следующие $$$q$$$ строк описывают запросы. В каждой из них находится числo $$$t$$$ ($$$1$$$ $$$\leq$$$ $$$t$$$ $$$\leq$$$ $$$2$$$) — тип запроса.
Если $$$t$$$ = 1, то в строке содержатся еще два целых числа $$$i$$$ и $$$v$$$ ($$$1$$$ $$$\leq$$$ $$$i$$$ $$$\leq$$$ $$$10^9$$$, $$$0$$$ $$$\leq$$$ $$$v$$$ $$$\leq$$$ $$$2^{30} - 1$$$).
Если $$$t$$$ = 2, то в строке содержится еще одно целое число $$$z$$$ ($$$0$$$ $$$\leq$$$ $$$z$$$ $$$\leq$$$ $$$2^{30} - 1$$$).
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся при прохождении всех тестов этой группы, а также при прохождении тестов необходимых подгрупп. Баллы за соответствующие группы указаны в таблице. Исключение составляют группы $$$1$$$ и $$$2$$$, которые оцениваются за каждый пройденный тест отдельно.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия |
| 1 | 10 | $$$n$$$, $$$q$$$ = $$$1$$$ и $$$a_{i}$$$, $$$z$$$, $$$v$$$ $$$\leq$$$ $$$2^{10} - 1$$$, все запросы второго типа | – | Потестовая оценка |
| 2 | 20 | $$$n$$$, $$$q$$$ $$$\leq$$$ $$$500$$$ и $$$a_{i}$$$, $$$z$$$, $$$v$$$ $$$\leq$$$ $$$2^{10} - 1$$$, во всех запросах первого типа $$$i$$$ $$$\leq$$$ $$$n$$$ | – | Потестовая оценка |
| 3 | 20 | $$$n$$$ $$$\leq$$$ $$$7000$$$ и $$$a_{i}$$$, $$$z$$$, $$$v$$$ $$$\leq$$$ $$$2^{10} - 1$$$, во всех запросах первого типа $$$i \le n$$$ | 0, 1, 2 | – |
| 4 | 20 | $$$n$$$ $$$\leq$$$ $$$7000$$$, $$$q$$$ $$$\leq$$$ $$$500$$$ | 0, 1, 2 | – |
| 5 | 30 | – | 0, 1, 2, 3, 4 | – |
34 2 421 1 12 8
8
62 0 2 5 7 452 132 02 112 282 29
8 0 8 24 24
Операция $$$or$$$ обозначает операцию побитового «ИЛИ».
Побитовое «ИЛИ» — бинарная операция, действие которой эквивалентно применению логического «ИЛИ» к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0, иначе двоичный разряд результата равен 1.
Разберем первый пример из условия. Изначально дана последовательность $$$[4, 2, 4]$$$, после первого запроса $$$a_1=1$$$ последовательность становится $$$[1, 2, 4]$$$. Поступает второй запрос $$$z=8$$$. Можно убедиться, что для всех $$$x$$$ от $$$0$$$ до $$$7$$$ выполняется $$$(1$$$ $$$or$$$ $$$2$$$ $$$or$$$ $$$4$$$ $$$or$$$ $$$x) \le 8$$$, а для всех $$$x \gt 7$$$ выполняется $$$(1$$$ $$$or$$$ $$$2$$$ $$$or$$$ $$$4$$$ $$$or$$$ $$$x) \gt 8$$$. Поэтому ответ на второй запрос равен $$$8$$$.