Все ваши материалы направляйте с таким расчетом, чтобы
они были получены в понедельник - 28 февраля. Проверка материалов,
полученных позже этого срока, не проводится. Материалы следующего занятия будут
высланы 28 февраля.
Задача M.
"Детский праздник" (20 баллов)
Организаторы детского праздника планируют надуть для
него m воздушных шариков. С этой целью они пригласили n
добровольных помощников, i-й среди которых надувает шарик за t-i
минут, однако каждый раз после надувания zi шариков устает и
отдыхает yi минут. Если помощник надул шарик и должен
отдохнуть, но больше шариков ему надувать не придется, то считается, что он
закончил работу сразу после окончания надувания последнего шарика, а не после
отдыха.
Требуется
написать программу, которая определит, через какое время будут надуты шарики
при наиболее оптимальной работе помощников и сколько шариков надует каждый из
них.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один
тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в первой
строке числа m и n (0£m£1000, 0£n£20). Следующие n строк содержат по три целых
числа - ti, z-i и yi соответственно (1£ti,
yi£100, 1£zi£1000).
Формат выходных данных:
В выходной текстовый
файл OUTPUT.TXT записывается в первой строке число t - время, за которое
будут надуты все шарики. Во вторую строку записывается n чисел - сколько
шариков надует каждый из помощников. Числа разделить пробелами. Если
распределений несколько, вывести любое из них.
Пример файла входных данных:
10
3
1 2
3
3
10 3
2 4
3
Пример файла выходных данных (для приведенного выше
входного файла):