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

Условие

В Берляндии в обиходе монеты достоинством 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 

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

Условие

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

Каждый месяц фонд получает 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

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

Условие

Перевозка пассажиров происходит по следующему алгоритму: автобус приходит на вокзал и ожидает пассажиров, пока они не займут все 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

Задача D. Унисон ≡

Условие

Два друга-ирландца Фаолан и Леон очень любят петь, особенно в праздники, когда они могут собраться и петь песни вместе. Хоть они и друзья, у них не так много общих песен, но это не мешает им пытаться петь разные песни одновременно.

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

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

Когда Фаолан и Леон поют, они следуют по текстам своих песен слева направо, сверху вниз, с удовольствием распевая в унисон совместимые строки и пропуская все остальные.

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

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

В первой строке входных данных содержатся целые числа N M: количество строк в первой и второй песне соответственно. Далее следуют N + M строк, содержащих текст первой и затем второй песни. Каждая строка может состоять только из печатных ASCII символов.

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

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

Ограничения

1 ≤ N, M ≤ 10⁶

N*M ≤ 10⁷

Длина каждой строки не превосходит 50.

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

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

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

3 4
It's funny how the war goes on
Without John, without our John
La la la la la, la la!
We're so young and so gone
Let's chase the dragon from our home
Ah ah from our home!
From our home

17