Шкафчики
(Время: 5 сек. Память: 16 Мб Сложность: 58%)
Тренажерный зал в течение суток планирует принять N клиентов, время прихода и ухода каждого из них определено с точностью до минуты. Находясь в тренажерном зале, клиент занимает один из M шкафчиков для раздевалок. Шкафчики в учреждении нумеруются целыми числами от 1 до M.
По заданному расписанию визитов клиентов требуется распределить шкафчики таким образом, чтобы каждый человек в свое время посещения использовал отдельный шкафчик.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N и M – количество клиентов и шкафчиков соответственно. Каждая из последующих N строк содержит информацию о клиенте: фамилию, время прихода и время ухода, разделенные пробелом. Фамилия содержит от 1 до 10 символов английского алфавита. Время прихода строго меньше времени ухода. Каждое из времен имеет формат ЧЧ:ММ (1 ≤ N, M ≤ 105, 00:00 ≤ ЧЧ:ММ ≤ 23:59).
Выходные данные
В выходной файл OUTPUT.TXT выведите фамилии клиентов и номера занимаемых ими шкафчиков в той же последовательности, в которой они заданы во входных данных. Если существует несколько решений, выведите любое. Если решения не существует, выведите «No solution» (без кавычек).
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 3
Ivanov 09:00 13:30
Petrov 05:30 10:00
Sidorov 09:30 14:00
Orlov 13:30 16:15
Frolov 13:00 17:00 | Ivanov 2
Petrov 1
Sidorov 3
Orlov 2
Frolov 1 |
| 2 | 2 1
Kuznetsov 09:00 12:00
Bobrov 11:59 13:20 | No solution |
Система оценки
Решения для N ≤ M будут оцениваться в 20 баллов.
Решения для N ≤ 1000 будут оцениваться в 60 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
