НачалоПодразделы
| 648. Космическая станция |
Другие разделы
Дата и время
20/12/2024 12:15:37
Занятие 7
A. Спрятанный текст B. Сдача C. Космическая станция D. Задача о расписании E. Канатная дорога F. Отрезки G. Advertisement
E. Канатная дорога
Жадные алгоритмыСтеки, очереди
Олимпиадные задачи на русском языке
| 10/01/2007 | Областная олимпиада школьников по информатике (командные соревнования) (4) |
| 24/10/2007 | Занятие 7 (E) |
| 19/11/2011 | Занятие 6 (C) |
| 25/03/2013 | Занятие 21 (C) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Чтобы спуститься по канатной дороге и сесть в поезд, требуется ровно 30 минут. Хотя вагончики канатной дороги приходят ежеминутно, вместимость их ограничена. Поэтому, когда заканчиваются рождественские каникулы и все гости горнолыжного курорта уезжают домой, на станции канатной дороги выстраивается длинная очередь, и многие туристы рискуют опоздать на свой поезд.
Напишите программу, которая определяет порядок посадки туристов в вагончики канатной дороги, минимизирующий количество опоздавших на поезд.
В первой строке входного файла содержатся два целых числа, разделенных пробелом – вместимость одного вагончика `N` (`1\ ≤\ N\ ≤\ 100`) и количество уезжающих групп туристов `K` (`1\ ≤\ K\ ≤\ 1000`). Далее следует `K` строк, каждая строка содержит время прихода группы на станцию канатной дороги в формате ЧЧ:ММ, время отхода их поезда в формате ЧЧ:ММ и количество человек в группе (целое число от 1 до 100), данные в строке разделены пробелами. Информация о группах упорядочена по времени их прихода. Время задано в пределах одних суток от 00:00 до 23:59. Разница между временем прихода группы и отхода их поезда не менее 30 минут.
В выходной файл вывести одно целое число – минимальное количество туристов, опоздавших на поезд.
Пример ввода
2 3 08:00 08:35 3 08:00 08:31 5 08:03 08:35 5
Вывод для примера
1
