Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Шкафчики

(Время: 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.TXTOUTPUT.TXT
15 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
22 1
Kuznetsov 09:00 12:00
Bobrov 11:59 13:20
No solution

Система оценки

Решения для N ≤ M будут оцениваться в 20 баллов.

Решения для N ≤ 1000 будут оцениваться в 60 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2005 / 2006
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 A. Словесная запись числа
 B. Ёлочка
 C. Робот Гильберта
 D. Шкафчики
 E. Изоморфизм

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru