printОбластная олимпиада школьников по информатике (командные соревнования)

print4. Канатная дорога

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Чтобы спуститься по канатной дороге и сесть в поезд, требуется ровно 30 минут. Хотя вагончики канатной дороги приходят ежеминутно, вместимость их ограничена. Поэтому, когда заканчиваются рождественские каникулы и все гости горнолыжного курорта уезжают домой, на станции канатной дороги выстраивается длинная очередь, и многие туристы рискуют опоздать на свой поезд.
Напишите программу, которая определяет порядок посадки туристов в вагончики канатной дороги, минимизирующий количество опоздавших на поезд.
В первой строке входного файла содержатся два целых числа, разделенных пробелом – вместимость одного вагончика `N` (`1\ ≤\ N\ ≤\ 100`) и количество уезжающих групп туристов `K` (`1\ ≤\ K\ ≤\ 1000`). Далее следует `K` строк, каждая строка содержит время прихода группы на станцию канатной дороги в формате ЧЧ:ММ, время отхода их поезда в формате ЧЧ:ММ и количество человек в группе (целое число от 1 до 100), данные в строке разделены пробелами. Информация о группах упорядочена по времени их прихода. Время задано в пределах одних суток от 00:00 до 23:59. Разница между временем прихода группы и отхода их поезда не менее 30 минут.
В выходной файл вывести одно целое число – минимальное количество туристов, опоздавших на поезд.

Пример ввода

2 3
08:00 08:35 3
08:00 08:31 5
08:03 08:35 5

Вывод для примера

1
В 8:00 едут 2 туриста из 2-ой группы, в 8:01 – еще 2 туриста из 2-ой группы, в 8:02 едут 2 туриста из 1-ой группы, в 8:03 – 1 из 1-ой группы и 1 из 3-ей группы, в 8:04 – 2 из 3-ей, в 8:05 – еще 2 из 3-ей. Опаздывает на поезд 1 турист из 2-ой группы.
loading