06/04/2025 13:04:14

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

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

Задачи

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

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

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

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

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

Задачи

828. Гонка преследования

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

В гонке преследования участники стартуют в таком порядке и с такими интервалами, с какими они пришли на финиш в спринте. Участник, пришедший первым к финишу по результатам спринта, стартует первым. Участник, показавший время в спринте на

$t$ секунд больше победителя, стартует на

$t$ секунд позже первого участника. Чтобы во время старта спортсмены не мешали друг другу, участники с близким временем должны стартовать по разным дорожкам. Дорожка становится доступной для старта очередного участника через

$D$ секунд.

Напишите программу, вычисляющую по результатам спринта минимальное количество стартовых дорожек в гонке преследования.

В первой строке ввода содержатся два целых числа – число участников

$N$ (

$1\ ≤\ N\ ≤\ 1000$ ) и интервал времени в секундах между стартами участников по одной дорожке

$D$ (

$1\ ≤\ D\ ≤\ 100$ ). Далее следует

$N$ строк,

$i$ -я строка содержит время финиша

$i$ -го участника в спринте в формате

$h$ :

$"mm"$ :

$"ss"$ , где

$h$ (

$0\ ≤\ h\ <\ 20$ ) – часы,

$"mm"$ (

$00\ ≤\ "mm"\ ≤\ 59$ ) – минуты, а

$"ss"$ (

$00\ ≤\ "ss"\ ≤\ 59$ ) – секунды. В спринте используется раздельный старт участников с интервалом в 1 минуту, т.е.

$i$ -й участник стартует в момент времени (

$i-1$ ):00, результат участника вычисляется как разница между временем старта и временем финиша. Время финиша у всех участников больше времени старта.

Вывести одно число – минимальное число стартовых дорожек в гонке преследования.

Пример ввода

3 10
0:09:15
0:10:00
0:11:05

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

15/03/2008	Южно-Уральский открытый командный чемпионат по программированию (K)
03/07/2013	Лето 2013-3 (I)
29/06/2018	Лето 2018 - 3 (командные) (G)
02/07/2021	Лето 2021-3 (командное) (F)
01/07/2022	Лето 2022-3 (командное) (D)
11/11/2023	Марафон 80 задач, 4 этап (G)