25/04/2024 12:55:30

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1402. Рестораны

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

В некотором городе есть сеть ресторанов, имеющая в общей сложности `N` практически одинаковых залов. Администрации поступило `K` заявок на проведение в предпраздничный день корпоративных мероприятий. В каждой заявке указано время начала и окончания (от 00:00 до 23:59). Для проведения одного мероприятия нужен целиком один зал (какой конкретно, значения не имеет). После окончания мероприятия нужно не менее получаса для подготовки к следующему мероприятию в этом зале. Требуется удовлетворить как можно большее число заявок. Если можно удовлетворить все, то при этом следует использовать наименьшее число залов.

В первой строке входного файла содержатся числа `N` и `K` (`1 ≤ N, K ≤ 100`). В каждой из следующих `K` строк содержится время начала и окончания заявки в формате ЧЧ:ММ-ЧЧ:ММ. Время окончания каждой заявки хотя бы на минуту больше времени её начала.

В первой строке выходного файла выведите два числа – количество заявок `P`, которые удалось удовлетворить, и количество залов `Q`, которое пришлось задействовать. В каждой из следующих `P` строк выведите по два числа - порядковый номер заявки (какой она стояла во входном файле) и номер зала. Если задача имеет несколько решений, то выведите любое из них.

Пример ввода

3 4
17:00-20:00
18:00-21:00
15:00-17:30
21:00-23:30

Пример вывода

Источник: XII Межвузовская олимпиада, г. Вологда, 2009

24/06/2010	Лето 2010 дорешивание ( 2I)
25/06/2010	Лето 2010 - 2 (I)
07/11/2013	Занятие 8 для продолжающих (E)
10/07/2017	Лето 2017 - 8 (D)