Задача A. Шпион ≡

Условие

Шпион проник во вражескую организацию, получил доступ к Главному Компьютеру (ГК), вставил в него диск, и в момент времени t₀ = 0 начал выкачивать Важные Данные (ВД). ВД выкачиваются со скоростью 1 ГБ/сек.

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

Задача шпиона состоит в том, чтобы загрузить максимальное количество ВД, безопасно извлечь накопитель из ГК и покинуть КГК незамеченным. При этом необходимо покинуть КГК раньше, чем его посетит большой патруль, который появится в момент времени B. Безопасное извлечение накопителя занимает D секунд. В это время ВД не загружаются, а шпион может быть замечен патрулём, поэтому эту операцию нужно производить, когда патруля нет поблизости.

Ваша задача состоит в том, чтобы вычислить, какое максимальное количество ГБ ВД может получить шпион, или определить, что миссия невыполнима.

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

Входные данные содержат 4 целых числа T, A, B, D, каждое в отдельной строке.

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

Ответ должен содержать одно целое число: максимальное количество Важных Данных, в ГБ. В случае, если миссия невыполнима, необходимо вывести -1.

Ограничения

1 ≤ A, B, D, T ≤ 10⁴

A < T

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

4
3
10
1

7

4
1
11
2

9

Задача B. Самая высокая стопка монет на всём Дальнем Востоке ≡

Условие

В Берляндии в обиходе монеты достоинством 1, 2, 3, 4, 5 и 6 бурлей, толщина всех монет одинаковая. У Васи есть неограниченное количество монет каждого достоинства. Вася и Петя играют в следующую игру: Петя загадывает сумму S, которую необходимо набрать, и сообщает Васе число N -- количество монет, которые Вася может использовать. После этого Вася должен подобрать такие N монет, чтобы их сумма равнялась ровно S бурлям. Далее все N монет раскладываются в 6 стопок по номиналам.

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

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

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

Выходной файл должен содержать M строк по 6 цифр ~--- количество монет в каждой стопке.

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

1
30 6

0 0 0 0 6 0 

Задача C. Деревья Илона Маска ≡

Условие

Девочка Саша устроилась волонтёром в благотворительный фонд Илона Маска, который занимается посадкой деревьев.

Каждый месяц фонд получает M денежных средств, которые тратит на посадку и заботу об уже посаженных деревьях. Все не потраченные деньги изымаются в конце месяца. В самом начале посадка дерева стоит K денег, но из-за кризиса стоимость растёт на P каждый месяц. Обслуживание каждого посаженного дерева стоит L денег в месяц, при этом стоимость обслуживания уменьшается ежемесячно после первого на R, пока не достигнет нуля. В первый раз дерево обслуживается на следующий месяц после посадки, т.е. стоимость обслуживания дерева в первый месяц L, во второй L−R, потом L−2∗R и так далее. Стоимость обслуживания дерева зависит от времени, когда оно было посажено.

Цель фонда —- посадить (но не обязательно вырастить) T деревьев. Это означает, что допустимо в последний месяц высадить столько деревьев, что денег в следующий месяц не хватит на обслуживание деревьев, но до момента, пока все деревья не высажены, нельзя тратить больше, чем M денег в месяц. Саше поручили написать программу, которая рассчитает минимальное количество месяцев, которое понадобится для достижения цели. Саша попросила вас помочь ей с этим.

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

Входные данные содержат число M -- ежемесячное количество выделяемых денежных средств, K -- стоимость посадки дерева, P -- на сколько увеличится стоимость посадки, L -- стоимость обслуживания дерева, R -- на сколько уменьшится стоимость обслуживания, T -- требуемое количество деревьев.

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

Выходные данные должны содержать одно целое число: минимальное количество месяцев, которое требуется для посадки T деревьев. В случае, если высадить деревья невозможно выведите −1.

Ограничения

1 ≤ M, T, L, K ≤ 10⁴

1 ≤ P, R ≤ 10²

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

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

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

100 5 1 4 1 40

6

Задача D. Автобусы ≡

Условие

Перевозка пассажиров происходит по следующему алгоритму: автобус приходит на вокзал и ожидает пассажиров, пока они не займут все M мест. Новый автобус приходит на вокзал каждые d минут, первый автобус приезжает в момент времени 0. Время ожидания пассажира ~--- это время, пока он стоит на остановке (если автобус стоит на остановке, а пассажир находится в нём, это не считается за ожидание).

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

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

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

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

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

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

Ограничения

0 ≤ N, M ≤ 10⁶; 1 ≤ t_i ≤ 10⁶; 1 ≤ T ≤ 10⁹

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

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

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

5 3 3
5 4 3 2 1

6

6 3 6
6 6 6 6 6 6

8