Обработка журнала сервера
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела, выполненной не позднее 11:59:59.
Первая строка входного файла содержит два натуральных числа: $N$ ($N < 1\,000\,000$) — количество строк в журнале и $K$ ($K < 1\,000\,000$) — вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит время регистрации запроса в формате ЧЧ:ММ:СС и два натуральных числа: $C$ ($C < 1\,000\,000$) — идентификатор клиентского устройства и $S$ ($S < K$) — объём данных запроса в Кбайт.
В ответе запишите два числа: сначала наибольший суммарный объём данных, переданных на сервер с двух устройств, а затем объём последней по времени резервной копии, выполненной не позднее 11:59:59.
Типовой пример организации данных во входном файле:
$N = 8$, $K = 140000$.
$01{:}01{:}01$, $101$, $20000$
$03{:}03{:}03$, $202$, $110000$
$05{:}05{:}05$, $101$, $90000$
$07{:}07{:}07$, $303$, $62000$
$10{:}10{:}10$, $101$, $48000$
$15{:}15{:}15$, $202$, $12000$
$21{:}21{:}21$, $303$, $120000$
$23{:}23{:}23$, $404$, $134000$
При таких исходных данных резервное копирование выполняется четыре раза: в $05{:}05{:}05$ в объёме $130000$ Кбайт, в $07{:}07{:}07$ в объёме $90000$ Кбайт, в $21{:}21{:}21$ в объёме $122000$ Кбайт и в $23{:}23{:}23$ в объёме $120000$ Кбайт. Всего на сервер передано $596000$ Кбайт данных: $158000$, $122000$, $182000$ и $134000$ Кбайт от клиентов с идентификаторами $101$, $202$, $303$ и $404$ соответственно.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Какие данные нужно накапливать отдельно для каждого идентификатора клиента и как определить момент создания резервной копии?
2Наводящая — какие числа считатьуровень 2 из 3
Храните сумму объёмов для каждого клиента в словаре. Для резервных копий поддерживайте текущий объём раздела: если добавление очередного запроса невозможно, запишите текущую сумму как объём копии и обнулите накопитель.
3Прямая — фактически решениеуровень 3 из 3
После обработки журнала найдите две наибольшие суммы среди значений словаря. Для второй величины обновляйте ответ только при времени резервной копии не позднее 11:59:59; последняя подходящая копия и будет искомой.