Задача A. Аквалангист ≡

Условие

Аквалангист Джонс находится в море в координате x_j, y_j на глубине h_j метров. Джонс заметил акулу, которая находится в координате x_s, y_s на глубине h_s метров. Акула тоже заметила Джонса.

Успеет ли Джонс выплыть вертикально вверх к поверхности со скоростью 1 м/с раньше, чем акула достигнет Джонса, если акула способна двигаться только параллельно осям координат со скоростью v_s м/с и приближается к нему по одному из кратчайших путей?

Если Джонс достиг поверхности одновременно с тем, как акула достигла Джонса, считается, что он не успел.

Формат входных данных

Входные данные содержат в двух строках целые числа x_j, y_j, h_j и x_s, y_s, h_s, v_s.

Формат выходных данных

Выходные данные должны содержать YES, если Джонс успеет выплыть и NO в ином случае.

Ограничения

0 ≤ |x_j|, |y_j|, h_j, |x_s|, |y_s|, h_s ≤ 10⁵

1 ≤ v_s ≤ 100

Примеры тестов

0 0 1
100 100 100 1

YES

0 0 1
0 0 2 2

NO

Задача B. Быки и коровы 2 ≡

Условие

На одномерном поле длиной N клеток пасутся быки и коровы. Каждая клетка либо пустая, либо занята быком, либо занята коровой.

На поле периодически нападают волки, поэтому пастухи решили оградить участок длиной h клеток.

Требуется написать программу, определяющую участок с наибольшим количеством коров. Если таких участков несколько, то нужно выбрать среди них участок с наибольшим количеством быков. Если и таких участков несколько, то нужно выбрать участок наиболее удалённый от краёв поля. Если же и таких участков несколько, то необходимо выбрать самый левый из них.

Формат входных данных

В первой строке входного файла заданы числа N, h. Далее идёт строка из N символов, где каждый символ — либо '.' (ASCII 46), что означает пустую клетку, либо 'X' (ASCII 88), обозначающий корову, либо 'Y' (ASCII 89), обозначающий быка.

Формат выходных данных

Выходные данные должны содержать два числа l, r — координаты самой левой и самой правой клеток отрезка. Клетки нумеруются с единицы.

Ограничения

1 ≤ N < 10⁵, 1 ≤ h ≤ N

Примеры тестов

15 5
XX...XXYYYXX.YY

6 10

Задача C. Жадная последовательность ≡

Условие

Дана последовательность из N целых чисел a_i. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.

Формат входного файла

Первая строка входного файла содержит целые числа N и M — количество элементов последовательности и количество операций.

Вторая строка входного файла содержит N целых чисел a_i — элементы последовательности.

Формат выходного файла

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 10⁵

 − 10⁴ ≤ a_i ≤ 10⁴

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

Примеры тестов

4 1
1 2 3 4

3 4 3

4 2
3 2 1 1

3 4

Задача D. Сбор справок ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая скажет, существует ли способ получить справки от всех чиновников

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

Формат входного файла

Формат выходного файла

Ограничения

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

4 3
1 2
1 3
3 4

YES

4 3
1 2
2 3
3 1

NO

Задача E. Flasks equalizing ≡

Условие

В лаборатории стоит необычная конструкция из N одинаковых цилиндрических сосудов, выстроенных в ряд.

В i-й сосуд налито a_i миллилитров жидкости.

За один шаг можно перелить любое количество жидкости из одного сосуда в одного или обоих его соседей слева и справа в любой пропорции. Количество жидкости во всех сосудах после каждого шага должно оставаться целочисленным.

Требуется написать программу, выполняющую минимально необходимое количество вышеописанных шагов, чтобы уравнять количество жидкости во всех сосудах.

Формат входного файла

Первая строка входного файла содержит целое число N.

Вторая строка содержит N целых чисел a_i. Гарантируется, что общее количество жидкости делится на N.

Формат выходного файла

Первая строка выходного файла должна содержать целое число S — минимальное число шагов.

Следующие S строк содержат по три целых числа I, L, R — индекс сосуда, начиная с 1, увеличение уровня в соседнем слева сосуде, увеличение уровня в соседнем справа сосуде соответственно.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ a_i ≤ 10⁹

Примеры тестов

5
7 7 1 5 5

2
2 0 4
1 0 2

5
7 6 1 5 6

4
2 0 3
4 1 0
1 0 2
5 1 0

Задача A. Улучшение успеваемости ≡

Условие

В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.

Примеры округления оценок приведены в таблице.

Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок. Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.

Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

Формат входных данных

Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c.

Примечание

Следует обратить внимание, что входные данные в этой и других задачах не помещаются в стандартный 32-битный тип данных. Необходимо использовать 64-битный тип данных (long long в С++, int64 в Паскале, long в Java).

Формат выходных данных

Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.

Ограничения

0 ≤ a, b, c ≤ 10¹⁵

a + b + c ≥ 1

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

2
0
0

2

Задача B. Призы ≡

Условие

Петр участвует в конкурсе, в котором разыгрывается N призов. Призы пронумерованы от 1 до N.

По итогам конкурса участник может набрать от 2 до N баллов. Если участник наберет K баллов, то он получит один из призов с номером от 1 до K.

Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов с номером от 1 до K. Затем участник может выбрать любой приз из оставшихся K − 1.

Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом a_i.

Требуется написать программу, которая по заданным ценностям призов определяет для каждого K от 2 до N, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе K баллов.

Формат входного файла

Первая строка входного файла содержит число N. Вторая строка этого файла содержит N целых чисел: a₁, a₂, …, a_N.

Формат выходного файла

Выходной файл должен содержать одну строку, содержащую N − 1 целых чисел: для каждого K от 2 до N должна быть выведена ценность приза, который достанется Петру, если он наберет K баллов.

Ограничения

2 ≤ N ≤ 100000; 1 ≤ a_i ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 1 (24 балла)

N ≤ 100

Подзадача 2 (24 балла)

N ≤ 5000

Подзадача 3 (52 балла)

N ≤ 100 000

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

5
1 3 4 2 5

1 3 3 4 

Задача C. Удаление чисел ≡

Условие

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

Необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса.

Например, пусть n = 13, k = 2.

• На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
• На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
• На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
• На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.

Формат входных данных

Первая строка входных данных содержит целое число n.

Вторая строка входных данных содержит целое число k.

Формат выходных данных

Требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Ограничения

3 ≤ n ≤ 10¹⁸

2 ≤ k ≤ 100, k < n

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

13
2

3

Задача D. Города ≡

Условие

Юный программист решил придумать собственную игру. Игра происходит на поле размером N×N клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.

Граница между государствами должна проходить по границам клеток таким образом, чтобы из любой клетки каждого государства существовал путь по клеткам этого же государства в любую другую его клетку (из клетки можно перейти в соседнюю, если они имеют общую сторону). Каждая клетка игрового поля должна принадлежать только одному из двух государств, при этом государства не обязаны состоять из одинакового количества клеток.

Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ N ≤ 50

Примеры тестов

3
DDD
DDC
DDC

111
111
112

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

11111
11111
12222
22222
22222

Задача E. Автоматизированное управление доставкой ≡

Условие

Группа программистов регионального сортировочного центра работает над автоматизацией управления доставкой почты.

Посылки принимаются в клиентских почтовых пунктах. Почтовый пункт принимает посылки, вес каждой из которых составляет целое число килограммов. Минимальный вес посылки равен 1 кг, а максимальный вес — k кг. Принятые посылки помещаются в специальный пакет.

Если после приема очередной посылки суммарный вес посылок в пакете больше или равен x кг, то пакет доставляется в муниципальный почтовый центр, где пакет с посылками перемещается в специальный контейнер.

Если после доставки очередного пакета суммарный вес посылок в контейнере больше или равен y кг, то контейнер перевозится в региональный сортировочный центр, откуда посылки уже доставляются получателям.

Суммарный вес посылок в контейнере при его перевозке может различаться в зависимости от массы принятых посылок. Необходимо выяснить, каким может быть минимальный суммарный вес посылок в контейнере при перевозке его из муниципального почтового центра в региональный сортировочный центр.

Требуется написать программу, которая по заданным значениям k — максимального веса посылки, x — необходимого веса пакета для его отправки в муниципальный почтовый центр, и y — необходимого веса контейнера для его отправки в региональный сортировочный центр, определяет минимальный вес контейнера при его перевозке.

Формат входного файла

Входной файл содержит три целых положительных числа, по одному на строке. Первая строка содержит число k. Вторая строка содержит число x. Третья строка содержит число y.

Формат выходного файла

Требуется вывести одно целое число — минимальный возможный вес контейнера при перевозке.

Ограничения

1 ≤ k, x, y ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примеру

В приведенном примере принимаются посылки весом 1 и 2 кг. При накоплении посылок с суммарным весом хотя бы в 7 кг пакет доставляется из клиентского почтового пункта в муниципальный почтовый центр. При накоплении посылок с суммарным весом хотя бы в 20 кг контейнер перевозится из муниципального почтового центра в региональный сортировочный центр.

Минимальный возможный вес контейнера в данном примере составляет 21 кг и достигается, например, следующим образом: в муниципальный почтовый центр последовательно доставляется 3 пакета по 7 кг каждый. Пакет весом 7 кг может получиться, например, после приема семи посылок по 1 кг.

Примеры тестов

2
7
20

21

Задача F. Кольцевая линия ≡

Условие

В городе, в котором живут друзья Андрей и Борис, метро состоит из единственной кольцевой линии, вдоль которой на равном расстоянии друг от друга расположены n станций, пронумерованных от 1 до n. Участок линии метро между двумя соседними станциями называется перегоном.

Поезда по кольцевой линии двигаются как по часовой стрелке, так и против часовой стрелки, поэтому чтобы добраться от одной станции до другой, пассажир может выбрать то направление, в котором требуется проехать меньше перегонов. Минимальное число перегонов, которое необходимо проехать, чтобы добраться от одной станции до другой, назовем расстоянием между станциями.

Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X и выписать для нее два числа: D_a — расстояние от станции, на которой живет Андрей, до станции X и D_b — расстояние от станции, на которой живет Борис, до станции X, то полученная пара чисел [D_a, D_b] будет однозначно задавать станцию X.

Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1] и станция 4 — парой [1, 2].

Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций A, B, таких что если Андрей живет на станции A, а Борис — на станции B, то выполняется описанное выше условие.

Требуется написать программу, которая по числу станций n на кольцевой линии определяет искомое количество вариантов.

Пояснения к примерам

В первом примере подходят следующие варианты:

• Андрей живет на станции 1, а Борис на станции 2;
• Андрей живет на станции 1, а Борис на станции 4;
• Андрей живет на станции 2, а Борис на станции 1;
• Андрей живет на станции 2, а Борис на станции 3;
• Андрей живет на станции 3, а Борис на станции 2;
• Андрей живет на станции 3, а Борис на станции 4;
• Андрей живет на станции 4, а Борис на станции 1;
• Андрей живет на станции 4, а Борис на станции 3.

Система оценки и описание подзадач

В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (25 баллов)

Подзадача 2 (25 баллов)

Подзадача 3 (50 баллов)

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Первая строка входного файла содержит одно целое число n.

Формат выходного файла

Выходной файл должен содержать одно число — искомое количество вариантов.

Ограничения

3 ≤ n ≤ 40 000;

Примеры тестов

4

8

5

20

Задача G. Крестьянин и чёрт ≡

Условие

Встретил крестьянин чёрта, и тот говорит ему: «Видишь мост через эту реку? Стоит тебе только перейти через этот мост — у тебя будет втрое больше денег, чем есть. Перейдёшь назад, опять станет втрое больше, чем было. И так каждый раз, как ты будешь переходить через мост».

 — Ой ли? — говорит крестьянин.

 — Верное слово! — уверяет чёрт. — Только чур, уговор! За то, что я тебе утраиваю деньги, ты, каждый раз перейдя через мост, будешь отдавать мне по X копеек. Иначе не согласен.

 — Ну, что же, это не беда! — говорит крестьянин. — Раз деньги будут утраиваться, так отчего же тебе X копеек каждый раз не дать?

Перешёл крестьянин через мост, посчитал деньги — и вправду, стало втрое больше, чем было. Отсчитал X копеек, бросил чёрту, перешёл снова.. После N-го перехода по мосту отсчитал крестьянин в N-й раз X копеек, бросил чёрту и понял, что не осталось у него ни копейки.

Сколько копеек было у крестьянина изначально?

Требуется написать программу, которая по количеству копеек, взятых чёртом за один переход по мосту, и количеству переходов определит изначальное количество копеек у крестьянина.

Формат входных данных

В первой строке ввода содержится целое число X — количество копеек, которые крестьянин будет отдавать чёрту.

Во второй строке содержится целое число N — сколько раз крестьянин смог пройти по мосту, прежде чем у него закончились копейки.

Формат выходных данных

Выведите единственное целое число K — изначальное количество копеек у крестьянина.

Ограничения

1 ≤ X ≤ 10⁹

1 ≤ N ≤ 18

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

Пояснения к примерам

В первом примере у крестьянина изначально было 5 копеек. После перехода по мосту копеек стало 15 и крестьянину пришлось их все отдать чёрту.

Примеры тестов

15
1

5

81
4

40

Задача H. Кондиционеры ≡

Условие

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна a_i ватт.

Администрации школы предоставили список из m различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе — кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.

Формат входного файла

Первая строка входного файла содержит одно целое число n — количество классов в школе.

Вторая строка содержит n целых чисел a_i — минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.

Третья строка содержит одно целое число m — количество предложенных моделей кондиционеров.

Далее, в каждой из m строк содержится пара целых чисел b_j и c_j — мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число — минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

Ограничения

1 ≤ n ≤ 50 000;

1 ≤ a_i ≤ 1000;

1 ≤ m ≤ 50 000

1 ≤ b_j ≤ 1000, 1 ≤ c_j ≤ 1000;

Примеры тестов

1
800
1
800 1000

1000

3
1 2 3
4
1 10
1 5
10 7
2 3

13

Задача I. Трёхцветник ≡

Условие

Куст трёхцветника в начале своего роста выглядит, как три ветки, направленные в разные стороны:

В начале очередного цикла цветения каждая ветка пускает два отростка в разные стороны. При этом, ветка продолжает свой рост. Отростки являются ветками, из которых в начале следующего цикла также начнут появляться новые отростки. Каждая ветка даёт отростки ровно один раз.

После первого и второго циклов цветения трёхцветник примет следующий вид:

Юному садоводу стало интересно узнать количество веток у куста трёхцветника после N циклов цветения.

Требуется написать программу, которая считывает количество циклов цветения, и вычисляет количество веток.

Формат входных данных

Первая строка содержит одно целое число N — количество циклов цветения.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ N ≤ 40

Описание системы оценивания

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

Примеры тестов

1

9

2

21

Задача Z. Сумма с перестановкой ≡

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

1. x получается перестановкой цифр числа a;
2. y получается перестановкой цифр числа b;
3. x и y не содержат лидирующих нулей;
4. x + y = c.

Формат входного файла

Входной файл содержит целые числа a b c.

Формат выходного файла

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 10⁹

Примеры тестов

12 31 25

YES
12 13

12 31 26

NO

Задача A. Цапли ≡

Условие

Петя и Маша пришли в зоопарк. Больше всего Пете понравились цапли. Он был поражен их способностью спать на одной ноге.

В вольере находятся несколько цапель. Некоторые из них стоят на двух ногах, некоторые - на одной. Когда цапля стоит на одной ноге, то другую ее ногу не видно. Петя пересчитал видимые ноги всех цапель, и у него получилось число a.

Через несколько минут к вольеру подошла Маша. За это время некоторые цапли могли поменять позу, поэтому Петя предложил ей заново пересчитать видимые ноги цапель. Когда Маша это сделала, у нее получилось число b.

Выйдя из зоопарка, Петя с Машей заинтересовались, сколько же всего цапель было в вольере. Вскоре ребята поняли, что однозначно определить это число можно не всегда. Теперь они хотят понять, какое минимальное и какое максимальное количество цапель могло быть в вольере.

Требуется написать программу, которая по заданным числам a и b выведет минимальное и максимальное количество цапель, которое могло быть в вольере.

Система оценивания

Правильные решения для тестов, в которых 1 ≤ a ≤ 1000, 1 ≤ b ≤ 1000, будут оцениваться из 50 баллов.

Пояснения к примеру

В приведенном примере возможны следующие варианты:

• В вольере две цапли. Когда Петя считал ноги, одна цапля стояла на двух ногах, а другая — на одной. Петя насчитал три ноги. Когда Маша считала ноги, обе цапли стояли на двух ногах, Маша насчитала четыре ноги.
• В вольере три цапли. Когда Петя считал ноги, все цапли стояли на одной ноге, Петя насчитал три ноги. Когда Маша считала ноги, одна цапля стояла на двух ногах, а еще две — на одной. Маша насчитала четыре ноги.

Формат входного файла

Входной файл содержит два целых числа a и b, разделенных ровно одним пробелом.

Формат выходного файла

Выведите в выходной файл два целых числа, разделенных пробелом - минимальное и максимальное число цапель, которое могло быть в вольере. Гарантируется, что хотя бы одно количество цапель соответствует условию задачи.

Ограничения

1 ≤ a, b ≤ 10⁹

Примеры тестов

3 4

2 3

Задача B. Круглый стол ≡

Условие

Возрождая древние традиции английских рыцарей, в одном городе члены школьного клуба любителей информатики каждую неделю собираются за круглым столом и обсуждают результаты последних соревнований.

Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении. Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того, кто с кем сидит рядом.

В клуб приходят на занятия m мальчиков и n девочек. Иван Петрович заметил, что мальчик активно участвует в обсуждении только тогда, когда непосредственно рядом с ним с обеих сторон от него сидят девочки, а девочка активно участвует в обсуждении только тогда, когда непосредственно рядом с ней с одной стороны от нее сидит мальчик, а с другой — девочка.

Желая сделать заседание клуба как можно более интересным, Иван Петрович решил разместить участников за круглым столом таким образом, чтобы как можно больше членов клуба приняло активное участие в обсуждении.

Требуется написать программу, которая по заданным числам m и n выведет такой способ размещения m мальчиков и n девочек за круглым столом, при котором максимальное количество членов клуба будет активно участвовать в обсуждении.

Пояснения к примерам

В первом примере все члены клуба примут активное участие в обсуждении.

Во втором примере мальчики примут активное участие в обсуждении, а девочки нет. В этом примере можно также разместить членов клуба следующим образом: «BBGG». В этом случае активное участие в обсуждении примут обе девочки, а мальчики — нет. Разместить всех так, чтобы три или четыре члена клуба приняли активное участие в обсуждении, нельзя.

Формат входного файла

Входной файл содержит два целых числа m и n, разделенных ровно одним пробелом.

Формат выходного файла

Выходной файл должен содержать строку с расположенными в некотором порядке m символами «B» (заглавная латинская буква) и n символами «G» (заглавная латинская буква). Символ «B» означает мальчика, а символ «G» — девочку.

Символы следует расположить в том порядке, в котором нужно разместить членов клуба вокруг стола. Соседние символы соответствуют членам клуба, которые сидят рядом. Рядом сидят также члены клуба, соответствующие первому и последнему символу выведенной строки.

Ограничения

0 ≤ m ≤ 1000; 0 ≤ n ≤ 1000; m + n ≥ 3

Примеры тестов

1 2

BGG

2 2

BGGB

Задача C. Поврежденный XML ≡

Условие

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки  <  (ASCII 60), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка  >  (ASCII 62). Примеры открывающих тегов:  < a > ,  < dog > .

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш / (ASCII 47), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов:  < /a > ,  < /dog > .

XML-строка называется корректной, если она может быть получена по следующим правилам:

• Пустая строка является корректной XML-строкой.
• Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
• Если A — корректная XML-строка, то строка  < X > A < /X > , получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

•  < a >  < /a > 
•  < a >  < ab >  < /ab >  < c >  < /c >  < /a > 
•  < a >  < /a >  < a >  < /a >  < a >  < /a > 

•  < a >  < /b > 
•  < a >  < b > 
•  < a >  < b >  < /a >  < /b > 

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Формат входного файла

Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Строка во входном файле заканчивается переводом строки.

Формат выходного файла

Выходной файл должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.

Ограничения

Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы  < ,  >  и /.

Примеры тестов

<a></b>

<b></b>

<a><aa>

<a></a>

<a><>a>

<a></a>

<a/</a>

<a></a>

Задача D. Игра с числами ≡

Условие

Сегодня на уроке математики Петя и Вася изучали понятие арифметической прогрессии. Арифметической прогрессией с разностью d называется последовательность чисел a₁, a₂, …, a_k, в которой разность между любыми двумя последовательными числами равна d. Например, последовательность 2, 5, 8, 11 является арифметической прогрессией с разностью 3.

После урока Петя и Вася придумали новую игру с числами. Игра проходит следующим образом.

В корзине находятся n фишек, на которых написаны различные целые числа a₁, a₂, …, a_n. По ходу игры игроки выкладывают фишки из корзины на стол. Петя и Вася делают ходы по очереди, первым ходит Петя. Ход состоит в том, что игрок берет одну фишку из корзины и выкладывает ее на стол. Игрок может сам решить, какую фишку взять. После этого он должен назвать целое число d такое, что все числа на выбранных к данному моменту фишках являются членами некоторой арифметической прогрессии с разностью d, не обязательно последовательными. Например, если на столе выложены фишки с числами 2, 8 и 11, то можно назвать число 3, поскольку эти числа являются членами приведенной в начале условия арифметической прогрессии с разностью 3.

Игрок проигрывает, если он не может сделать ход из-за отсутствия фишек в корзине или из-за того, что добавление любой фишки из корзины на стол приводит к тому, что он не сможет подобрать соответствующее число d.

Например, если в корзине имеются числа 2, 3, 5 и 7, то Петя может выиграть. Для этого ему необходимо первым ходом выложить на стол число 3. После первого хода у него много вариантов назвать число d, например он может назвать d = 3. Теперь у Васи два варианта хода.

• Вася может вторым ходом выложить фишку с числом 5 и назвать d = 2. Тогда Петя выкладывает фишку с числом 7, называя d = 2. На столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2. Вася не может ее выложить, поскольку после этого он не сможет назвать корректное число d. В этом случае Вася проигрывает.
• Вася может вторым ходом выложить фишку с числом 7 и также назвать, например, d = 2. Тогда Петя выкладывает фишку с числом 5, называя также d = 2. Вася снова попадает в ситуацию, когда на столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2, и он также проигрывает.

Заметим, что любой другой первый ход Пети приводит к его проигрышу. Если он выкладывает число 2, то Вася отвечает числом 7, и Петя не может выложить ни одной фишки. Если Петя выкладывает фишку с числом 5 или 7, то Вася выкладывает фишку с числом 2, и у Пети также нет допустимого хода.

Требуется написать программу, которая по заданному количеству фишек n и числам на фишках a₁, a₂, …, a_n определяет, сможет ли Петя выиграть вне зависимости от действий Васи, и находит все возможные первые ходы Пети, ведущие к выигрышу.

Пояснения к примерам

Первый пример рассматривается в тексте условия этой задачи. Во втором примере, какую бы фишку не выложил Петя первым ходом, Вася в ответ выкладывает другую фишку, и Петя не может сделать ход из-за отсутствия фишек в корзине.

Система оценивания

Правильные решения для тестов, в которых 1 ≤ n ≤ 15, будут оцениваться из 40 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n.

Вторая строка содержит n различных целых чисел a₁, a₂, …, a_n. Соседние числа разделены ровно одним пробелом.

Формат выходного файла

Первая строка выходного файла должна содержать число k — количество различных первых ходов, которые может сделать Петя, чтобы выиграть. Если Вася может выиграть вне зависимости от действий Пети, строка должна содержать цифру 0. Во второй строке должно содержаться k различных целых чисел — все выигрышные числа. Будем называть число выигрышным, если, выложив в качестве первого хода фишку, содержащую это число, Петя может выиграть вне зависимости от действий Васи. Соседние числа в строке должны быть разделены ровно одним пробелом.

Ограничения

1 ≤ n ≤ 200

d ≥ 2

1 ≤ a_i ≤ 10⁵

Примеры тестов

4
2 3 5 7

1
3

2
2 4

0

Задача A. Лифт ≡

Условие

В современном многоэтажном офисе крупной компании установлен новый лифт. В компании работает n сотрудников. Для проверки эффективности системы управления лифтом требуется провести моделирование его работы в конце рабочего дня, когда все сотрудники должны покинуть здание и спуститься на первый этаж.

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й сотрудник подходит к лифту в секунду t_i на этаже a_i, чтобы спуститься на первый этаж.

На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван, либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе с ним лифт могут ожидать и другие сотрудники.

В каждый момент времени не более одного вызова является активным.

Изначально лифт свободен и находится на первом этаже. Когда поступает первый вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если несколько вызовов поступает одновременно, активным становится вызов от сотрудника с меньшим номером.

Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один этаж в секунду.

При движении вниз лифт останавливается на тех этажах, с которых на момент проезда мимо этого этажа был сделан вызов. Все ожидающие лифт сотрудники заходят в него и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все люди выходят из лифта, а лифт ожидает следующего вызова.

Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов, активируется вызов, который поступил раньше других. Если несколько вызовов поступило одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает обслуживание описанным образом, пока все люди не окажутся на первом этаже.

Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду сначала люди подходят и вызывают лифт, а затем лифт выполняет свое действие (перемещается на соседний этаж, сажает или выпускает людей, принимает решение, на какой вызов отправиться).

Требуется написать программу, которая по описанию вызовов лифта для каждого сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных

Первая строка входных данных содержит целые числа n и m — количество людей, вызывающих лифт, и количество этажей в здании.

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых числа t_i и a_i — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на котором это происходит.

Формат выходных данных

Выходные данные должны содержать n целых чисел, для каждого сотрудника требуется вывести секунду, в которую он выйдет из лифта на первом этаже.

Ограничения

1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁹

1 ≤ t₁ ≤ t₂ ≤ ...  ≤ t_n ≤ 10⁹, 2 ≤ a_i ≤ m

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения к примерам

Использованные в пояснении к примеру обозначения

Примеры тестов

5 4
2 3
2 4
5 2
5 3
9 3

6
12
6
12
12

Задача B. Река ≡

Условие

Во Флатландии протекает богатая рыбой река Большой Флат. Много лет назад река была поделена между n рыболовными предприятиями, каждое из которых получило непрерывный отрезок реки. При этом i-е предприятие, если рассматривать их по порядку, начиная от истока, изначально получило отрезок реки длиной a_i.

С тех пор с рыболовными предприятиями во Флатландии k раз происходили различные события. Каждое из событий было одного из двух типов: банкротство некоторого предприятия или разделение некоторого предприятия на два.

При некоторых событиях отрезок реки, принадлежащий предприятию, с которым это событие происходит, делится на две части. Каждый такой отрезок имеет длину большую или равную 2. Деление происходит по следующему правилу. Если отрезок имеет четную длину, то он делится на две равные части. Иначе он делится на две части, длины которых различаются ровно на единицу, при этом часть, которая ближе к истоку реки, имеет меньшую длину.

При банкротстве предприятия происходит следующее. Отрезок реки, принадлежавший обанкротившемуся предприятию, переходит к его соседям. Если у обанкротившегося предприятия один сосед, то этому соседу целиком передается отрезок реки обанкротившегося предприятия. Если же соседей двое, то отрезок реки делится на две части описанным выше способом, после чего каждый из соседей присоединяет к своему отрезку ближайшую к нему часть.

При разделении предприятия отрезок реки, принадлежавший разделяемому предприятию, всегда делится на две части описанным выше способом. Разделившееся предприятие ликвидируется, и образуются два новых предприятия.

Таким образом, после каждого события каждое предприятие владеет некоторым отрезком реки.

Министерство финансов Флатландии предлагает ввести налог на рыболовные предприятия, пропорциональный квадрату длины отрезка реки, принадлежащего соответствующему предприятию. Чтобы проанализировать, как будет работать этот налог, министр хочет по имеющимся данным узнать, как изменялась величина, равная сумме квадратов длин отрезков реки, принадлежащих предприятиям, после каждого произошедшего события.

Требуется написать программу, которая по заданному начальному разделению реки между предприятиями и списку событий, происходивших с предприятиями, определит, чему равна сумма квадратов длин отрезков реки, принадлежащих предприятиям, в начальный момент времени и после каждого события.

Пояснения к примерам

Распределение отрезков реки между предприятиями после каждого события, описанного в примере, приведено на рисунке ниже.

Система оценивания и описание подзадач

В этой задаче четыре подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Внимание! Тест из примера не подходит под ограничение подзадачи 3. Тем не менее, решение задачи принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера, даже если участник претендует на правильное решение только этой подзадачи.

В первой строке каждого теста после числа n указан номер подзадачи, для теста из примера указано число 0, в тестах первой подзадачи указано число 1, и т. д.

Подзадача 1 (30 баллов)

2 ≤ n ≤ 100, 1 ≤ k ≤ 100, 1 ≤ a_i ≤ 100, p = 1.

Подзадача 2 (30 баллов)

2 ≤ n ≤ 100 000, 1 ≤ k ≤ 100 000, 1 ≤ a_i ≤ 10⁴, p = 2.

Для всех i от 1 до k − 1 выполнено условие: |v_i − v_i + 1| ≤ 10

Подзадача 3 (20 баллов)

2 ≤ n ≤ 100 000, 1 ≤ k ≤ 100 000, 1 ≤ a_i ≤ 10⁴, p = 3.

Все события имеют тип e_i = 1 (нет разделений предприятий, только банкротства).

Подзадача 4 (20 баллов)

2 ≤ n ≤ 100 000, 1 ≤ k ≤ 100 000, 1 ≤ a_i ≤ 10⁴, p = 4.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Первая строка входного файла содержит два целых числа: n и p — исходное количество предприятий и номер подзадачи.

Вторая строка входного файла содержит n целых чисел a₁, a₂, …, a_n — длины исходных отрезков реки.

Третья строка входного файла содержит целое число k — количество событий, происходивших с предприятиями.

Последующие k строк содержат описания событий, i-я строка содержит два целых числа: e_i и v_i — тип события и номер предприятия, с которым оно произошло. Значение e_i = 1 означает, что предприятие, которое после всех предыдущих событий является v_i-м по порядку, если считать с единицы от истока реки, обанкротилось, а значение e_i = 2 означает, что это предприятие разделилось на два.

Гарантируется, что значение v_i не превышает текущее количество предприятий. Гарантируется, что если отрезок предприятия при банкротстве или разделении требуется поделить на две части, то он имеет длину большую или равную 2. Гарантируется, что если на реке осталось единственное предприятие, оно не банкротится.

Формат выходного файла

Выходной файл должен содержать (k + 1) целых чисел, по одному в строке. Первая строка должна содержать исходную сумму квадратов длин отрезков реки, а каждая из последующих k строк — сумму квадратов длин отрезков реки после очередного события.

Ограничения

2 ≤ n ≤ 100 000, 0 ≤ p ≤ 4, 1 ≤ k ≤ 100 000, 1 ≤ a_i ≤ 10⁴.

Примеры тестов

4 0
3 5 5 4
5
1 1
2 1
1 3
2 2
1 3

75
105
73
101
83
113

Задача C. Интересные числа ≡

Условие

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 — интересные.

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 10⁹ + 7.

Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 10⁹ + 7.

Формат входного файла

Входной файл содержит две строки. Первая строка содержит число L, вторая строка содержит число R.

Формат выходного файла

Выходной файл должен одно целое число — остаток от деления количества интересных чисел, лежащих в диапазоне от L до R включительно, на 10⁹ + 7.

Ограничения

1 ≤ L ≤ R ≤ 10¹⁰⁰

Описание подзадач и системы оценивания

Подзадача 1 (21 балл)

L = 1, R ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (22 балла)

1 ≤ L ≤ R ≤ 10¹⁸.

В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (24 балла)

L = 1, R = 10^k для некоторого целого k, 2 ≤ k ≤ 100.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (33 балла)

1 ≤ L ≤ R ≤ 10¹⁰⁰.

В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

1
100

54

Задача D. Мониторинг труб ≡

Условие

Газораспределительная система одного региона устроена следующим образом. Она содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p₂, p₃, … , p_n. Для всех i от 2 до n узел с номером p_i соединен односторонней трубой с узлом i, газ по этой трубе передается от узла p_i к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до любого узла системы (возможно, с использованием промежуточных узлов). В системе используются трубы различных типов, тип трубы обозначается буквой английского алфавита от "a" до "z". Труба, соединяющая узел p_i с узлом i, имеет тип c_i.

Для проверки качества труб используется специальный робот. Он помещается в систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по которой он перемещается. Робот может перемещаться по трубам только в том же направлении, в котором по трубе передается газ. Совершив одно или несколько перемещений по трубам между узлами, робот извлекается из системы труб.

Каждый запуск робота должен соответствовать одной из m заданных спецификаций, пронумерованных от 1 до m. Спецификация с номером t представляет собой строку s_t, состоящую из строчных букв английского алфавита. Запуск соответствует спецификации s_t, если количество перемещений робота по трубам во время запуска совпадает с длиной s_t, и для всех j от 1 до длины s_t на j-м шаге робот перемещается по трубе, тип которой совпадает с s_t[j] — символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t, то стоимость этого запуска составляет w_t. Оператору системы необходимо проверить все трубы, для этого можно запускать робота несколько раз. Каждый раз выбирается спецификация и маршрут робота по трубам, соответствующий выбранной спецификации. Необходимо проверить все трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку спецификаций определяет минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены, а также, по требованию, список необходимых для этого запусков.

Формат входных данных

В первой строке входных данных находятся три целых числа n, m и t — количество узлов системы труб, количество спецификаций запусков робота и параметр, указывающий требуется ли вывести список запусков робота, или только их минимальную суммарную стоимость.

В последующих (n − 1) строках содержится информация о трубах, (i − 1)-я из этих строк содержит разделенные пробелом значения p_i и c_i, где p_i — целое число, задающее номер узла, из которого ведет труба в i-й узел, а c_i — строчная буква английского алфавита, задающая тип этой трубы.

В последующих m строках содержится информация о спецификациях, i-я из этих строк содержит разделенные пробелом целое число w_i — стоимость запуска робота в соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита строку s_i — саму спецификацию.

Формат выходных данных

Первая строка выходных данных должна содержать одно число — минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены. Если проверить все трубы невозможно, требуется вывести  − 1.

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний запусков робота. В этом случае вторая строка выходных данных должна содержать число k — количество запусков робота, которое необходимо выполнить для проверки труб. В следующих k строках необходимо вывести по три целых числа a_i, b_i и c_i — номер узла, в котором начинается запуск, номер узла, в котором заканчивается запуск, и номер спецификации, которой соответствует запуск.

Если оптимальных способов проверки несколько, требуется вывести любой из них.

Ограничения

1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, t равно 0 или 1

1 ≤ p_i ≤ i − 1

1 ≤ w_i ≤ 10⁹. Суммарная длина строк s_i не превышает 10⁶.

Пояснение к примеру

Система труб, заданная во втором примере входных данных, и оптимальный способ проверки всех труб для этого случая приведены на рисунке ниже.

Необходимо обратить внимание на следующие моменты:

• трубу можно проверять несколько раз, так в приведенном примере дважды проверена труба из узла 2 в узел 3;
• одну и ту же спецификацию разрешается использовать несколько раз, в приведенном примере вторая спецификация используется дважды, для проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
• робот может перемещаться по трубам только в том же направлении, по которому по трубе передается газ, спецификацию «ab» нельзя использовать для проверки труб по маршруту 2→1→6, так как робот не может переместиться из узла 2 в узел 1.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

3 3 0
1 a
2 b
3 a
4 b
2 a

6

7 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab

15
4
1 4 1
1 6 2
6 7 2
2 5 3

Задача E. Полезные ископаемые ≡

Условие

Ведется проект по освоению планеты соседней звездной системы. Для добычи полезных ископаемых планируется направить на планету несколько партий роботов.

Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером w на h, клетки участка имеют координаты от (1, 1) до (w, h). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено s баз, и i-я база находится в клетке с координатами (x_i, y_i).

Каждая партия роботов характеризуется тремя параметрами: j-я партия доставляется на базу b_j, содержит n_j роботов и каждый робот партии обладает мобильностью m_j.

Когда партия роботов доставляется на соответствующую базу, каждый робот этой партии перемещается по поверхности планеты от базы до некоторой клетки. Если мобильность робота равна m, он может не более m раз переместиться на одну из восьми соседних клеток, как показано на рис. 1.

Рис. 1. Возможные перемещения робота в восьми направлениях.

После того как роботы из всех доставленных партий размещаются на участке, они активируются и начинают добычу полезных ископаемых. В процессе перемещения в одной клетке может одновременно находиться произвольное количество роботов. Однако после активации в каждой клетке должно находиться не более q роботов.

Руководством проекта получена информация о t партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше q роботов. Поэтому руководство должно выбрать k первых партий роботов, где 0 ≤ k ≤ t, которые будут полностью доставлены на соответствующие базы. После этого, если k < t, следует дополнительно принять z из n_k + 1 роботов следующей, (k + 1)-й партии, 0 ≤ z < n_k + 1.

Все полученные таким образом роботы должны с учетом ограничения на мобильность разместиться на участке таким образом, чтобы в каждой клетке было не более q роботов. После этого они будут активированы и начнут добычу полезных ископаемых. Разумеется, руководство проекта старается максимизировать количество роботов, которые будут доставлены на планету, поэтому, с учетом описанных ограничений, требуется максимизировать k, а затем максимизировать z.

Требуется написать программу, которая по размерам участка, числу q, описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число k — количество партий роботов, и затем – максимальное число z – дополнительное количество роботов из (k + 1)-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более q роботов.

Формат входного файла

Первая строка входного файла содержит числа w, h, s и q. Последующие s строк содержат по два целых числа x_i, y_i и описывают базы специалистов (1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h).

Следующая строка содержит число t — количество партий роботов. Последующие t строк описывают партии роботов и содержат по 3 целых числа: b_j, n_j и m_j (1 ≤ b_j ≤ s, 1 ≤ n_j ≤ w × h × q, 0 ≤ m_j < max(w, h)).

Формат выходного файла

Требуется вывести два числа: k и z, 0 ≤ k ≤ t. Если k = t, то z должно быть равно 0, иначе должно выполняться условие 0 ≤ z < n_k + 1.

Ограничения

1 ≤ w, h ≤ 10⁵, 1 ≤ s ≤ 4, 1 ≤ q ≤ 100, 1 ≤ t ≤ 100,

Пояснение к примеру

В приведенном примере описания входных данных следует полностью принять первую партию роботов и дополнительно принять 7 роботов из второй партии. На рис. 2 показано, как можно разместить этих роботов на участке, чтобы в каждой клетке было не более одного робота. Базы специалистов показаны кружками. Клетки, в которых окажутся роботы с базы 1, показаны вертикальной штриховкой, а клетки, в которых окажутся роботы с базы 2, показаны серым цветом.

Рис. 2. Возможное размещение роботов на участке в данном примере.

Описание подзадач и системы оценивания

Баллы за каждую из подзадач 1–5 начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Тесты для подзадачи 6 запускаются только в случае, если все тесты подзадач 1–5 успешно пройдены. Каждый тест в подзадаче 6 оценивается независимо в 1 балл.

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

Примеры тестов

4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2

1 7

Задача F. Поездка на каникулах ≡

Условие

Железная дорога Флатландии представляет собой прямую, вдоль которой расположены N станций. Будем называть участок железной дороги от некоторой станции до следующей перегоном.

Поезд следует от станции 1 до станции N, делая остановку на каждой станции. В поезде K мест, пронумерованных от 1 до K. На поезд продаются билеты, каждый билет характеризуется тремя числами: S, T и A. Такой билет позволяет проехать от станции S до станции T на месте A.

Иван планирует в один из дней летних каникул проехать на поезде от одной станции до другой. Он выяснил, что на поезд в этот день уже продано M билетов, и возможно уже нет мест, свободных на всех перегонах между интересующими его станциями. Билет от одной станции до другой на определенное место можно купить, только если это место свободно на всех перегонах между этими станциями.

Иван сообразил, что иногда все равно можно проехать от одной станции до другой, купив несколько билетов и пересаживаясь с одного места на другое на некоторых промежуточных станциях. Разумеется, пересаживаться с места на место неудобно, поэтому Иван хочет купить минимальное количество билетов, чтобы на каждом перегоне у него было свое место.

Иван еще не решил, от какой станции и до какой он поедет. Он записал Q вариантов поездки, и для каждого из них хочет узнать, какое минимальное число билетов ему придется купить, если он выберет этот вариант.

Требуется написать программу, которая по заданному описанию уже проданных билетов и вариантов поездки Ивана определяет для каждого варианта, какое минимальное количество билетов необходимо купить, чтобы совершить такую поездку.

Формат входного файла

Первая строка входного файла содержит числа N, M и K — количество станций, количество уже проданных билетов и количество мест в поезде. Последующие M строк содержат информацию о проданных билетах.

Каждая строка содержит три числа: s_i, t_i и a_i — номер станции, от которой куплен билет, номер станции, до которой куплен билет, и номер места, на которое куплен билет.

Гарантируется, что все билеты куплены таким образом, что ни на каком перегоне ни на какое место нет более одного билета.

Далее идет строка, которая содержит число Q. Последующие Q строк содержат описания вариантов поездки. Каждая строка содержит два числа: f_j, d_j — номер станции, от которой Иван хочет поехать в этом варианте, и номер станции, до которой он хочет поехать.

Формат выходного файла

Выходной файл должен содержать Q чисел: для каждого варианта поездки требуется вывести минимальное количество билетов, которое необходимо купить Ивану, чтобы совершить соответствующую поездку. Если поездку совершить невозможно, то для этого варианта требуется вывести  − 1.

Ограничения

2 ≤ N ≤ 200 000; 0 ≤ M ≤ 200 000, 1 ≤ K ≤ 200 000

1 ≤ s_i < t_i ≤ N; 1 ≤ a_i ≤ K

1 ≤ Q ≤ 200 000; 1 ≤ f_j < d_j ≤ N

Система оценки и описание подзадач

В этой задаче три подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 2, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 1 и 2.

Подзадача 1 (33 баллов)

N ≤ 100; M ≤ 100; K ≤ 100, Q = 1

Подзадача 2 (30 баллов)

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q = 1

Подзадача 3 (37 баллов)

N ≤ 200 000; M ≤ 200 000; K ≤ 200 000; Q ≤ 200 000

Получение информации о результатах окончательной проверки

По запросу сообщаются баллы за каждую подзадачу.

Пояснение к примеру

На перегоне от 2-й до 3-й станции все места заняты, поэтому проехать от 1-й до 5-й станции невозможно. От 3-й до 5-й станции можно проехать, используя два билета: от 3-й до 4-й станции на место 2 и от 4-й до 5-й на место 1. От 4-й до 5-й станции можно проехать, используя один билет на место 1.

Примеры тестов

5 4 3
1 4 1
2 5 3
2 3 2
4 5 2
3
1 5
3 5
4 5

-1
2
1

Задача A. Кампус ≡

Условие

Новое здание кампуса Университета Байтбурга имеет n этажей, пронумерованных снизу вверх от 1 до n. Комнаты студентов расположены в нескольких подъездах.

В каждом подъезде на этажах, номер которых кратен числу k, расположено по x комнат, а на остальных этажах расположено по y комнат.

Комнаты внутри каждого подъезда пронумерованы последовательными натуральными числами. Номера комнат на первом этаже имеют наименьшие значения в этом подъезде, затем следуют номера комнат на втором этаже, и так далее. Комнаты в первом подъезде пронумерованы, начиная с 1, в каждом следующем подъезде нумерация комнат начинается с числа, следующего после максимального номера комнаты в предыдущем подъезде.

На рис.1 показаны номера комнат в здании с n = 7 этажами, 3 подъездами, и параметрами k = 3, x = 2, y = 3.

Для организации расселения студентов администрация кампуса должна по номеру комнаты оперативно определять этаж, на котором она находится.

Требуется написать программу, которая по заданным числам n, k, x и y, а также по номерам комнат, определяет для каждой комнаты, на каком этаже она находится.

Формат входного файла

Первая строка входного файла содержит натуральные числа n, k, x и y. Соседние числа разделены ровно одним пробелом.

Вторая строка входного файла содержит натуральное число q  — количество номеров комнат, для которых требуется определить этаж.

Третья строка содержит q целых чисел a₁, a₂, ..., a_q  — номера комнат. Можно считать, что в здании так много подъездов, что все комнаты с заданными номерами существуют.

Формат выходного файла

Требуется вывести q чисел, по одному на строке. Для каждого номера комнаты во входном файле требуется вывести номер этажа, на котором она находится.

Ограничения

1 ≤ n ≤ 10⁹, 1 ≤ x, y ≤ 10⁹, 1 ≤ q ≤ 1000, 1 ≤ a_i ≤ 10¹⁸

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

7 3 2 3
4
1 19 20 50

1
7
1
5

Задача B. Призы ≡

Условие

Петр участвует в конкурсе, в котором разыгрывается N призов. Призы пронумерованы от 1 до N.

По итогам конкурса участник может набрать от 2 до N баллов. Если участник наберет K баллов, то он получит один из призов с номером от 1 до K.

Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов с номером от 1 до K. Затем участник может выбрать любой приз из оставшихся K − 1.

Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом a_i.

Требуется написать программу, которая по заданным ценностям призов определяет для каждого K от 2 до N, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе K баллов.

Формат входного файла

Первая строка входного файла содержит число N. Вторая строка этого файла содержит N целых чисел: a₁, a₂, …, a_N.

Формат выходного файла

Выходной файл должен содержать одну строку, содержащую N − 1 целых чисел: для каждого K от 2 до N должна быть выведена ценность приза, который достанется Петру, если он наберет K баллов.

Ограничения

2 ≤ N ≤ 100000; 1 ≤ a_i ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 1 (24 балла)

N ≤ 100

Подзадача 2 (24 балла)

N ≤ 5000

Подзадача 3 (52 балла)

N ≤ 100 000

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

5
1 3 4 2 5

1 3 3 4 

Задача C. Выбор зала ≡

Условие

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом.

Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от A до B квадратных метров, включительно.

Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от C до D метров, включительно.

Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами Y × Z и Z × Y считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям.

Требуется написать программу, которая по заданным A, B, C и D определяет количество различных залов, площадь которых находится в пределах от A до B, а периметр — от C до D, включительно.

Пояснения к примеру

В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2.

Система оценки и описание подзадач

Подзадача 1 (50 баллов)

1 ≤ A ≤ B ≤ 1000, 4 ≤ C ≤ D ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (50 баллов)

1 ≤ A ≤ B ≤ 10⁹, 4 ≤ C ≤ D ≤ 10⁹.

В этой подзадаче 25 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Входной файл содержит четыре разделенных пробелами целых числа: A, B, C и D.

Формат выходного файла

Выходной файл должен содержать одно число — искомое количество залов.

Ограничения

1 ≤ A ≤ B ≤ 10⁹, 4 ≤ C ≤ D ≤ 10⁹

Примеры тестов

2 10 4 8

3

Задача D. Космическое поселение ≡

Условие

Для освоения Марса требуется построить исследовательскую базу. База должна состоять из N одинаковых модулей.

Каждый модуль представляет собой жилой отсек, который в основании имеет форму прямоугольника размером A × B метров.

Для повышения надежности модулей инженеры могут добавить вокруг каждого модуля дополнительный защитный слой. Толщина этого слоя должна составлять целое число метров, и все модули должны иметь одинаковую толщину защитного слоя.

Модуль с защитным слоем, толщина которой равна D метрам, будет иметь в основании форму прямоугольника размером (A + 2 D) × (B + 2 D) метров.

Все модули должны быть расположены на заранее подготовленном прямоугольном поле размером W × H метров.

При этом они должны быть организованы в виде регулярной сетки, их стороны должны быть параллельны сторонам поля, и модули должны быть ориентированы одинаково.

Требуется написать программу, которая по заданным количеству и размеру модулей, а также размеру поля для их размещения, определяет максимальную толщину дополнительного защитного слоя, который можно добавить к каждому модулю.

Пояснения к примеру

В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле — размер 6 × 6 метров.

Добавить дополнительный защитный слой к модулю нельзя.

Формат входного файла

Входной файл содержит пять разделенных пробелами целых чисел: N, A, B, W, H.

Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.

Формат выходного файла

Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя.

Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Ограничения

1 ≤ N, A, B, W, H ≤ 10¹⁸

Система оценки и описание подзадач

Подзадача 1 (26 баллов)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (23 балла)

1 ≤ N ≤ 1000; 1 ≤ A, B, W, H ≤ 10⁹.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (24 балла)

1 ≤ N ≤ 10⁹; 1 ≤ A, B, W, H ≤ 10¹⁸.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (27 баллов)

1 ≤ N ≤ 10¹⁸; 1 ≤ A, B, W, H ≤ 10¹⁸.

В этой подзадаче 9 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

11 2 3 21 25

2

1 5 5 6 6

0

Задача E. Призы ≡

Условие

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

Алиса хорошо знает Боба, и для каждого приза выяснила его ценность для Боба, которая является целым положительным числом. Алиса обижена на Боба и хочет выбрать свои призы так, чтобы суммарная ценность призов, которые достанутся Бобу, была как можно меньше. При этом Алису не волнует, какие призы достанутся ей.

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Пояснения к примерам

В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

Система оценивания и описание подзадач

В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (30 баллов)

3 ≤ n ≤ 50, 1 ≤ a_i ≤ 10⁵.

Подзадача 2 (30 баллов)

3 ≤ n ≤ 5000, 1 ≤ a_i ≤ 10⁵.

Подзадача 3 (40 баллов)

3 ≤ n ≤ 100 000, 1 ≤ a_i ≤ 10⁹.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей.

Вторая строка содержит n целых положительных чисел: a₁, a₂, …, a_n. Для каждого приза указана его ценность для Боба.

Формат выходного файла

Выходной файл должен содержать одно число — минимальное значение x, для которого Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Ограничения

3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3, 1 ≤ a_i ≤ 10⁹.

Примеры тестов

10 2
1 2 4 5 2 4 2 2 1 6

7

Задача F. Старая книга ≡

Условие

Группа юных археологов работает на раскопках здания древней библиотеки. Летом они обнаружили остатки старой книги и, изучив их, сделали следующие выводы.

Книга содержит несколько страниц, каждая страница содержит либо текст, либо иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма номеров страниц с текстом равна s.

К сожалению, ни общее количество страниц в книге, ни количество иллюстраций установить не удалось. Тем не менее, юных археологов заинтересовал вопрос, какое минимальное количество иллюстраций могло быть в книге.

Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание (буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая иллюстрацию):

• И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;
• И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;
• И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.

Минимальное количество иллюстраций равно 3.

Требуется написать программу, которая по заданным целым числам k и s определяет минимальное количество иллюстраций, которое могло быть в книге.

Формат входных данных

Первая строка входных данных содержит целое число k.

Вторая строка входных данных содержит целое число s.

Формат выходных данных

Требуется вывести одно целое число — минимальное количество иллюстраций в книге.

Ограничения

0 ≤ k ≤ 10⁹

k + 1 ≤ s ≤ 10¹²

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

1
8

3

Задача G. Вырубка леса ≡

Условие

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2 K-й, 3 K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2 M-й, 3 M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле.

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

• 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
• 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
• 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
• 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
• 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
• 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
• 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3.

Система оценивания и описание подзадач

Подзадача 1 (32 баллов)

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (10 баллов)

1 ≤ X ≤ 10¹⁸; X < K; X < M.

При решении этой подзадачи можно считать, что лесорубы не отдыхают. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (10 баллов)

1 ≤ X ≤ 10¹⁸.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 10¹⁸, 1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

Формат выходного файла

Выходной файл должен содержать одно целое число — искомое количество дней.

Ограничения

1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸, 1 ≤ X ≤ 10¹⁸

Примеры тестов

2 4 3 3 25

7