Олимпиадный тренинг

Задача . F. Анализ потока логов


Задача

Темы: Строки Бинарный поиск Перебор реализация *2000

Вам задан поток логов о предупреждениях в программе. Каждая запись потока логов представляет собой строку в формате:

«2012-MM-DD HH:MM:SS:MESSAGE» (без кавычек).

Строка «MESSAGE» состоит из пробелов, заглавных и строчных букв латинского алфавита, а также символов «!», «.», «,», «?». Строка «2012-MM-DD» определяет корректную дату в 2012 году. Строка «HH:MM:SS» определяет корректное время в 24 часовом формате.

Описанная запись потока логов обозначает, что в определенное в записи время произошло некоторое предупреждение в программе (описание предупреждения содержит строка «MESSAGE»).

Ваша задача вывести первый момент времени, когда количество предупреждений за последние n секунд стало не менее m.

Входные данные

В первой строке входных данных записаны два целых числа через пробел n и m (1 ≤ n, m ≤ 10000).

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

Гарантируется, что в логе есть хотя бы одна запись. Гарантируется, что суммарная длина всех строк потока логов не превышает 5·106 (в частности, это означает, что длина одной строки не превышает 5·106 символов). Гарантируется, что все заданные даты и времена корректны, а строка «MESSAGE» во всех записях не пустая.

Выходные данные

Если не существует искомого момента времени выведите -1. Иначе выведите строку в формате «2012-MM-DD HH:MM:SS» (без кавычек) — первый момент времени, когда количество предупреждений за последние n секунд стало не менее m.


Примеры
№Входные данныеВыходные данные
1 
60 3
2012-03-16 16:15:25: Disk size is
2012-03-16 16:15:25: Network failute
2012-03-16 16:16:29: Cant write varlog
2012-03-16 16:16:42: Unable to start process
2012-03-16 16:16:43: Disk size is too small
2012-03-16 16:16:53: Timeout detected
 
2012-03-16 16:16:43
2 
1 2
2012-03-16 23:59:59:Disk size
2012-03-17 00:00:00: Network
2012-03-17 00:00:01:Cant write varlog
 
-1
3 
2 2
2012-03-16 23:59:59:Disk size is too sm
2012-03-17 00:00:00:Network failute dete
2012-03-17 00:00:01:Cant write varlogmysq
 
2012-03-17 00:00:00

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет