Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В некотором городе есть сеть ресторанов, имеющая в общей сложности N практически одинаковых залов. Администрации
поступило K заявок на проведение в предпраздничный день корпоративных мероприятий. В каждой заявке указано
время начала и окончания (от 00:00 до 23:59). Для проведения одного мероприятия нужен целиком
один зал (какой конкретно, значения не имеет). После окончания мероприятия нужно не менее получаса
для подготовки к следующему мероприятию в этом зале. Требуется удовлетворить как можно большее число заявок.
Если можно удовлетворить все, то при этом следует использовать наименьшее число залов.
В первой строке входного файла содержатся числа N и K (1 ). В каждой из следующих K строк
содержится время начала и окончания заявки в формате ЧЧ:ММ-ЧЧ:ММ. Время окончания каждой заявки хотя бы
на минуту больше времени её начала.
В первой строке выходного файла выведите два числа – количество заявок P, которые удалось удовлетворить, и количество
залов Q, которое пришлось задействовать. В каждой из следующих P строк выведите по два числа - порядковый номер
заявки (какой она стояла во входном файле) и номер зала. Если задача имеет несколько решений, то выведите любое из них.
Пример ввода
3 4
17:00-20:00
18:00-21:00
15:00-17:30
21:00-23:30
Пример вывода
4 2
1 1
2 2
3 2
4 1
Источник: XII Межвузовская олимпиада, г. Вологда, 2009