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

Сервер выполняет запросы на передачу данных. Для каждого запроса в журнале указаны время регистрации, идентификатор клиента и объём переданных данных. Переданные данные сохраняются в специальном разделе памяти сервера вместимостью K Кбайт. Каждый раз, когда для очередного запроса недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных данных, после чего освобождает раздел и продолжает выполнение запросов. Определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов двух наибольших резервных копий, созданных не позднее 11:59:59.
В первой строке входного файла находятся натуральные числа N и K: количество записей журнала и вместимость раздела памяти в Кбайт. В каждой из следующих N строк записаны время в формате ЧЧ:ММ:СС, идентификатор клиента C и объём данных S в Кбайт. Выведите два числа: сначала идентификатор клиента, затем сумму объёмов двух наибольших подходящих резервных копий.

1. Для каждого идентификатора клиента поддерживаем суммарный объём переданных данных. Это можно сделать словарём, не храня весь журнал.
total[C]+=S

2. Поддерживаем объём данных, накопленных в специальном разделе. Если очередной запрос не помещается, текущий объём становится резервной копией, после чего раздел освобождается.
current+S>K⇒backups.append(current), current=0

3. После освобождения раздела добавляем объём текущего запроса. Так моделируется последовательная обработка журнала.
current+=S

4. Из словаря выбираем идентификатор с наибольшей суммой. Среди резервных копий, созданных не позднее 11:59:59, выбираем две наибольшие и складываем их объёмы.

5. Времена можно сравнивать как строки формата ЧЧ:ММ:СС или перевести в секунды. Так как записи идут в хронологическом порядке, момент создания копии определяется временем запроса, перед которым раздел пришлось освободить.