Задание 26 ЕГЭ по информатике · 1E4F52

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела, выполненной не позднее 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. Для каждого запроса увеличиваем сумму переданных данных соответствующего клиента на величину S.

2. Поддерживаем объём данных в специальном разделе. Если текущий объём вместе с новым запросом становится не меньше вместимости раздела K, создаём резервную копию накопленных данных, запоминаем её объём и очищаем раздел перед обработкой нового запроса.

3. Для каждой резервной копии сравниваем время с 11:59:59. Среди копий, выполненных не позднее этого времени, сохраняем последнюю по времени.

4. После обработки всех строк сортируем суммы по клиентам или находим две максимальные суммы одним проходом. Их сумма является первым числом ответа.

5. Вторым числом записываем объём найденной последней подходящей резервной копии.