АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

691. E - рестораны

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

В некотором городе есть сеть ресторанов, имеющая в общей сложности 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

4 2

1 1

2 2

3 2

4 1

 


Статистика Послать на проверку Обсуждение задачи Автор/источник: Межвузовская олимпиада по программированию, Вологда, 2009
Задачи с соревнований / Межвузовские олимпиады / XII Межвузовская олимпиада 2009 /
690. D - полка 691. 692. F - перевёртыш 694. H - игра 695. I - близкие числа
 
время генерации 0.125 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.