Среди открытого банка задач ЕГЭ по математике есть следующая: по заданным натуральным числам $$$l$$$, $$$r$$$ и $$$m$$$ вас просят найти целые числа $$$a$$$, $$$b$$$ и $$$c$$$, каждое из которых не меньше $$$l$$$ и не больше $$$r$$$, и такие, что будет существовать натуральное число $$$n$$$ (целое число, большее нуля) такое, что $$$n \cdot a + b - c = m$$$.
Паша еще только начал готовиться к ЕГЭ и не совсем понимает, как решать подобную задачу. Помогите ему для разных вариантов этой задачи находить подходящие $$$a$$$, $$$b$$$ и $$$c$$$.
В единственной строке заданы три целых числа $$$l$$$, $$$r$$$ и $$$m$$$ ($$$1 \leq l \leq r \leq 500\,000$$$, $$$1 \leq m \leq 10^{10}$$$).
Выведите три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ такие, что $$$l \leq a, b, c \leq r$$$ и существует такое натуральное число $$$n$$$, что $$$n \cdot a + b - c = m$$$. Гарантируется, что такие числа существуют. Если подходящих решений несколько, выведите любое из них.
В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$l, r, m \le 50$$$, наберут не менее $$$25$$$ баллов.
Решения, корректно работающие при $$$l, r, m \le 1000$$$, наберут не менее $$$55$$$ баллов.
4 6 13
4 6 5
2 3 1
2 2 3
В первом примере можно выбрать $$$n = 3$$$, тогда $$$n \cdot 4 + 6 - 5 = 13 = m$$$. Так же возможны такие ответы: $$$a = 4$$$, $$$b = 5$$$, $$$c = 4$$$ (при этом $$$n = 3$$$); $$$a = 5$$$, $$$b = 4$$$, $$$c = 6$$$ (при этом $$$n = 3$$$); $$$a = 6$$$, $$$b = 6$$$, $$$c = 5$$$ (при этом $$$n = 2$$$); $$$a = 6$$$, $$$b = 5$$$, $$$c = 4$$$ (при этом $$$n = 2$$$).
Во втором примере $$$n = 1$$$, тогда $$$n \cdot 2 + 2 - 3 = 1 = m$$$. Число $$$n = 0$$$ не могло быть выбрано, так как число $$$n$$$ обязательно должно быть натуральным.
Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из $$$n$$$ цветов.
Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов $$$m$$$ различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка $$$i$$$-го вида в букете его супруга становится счастливее на $$$a_i$$$, а от каждого следующего цветка такого вида она становится счастливее на $$$b_i$$$. То есть, если в букете $$$x_i \gt 0$$$ цветов вида $$$i$$$, то от цветов этого вида жена Володи становится счастливее на $$$a_i + (x_i - 1) \cdot b_i$$$.
Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета, набранного из доступных в магазине цветов.
В первой строке вводятся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le m \le 100\,000$$$) — требуемое количество цветов в букете и количество доступных видов цветов.
Каждая из следующих $$$m$$$ строк описывает $$$i$$$-й вид цветов и содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — увеличение счастья от первого цветка $$$i$$$-го вида и увеличение счастья от каждого последующего цветка этого вида.
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из $$$n$$$ цветов.
В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$n, m \le 7$$$ и $$$a_i \le b_i$$$, наберут не менее $$$8$$$ баллов.
Решения, корректно работающие при $$$n, m \le 7$$$, наберут не менее $$$20$$$ баллов.
Решения, корректно работающие при $$$n, m \le 1000$$$ и $$$a_i \le b_i$$$, наберут не менее $$$24$$$ баллов.
Решения, корректно работающие при $$$n, m \le 1000$$$, наберут не менее $$$60$$$ баллов.
Решения, корректно работающие при $$$a_i \le b_i$$$, наберут не менее $$$40$$$ баллов.
4 3 5 0 1 4 2 2
14
5 3 5 2 4 2 3 1
16
В первом примере если взять 1 цветок первого типа и 3 цветка второго типа, то итоговое увеличение счастья от букета будет равно $$$5 + 1 + 4 + 4 = 14$$$.
В втором примере если взять 2 цветка первого типа, 2 цветка второго типа и 1 цветок третьего типа, то итоговое увеличение счастья от букета будет равно $$$5 + 2 + 4 + 2 + 3 = 16$$$.
На планете Кирнес есть железнодорожный вокзал, с которого проложен железнодорожный путь до Сириуса. Этот путь активно используется товарными поездами, ходящими по одному и тому же ежедневному расписанию с одинаковой скоростью. К началу туристического сезона было решено запустить межпланетные электрички, следующие от вокзала до Сириуса. Электрички ходят по особому расписанию, которое надо согласовать с товарными поездами, поскольку железнодорожный путь является одноколейным.
Каждый день на планете Кирнес состоит из $$$h$$$ часов. Каждый час состоит из $$$m$$$ минут, причём $$$m$$$ обязательно чётное. Известно, что на данный момент $$$n$$$ товарных поездов отправляются с вокзала ежедневно по разу в день: $$$i$$$-й поезд отправляется в $$$h_i$$$ часов и $$$m_i$$$ минут.
Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны $$$\frac{m}{2}$$$ минутам. То есть для любой электрички предыдущая должна была отправиться ровно за $$$\frac{m}{2}$$$ минут до неё, а следующая должна отправиться ровно через $$$\frac{m}{2}$$$ минут после. Кроме этого, электричку надо подать на платформу за $$$k$$$ минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.
Поскольку электрички отправляются каждый день с интервалом в $$$\frac{m}{2}$$$ минут, то первая электричка отправится с вокзала в 0 часов и $$$t$$$ минут, причем $$$t \lt \frac{m}{2}$$$. Обратите внимание, что если $$$t \lt k$$$, то платформа вокзала будет занята и последние $$$k - t$$$ минут предыдущего дня.
Разумеется, не всегда можно составить корректное расписание электричек вместе со всеми товарными поездами. Тогда необходимо отменить некоторые товарные поезда, чтобы появилась возможность пустить электрички с соблюдением всех транспортных норм. При этом, чтобы грузоперевозчики не несли большие убытки, требуется отменить как можно меньше товарных поездов. Составление такого расписания оказалось трудной задачей для правительства планеты, поэтому это было поручено вам. Найдите такое время $$$t$$$ для запуска первой электрички, чтобы количество товарных поездов, которые потребуется отменить, было минимальным.
Первая строка содержит 4 целых числа $$$n$$$, $$$h$$$, $$$m$$$, $$$k$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le h \le 10^9$$$, $$$2 \le m \le 10^9$$$, $$$1 \le k \le \frac{m}{2}$$$) — число товарных поездов, количество часов и минут на планете Кирнес, а также время, которое электричка стоит у платформы. Гарантируется, что число минут $$$m$$$ четное.
В следующих $$$n$$$ строках вводится по два целых числа $$$h_i$$$ и $$$m_i$$$ ($$$0 \le h_i \lt h$$$, $$$0 \le m_i \lt m$$$) — время отправления $$$i$$$-го поезда, часы и минуты соответственно. Гарантируется, что все товарные поезда отправляются в разное время.
Выведите два числа: минимальное количество отмененных товарных поездов и $$$t$$$ — время запуска первой за день электрички в минутах.
Во второй строке через пробел выведите номера отменяемых товарных поездов.
В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Обозначим за $$$z$$$ минимальное количество отмененных товарных поездов.
Решения, корректно работающие при $$$n \leq 10,\ h \leq 24,\ m \leq 60$$$, $$$z = 0$$$, наберут не менее $$$8$$$ баллов.
Решения, корректно работающие при $$$n \leq 10,\ h \leq 24,\ m \leq 60$$$, наберут не менее $$$20$$$ баллов.
Решения, корректно работающие при $$$n \leq 1000$$$, $$$z = 0$$$, наберут не менее $$$24$$$ баллов.
Решения, корректно работающие при $$$n \leq 1000$$$, наберут не менее $$$60$$$ баллов.
Решения, корректно работающие при $$$z = 0$$$, наберут не менее $$$40$$$ баллов.
2 24 60 15 16 0 17 15
0 0
2 24 60 16 16 0 17 15
1 0 2
В первом примере первую электричку надо отправить в 0:00. Тогда поезд в 16:00 отправится сразу после электрички, а электричку в 17:30 надо будет подать на платформу сразу после отправления товарного поезда в 17:15.
Во втором примере подать электричку на платформу надо за 16 минут до отправления. Сделать это без отмены какого-то товарного поезда не получится: если отправлять электричку в $$$t \in [1, 15]$$$, то в 16:00 электричка уже должна быть на платформе, а с нее в это время отправляется первый товарный поезд. Если $$$t \in \{0, [16, 29]\}$$$, то второй товарный поезд в 17:15 не сможет уехать с платформы, потому что на ней уже будет стоять следующая электричка.
Если отменить второй поезд, то можно выбрать $$$t = 0$$$, тогда поезда будут отправляться в 0 и 30 минут каждый час, а столкновения с первым товарным поездом не будет. Также можно отменить только первый поезд и выбрать, например, $$$t = 13$$$.
Учёный Иван Иванович изучает перевёрнутые родословные. Перевёрнутая родословная представляет собой набор людей, про каждого из которых известны либо оба его родителя, либо не известен ни один родитель. Кроме того, известно, что у всех людей из родословной есть ровно один ребёнок, кроме одного человека, у которого детей вовсе нет. Поэтому, если пронумеровать людей целыми числами от $$$1$$$ до $$$n$$$, то можно обозначить за $$$s_i$$$ номер ребёнка человека с номером $$$i$$$ и сказать, что $$$s_i = 0$$$ в случае, если у человека с номером $$$i$$$ детей нет.
Будем считать, что человек $$$a$$$ входит в родословную человека $$$b$$$, если либо $$$a = b$$$, либо если у $$$b$$$ известны родители, и $$$a$$$ входит в родословную одного из родителей $$$b$$$.
Будем считать, что произошёл перекос родословной с участием некоторого человека, если известны оба его родителя и количество людей в родословной одного из его родителей хотя бы вдвое больше, чем количество людей в родословной второго родителя.
Иван Иванович посчитал количество перекосов родословной и получил число $$$k$$$, но, конечно же, он делал это вручную и мог ошибиться. Помогите проверить Ивану Ивановичу его вычисления: по числам $$$n$$$ и $$$k$$$ скажите, существует ли родословная из $$$n$$$ людей с $$$k$$$ перекосами, и если существует, то приведите пример подобной родословной.
В единственной строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 100\,000$$$, $$$0 \leq k \leq n$$$) — количество людей в родословной и количество перекосов в ней.
В первой строке выведите «YES» (без кавычек), если существует родословная с $$$n$$$ людьми и $$$k$$$ перекосами, и «NO» (без кавычек) в противном случае.
Если требуемая родословная существует, то во второй строке выведите $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \leq s_i \leq n$$$), задающих номера детей каждого из $$$n$$$ человек в родословной. Если искомых родословных несколько, выведите любую.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | $$$n$$$ | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 11 | $$$n \leq 10$$$ | |
| 2 | 19 | $$$n \leq 100$$$ | |
| 3 | 17 | $$$n \leq 300$$$ | |
| 4 | 22 | $$$n \leq 1000$$$ | |
| 5 | 31 | – |
3 0
YES 0 1 1
5 1
YES 0 1 1 3 3
3 2
NO
В первом примере подойдет единственная родословная, которую можно составить из трёх человек (человек и два его родителя).
Во втором примере подойдет следующая родословная:
В этом случае в родословную человека $$$1$$$ входят пять человек (люди $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$), в родословную человека $$$2$$$ входит один человек (только $$$2$$$), в родословную человека $$$3$$$ входят три человека ($$$3$$$, $$$4$$$, $$$5$$$), в родословную человека $$$4$$$ входит один человек (только $$$4$$$) и в родословную человека $$$5$$$ входит один человек (только $$$5$$$). В этом случае происходит перекос родословной в человеке $$$1$$$.
В третьем примере можно показать, что не существует родословной из трёх людей с двумя перекосами.
Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.
Игра происходит на шахматном поле размером $$$2n \times 2m$$$. Это поле имеет $$$2n$$$ строк и $$$2m$$$ столбцов. Для удобства будем обозначать как $$$(i, j)$$$ клетку поля, которая находится в $$$i$$$-й строке и $$$j$$$-м столбце. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка $$$(i, j)$$$ имеет белый цвет, если $$$i+j$$$ чётно, и чёрный цвет в противном случае.
Игра устроена следующим образом. Ильдар вырезает некоторые белые клетки поля. После этого он предлагает Ване попробовать решить следующую задачу: может ли он на не вырезанных белых клетках поля расставить $$$nm$$$ шахматных королей так, что никакие два выставленных короля не бьют друг друга, то есть не стоят на клетках поля, соседних по стороне или углу.
Конечно, Ильдар планирует сделать игру интересной и выставить несколько непростых для Вани комбинаций вырезанных клеток. Для этого он попросил у вас помощи. Чтобы перед игрой понять, как лучше всего действовать, он хочет потренироваться. Для этого, он берёт пустое поле и хочет $$$q$$$ раз либо вырезать какую-то белую клетку, либо вернуть на поле какую-то ранее вырезанную клетку. После каждого изменения он бы хотел знать, каким будет ответ на задачу для Вани.
Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.
В первой строке находится три целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m, q \leq 200\,000$$$) — количество пар строк шахматной доски, количество пар столбцов шахматной доски и количество запросов.
Следующие $$$q$$$ строк описывают запросы Ильдара. Каждая из этих строк содержит два целых числа $$$i$$$, $$$j$$$ ($$$1 \leq i \leq 2n$$$, $$$1 \leq j \leq 2m$$$, $$$i + j$$$ четно). Если клетка $$$(i, j)$$$ не вырезана, то Ильдар её вырезает, иначе он возвращает её обратно на поле.
Выведите $$$q$$$ строк. В $$$i$$$-й из этих строк выведите ответ на задачу для доски, полученной после $$$i$$$ первых запросов Ильдара.
Выведите «YES» (без кавычек), если Ваня может так расставить шахматных королей на не вырезанные белые клетки поля, что никакие два короля не будут бить друг друга. Иначе выведете «NO» (без кавычек).
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | ||||||
| Группа | Баллы | $$$n$$$ | $$$m$$$ | $$$q$$$ | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 10 | $$$n = 1$$$ | $$$m \leq 100$$$ | $$$q \leq 100$$$ | – | |
| 2 | 10 | $$$n \leq 3$$$ | $$$m \leq 3$$$ | $$$q \leq 20$$$ | 0 | |
| 3 | 15 | $$$n \leq 100$$$ | $$$m \leq 100$$$ | $$$q \leq 500$$$ | 0 – 2 | |
| 4 | 15 | $$$n \leq 3000$$$ | $$$m \leq 3000$$$ | $$$q \leq 3000$$$ | 0 – 3 | |
| 5 | 20 | – | – | – | – | Клетки не возвращаются |
| 6 | 30 | – | – | – | 0 – 5 | |
1 3 3 1 1 1 5 2 4
YES YES NO
3 2 10 4 2 6 4 1 3 4 2 6 4 2 2 2 4 1 3 4 4 3 1
YES YES NO NO YES YES NO YES YES NO
В первом примере, после второго запроса будут вырезаны клетки $$$(1, 1)$$$ и $$$(1, 5)$$$. Тогда Ваня может поставить три короля на клетки $$$(2, 2)$$$, $$$(2, 4)$$$ и $$$(2, 6)$$$.
После третьего запроса будут вырезаны клетки $$$(1, 1)$$$, $$$(1, 5)$$$ и $$$(2, 4)$$$. Тогда остаётся всего три пустые клетки $$$(2, 2)$$$, $$$(1, 3)$$$ и $$$(2, 6)$$$. Ваня не может поставить трех королей на эти клетки, потому что короли в клетках $$$(2, 2)$$$ и $$$(1, 3)$$$ бьют друг друга, так как эти клетки соседние по углу.