В этом году одна из школ запускает новую линейку командных олимпиад «ВКОШП-junior» для учеников 6-8 классов. Главная цель олимпиады — привлечение юных программистов и повышение интереса к олимпиадному движению. Тренеры стараются подобрать команды так, чтобы ребята чувствовали себя комфортно. Для этого сила любых двух участников команды должна отличаться не более чем на $$$с$$$ единиц силы. По правилам соревнования команды состоят из $$$k$$$ школьников. У тренера Славы на кружке $$$n$$$ школьников, пронумерованных числами от $$$1$$$ до $$$n$$$. Cила $$$i$$$-го школьника составляет $$$a_i$$$ единиц силы. Сколькими способами Слава может выбрать одну команду для участия во «ВКОШП-junior» с соблюдением вышеописанных условий?
Так как ответ может быть большим, выведите его остаток от деления на $$$10^9+7$$$.
В первой строке даны 3 целых числа $$$n$$$, $$$k$$$ и $$$c$$$ $$$(1 \le n \le 100\,000,\; 2 \le k \le n,\; 0 \le c \le 10^9)$$$ — число школьников, размер команды и значение максимального разброса силы соответственно.
Во второй строке даны целые числа $$$a_i$$$ $$$(0 \le a_i \le 10^9)$$$ — показатели силы школьников.
Выведите одно целое число — количество способов выбрать одну команду по модулю $$$10^9 + 7$$$.
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 10 & k = 2, n \le 2000 & \text {}\\ \hline 2 & 16 & k = 2 & \text {1}\\ \hline 3 & 31 & n \le 2\,000 & \text {1}\\ \hline 4 & 17 & k \le 5 & \text {1, 2} \\ \hline 5 & 26 & \text { Нет дополнительных ограничений } &\text {1, 2, 3, 4}\\ \hline \end{array}$$$$$$
6 2 5 10 2 7 9 1 4
9
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.
В саду есть $$$n$$$ рядов для посадки деревьев, в каждом из которых растет по $$$m$$$ яблонь. В сад хочет поселиться червячок Иннокентий, и он ищет лучшее место в саду для этого. Главным показателем при выборе яблони для будущего жилья червячок считает размер яблок, растущих на ней.
Изначально Иннокентий располагается в точке $$$(1, 1)$$$ (левой верхней точке сада). Из-за особенностей рельефа сада он может перемещаться только на соседнее дерево снизу или справа. При этом червячок может видеть размеры яблок только на соседних деревьях с тем, где он сейчас находится. Иннокентий не любит рисковать, и поэтому он переползёт на соседнее дерево только при условии, что яблоки на нём строго больше, чем на том, где он находится сейчас. При этом, если таких деревьев не существует, он поселится на текущем дереве. Иначе он переползёт на случайное из соседних деревьев, удовлетворяющих условиям.
Так как скоро зима, Иннокентий просит Вас помочь определить на каком максимальном количестве деревьев ему понадобиться побывать, чтобы найти себе жильё?
В первой строке даны два числа $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 1000)$$$ — количество рядов в саду и деревьев в каждом из них соответственно.
В следующих $$$n$$$ строках описываются ряды деревьев в саду. Таким образом, в $$$(i + 1)$$$-й строке $$$j$$$-е число описывает размер яблок $$$j$$$-го дерева в $$$i$$$-м ряду $$$a_{i, j}$$$ $$$(1 \le a_{i,j} \le 10^6)$$$.
В единственной строке выходного файла выведите одно число — максимально возможное количество деревьев, на которых может побывать Иннокентий, прежде чем найдет себе жилье.
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text {} \\ \hline 1 & 15 & \ a_{i,j} = i + j - 1 & \text {} \\ \hline 2 & 40 & \ 1 \le n, m \le 13 & \text {} \\ \hline 3 & 45 & \text { Нет дополнительных ограничений } & \text {1, 2}\\ \hline \end{array}$$$$$$
3 4 2 3 2 2 1 4 2 3 4 5 6 4
5
Тесты к этой задаче состоят из 3 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.
Главные Психологи Береляндии обеспокоились тем, что жители страны практически перестали друг с другом общаться. Так что они разработали программу поддержки социальной активности населения под названием «Банки дружбы». Программа включала в себя основание $$$n$$$ новых банков, имеющих разные ставки по вкладам: за год вложенные в банк деньги увеличиваются в $$$x$$$ раз.
Каждый житель страны изначально получал виртуальную сумму — 1 единицу денег, которую можно вложить в любой из банков. Через год он мог забрать все деньги из этого банка и положить в другой, более выгодный, или же снова положить деньги в этот банк. Забранные из банка и никуда не вложенные деньги сгорают.
Такие выгодные условия сразу привлекли огромное количество вкладчиков. Но банки выставили неимоверные требования по условию вклада: нужно было собрать множество документов, справок, подписей и т.п. В итоге, чтобы сделать выгодные вложения, люди сутками стояли в очередях в банке и заводили знакомства, что повысило социальную активность береляндцев (в этом, собственно, и заключалась задумка психологов).
Через несколько лет было проведено исследование с целью узнать насколько эффективна программа «Банки дружбы». Были опрошены $$$q$$$ пар знакомых друг другу бреляндцев, которых попросили назвать текущие суммы их вкладов. После этого для каждой пары узнали, могли ли эти берляндцы познакомиться, когда брали вклад в каком-то из банков. Попробуйте узнать и вы.
В первой строке вводится число $$$n$$$ $$$(1 \le n \le 100\,000)$$$ — количество банков.
На следующей строке даны $$$n$$$ чисел $$$a_i$$$ $$$(2 \le a_i \le 100\,000)$$$ — во сколько раз увеличивается за год количество денег в $$$i$$$-м банке.
В третьей строке вводится число $$$q$$$ $$$(1 \le q \le 50\,000)$$$ — количество пар опрошенных берляндцев.
В следующих $$$q$$$ строках дано по два числа $$$x_i$$$ и $$$y_i$$$ $$$(1 \le x_i, y_i \le 100\,000)$$$ — суммы на счетах соответствующих берляндцев.
Для каждой пары опрошенных берлянцев выведите «YES», если они могли познакомиться в очереди в банке, и «NO» в противном случае.
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 34 & 1 \le n, q \le 1000 & \text {}\\ \hline 2 & 31 & 1 \le n, a_i \le 1000 & \text {}\\ \hline 3 & 35 & \text { Нет дополнительных ограничений } & \text {1, 2}\\ \hline \end{array}$$$$$$
3 2 3 7 4 15 5 2 7 35 175 15 9
NO NO YES YES
Тесты к этой задаче состоят из 3 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.
Недавно вышла новая версия легендарной настольной игры «Колонизаторы»! Вы со своими друзьями, конечно же, не упустите шанс поиграть в новую игру.
Одной из основных механик игры является событие «Грабёж». Пусть сейчас играет $$$n$$$ человек, пронумерованных слева направо числами от $$$1$$$ до $$$n$$$. У $$$i$$$-го игрока в руке находятся $$$a_i$$$ карт. В момент, когда происходит событие «Грабёж», происходит следущее:
- Сначала все игроки одновременно выполняют действие: найти ближайшего игрока справа, у которого в руке больше карт, и отдать ему одну карту.
- Затем все игроки одновременно выполняют действие: найти ближайшего игрока слева, у которого в руке больше карт, и отдать ему одну карту.
Если у некоторого игрока нет необходимого соседа слева или справа, либо у него в руке нет ни одной карты, действие для данного игрока пропускается.
Вы с друзьями уже начали игру, и вот, внезапно, одно неаккуратное действие привело к событию «Грабёж». Выясните, какое максимальное количество карт в руке окажется у какого-то игрока после этого грабежа.
В первой строке записано целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — количество игроков.
Во второй строке через пробел записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — количество карт в руках игроков.
Выведите одно целое число — максимальное количество карт в руке после события «Грабёж».
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 42 & 1 \le n \le 100 & \text {}\\ \hline 2 & 58 & \text { Нет дополнительных ограничений } & \text {1}\\ \hline \end{array}$$$$$$
5 1 3 2 2 3
6
1 1
1
Рассмотрим первый пример.
Количество карт у игроков после первой фазы «Грабежа»: $$$0, 4, 1, 1, 5$$$.
Количество карт у игроков после второй фазы «Грабежа»: $$$0, 6, 0, 0, 5$$$.
Максимальное количество карт после «Грабежа» — $$$6$$$.
Во втором примере $$$n = 1$$$, поэтому единственный игрок никому не отдаст свои карты.
Тесты к этой задаче состоят из 2 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.
Саша очень любит настольные игры, особенно игру «Ticket to Ride». Сашины друзья однако не разделяют её энтузиазма, а больше всего им не нравится запоминать новые правила в очередном дополнении к игре.
Специально для таких случаев (когда никто не хочет запоминать сложные правила) Саша придумала свою собственную вариацию игры — правила в ней очень простые, а для игры нужны только карточки с разноцветными вагонами.
Скоро у Саши день рождения и она собирается позвать всех своих многочисленных друзей и устроить вечер игры в «Ticket to Ride» (точнее, в свою упрощённую версию игры). Однако у Саши есть проблема: каждому игроку потребуется по $$$a_i$$$ карточек каждого из $$$n$$$ цветов, а у неё их ограниченное число: всего $$$b_i$$$ штук. К счастью, дополнительно у Саши имеется ещё $$$k$$$ локомотивов — карт-джокеров, которые можно использовать вместо любого цвета.
Саша хочет позвать как можно больше своих друзей на день рождения, помогите ей понять, сколько человек сможет одновременно играть с ней в «Ticket to Ride».
В первой строке входных данных следуют два целых положительных числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 100\,000, 1 \le k \le 10^9)$$$ — число цветов и количество локомотивов.
Во второй строке следует последовательность $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, где $$$i$$$-е число равно числу карточек $$$i$$$-го цвета, необходимых для игры одному игроку.
В третьей строке следует последовательность $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le 10^9)$$$, где $$$i$$$-е число равно числу карточек $$$i$$$-го цвета в наличии у Саши.
Выведите одно целое число — сколько человек Саша может позвать на праздник (включая её саму).
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } &\text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 46 & n, k, a_i, b_i \le 1000 & \text {}\\ \hline 2 & 54 & \text { Нет дополнительных ограничений } & \text {1}\\ \hline \end{array}$$$$$$
3 1 2 1 4 11 3 16
4
4 3 4 3 5 6 11 12 14 20
3
Тесты к этой задаче состоят из 2 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.
Полумна Лавгут догадалась о планах отца выдать Гарри Поттера Пожирателям смерти и собирается предупретить его об этом, отправив письмо совиной почтой. Однако Полумна не знает, что на её перо наложено заклинание слежки, и как только она напишет хоть одно запрещённое слово (даже если оно просто будет являться подстрокой более длинного слова), об этом узнают Пожиратели смерти. Им потребуется $$$t$$$ секунд на сборы, после чего они сразу трансгрессируют к дому Полумны и арестуют её. Полумна пишет по $$$c$$$ символов в секунду. Узнайте, успеет ли она дописать и отправить свое сообщение Гарри до появления Пожирателей смерти.
В первой строке дана одна строка $$$s$$$ — текст сообщения Полумны. Текст состоит из строчных и заглавных букв латинского алфавита, цифр, пробелов и знаков препинания. Длина сообщения $$$|s|$$$ не превышает $$$100\,000$$$.
Во второй строке дано целое число $$$n$$$ $$$(1 \le n \le 100\,000)$$$ — число запрещённых слов. Далее даны сами запрещённые слова по одному на строке. Слова состоят из из строчных и заглавных букв латинского алфавита. Длина каждого слова не превосходит 10.
В последней строке даны два целых числа $$$t$$$ и $$$c$$$ $$$(1 \le t, c \le 100\,000)$$$ — время, необходимое Пожирателям на сборы и число символов, которое Полумна пишет за секуду соответственно.
Выведите «YES», если Полумна успеет отправить сообщение и «NO» иначе.
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 23 & |s|, n \le 100 & \text {}\\ \hline 2 & 36 & |s|, n \le 50\,000 & \text {1}\\ \hline 3 & 17 & \text { Все запрещённые слова имеют длину 10 } & \text {}\\ \hline 4 & 24 & \text { Нет дополнительных ограничений } & \text {1, 2, 3}\\ \hline \end{array}$$$$$$
Dear Harry. Evil Lord Voldemort wants to kill you. Best regards, Luna. 3 Voldemort pineapple pizza 2 10
NO
See you tomorrow 3 tom riddle voldemort 1 4
NO
See you tomorrow 3 tom riddle voldemort 1 5
YES
Тесты к этой задаче состоят из 4 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.
Один раз в год в городе Ч проводится день музеев для школьников. В музее советских игровых автоматов в этот день работало $$$k$$$ автоматов, время одной игры на каждом составляет $$$m$$$ минут. В одно и то же время на одном автомате не могут играть два человека.
Нам известно, что $$$n$$$ школьников заглядывали в этот день в музей: они записаны в протоколе в порядке прихода. Про каждого школьника $$$i$$$ нам известно время $$$x_i$$$, в которое он пришел в музей и время $$$y_i$$$, которое он был готов потратить на этот музей. Каждый школьник, заглянувший в музей, принимает решение: или ждать, когда освободится какой-нибудь автомат, после чего сыграть на нём одну игру, или же, если он не успевает сыграть в таких обстоятельствах, просто уйти.
В случае, когда два школьника претендуют на один и тот же автомат, преимущество имеет тот, кто стоит раньше в порядке протокола. Можете считать, что школьник $$$i$$$ может начать игру на автомате в тот же самый момент времени, когда последний школьник $$$j$$$, игравший на этом же автомате, закончил свою игру (то есть временем перехода к автомату и от него можно пренебречь).
Найдите число школьников, которым удастся поиграть в автомат.
В первой строке подается три числа — $$$n$$$, $$$k$$$ и $$$m$$$ $$$(1 \le n \lt 300\,000, 1 \le k, m \le 1000)$$$ — количество школьников в протоколе, количество автоматов, время игры на каждом автомате.
Следующие $$$n$$$ строк описывают протокол школьников. $$$i$$$-я из них содержит два числа — $$$x_i$$$ и $$$y_i$$$ $$$(0 \le x_i \le 1000, 1 \le y_i \le 1000)$$$ — время прихода и время ожидания школьника $$$i$$$. Протокол задан в порядке прихода школьников в музей.
Выведите одно число — количество школьников, которые поиграли в этот день в музее.
$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text {Тесты из условия} & \\ \hline 1 & 15 & n \lt k & \text {}\\ \hline 2 & 25 & k = 1 & \text {}\\ \hline 3 & 30 & n \le 1000 & \text {}\\ \hline 4 & 30 & \text { Нет дополнительных ограничений }& \text {1, 2, 3}\\ \hline \end{array}$$$$$$
5 2 10 1 12 1 5 1 20 10 16 11 10
4
Тесты к этой задаче состоят из 4 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.