Решение: Обработка журнала сервера
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела, выполненной не позднее 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$ соответственно.
Решение по шагам
5 шаговДля каждого запроса увеличиваем сумму переданных данных соответствующего клиента на величину $S$.
Поддерживаем объём данных в специальном разделе. Если текущий объём вместе с новым запросом становится не меньше вместимости раздела $K$, создаём резервную копию накопленных данных, запоминаем её объём и очищаем раздел перед обработкой нового запроса.
Для каждой резервной копии сравниваем время с $11{:}59{:}59$. Среди копий, выполненных не позднее этого времени, сохраняем последнюю по времени.
После обработки всех строк сортируем суммы по клиентам или находим две максимальные суммы одним проходом. Их сумма является первым числом ответа.
Вторым числом записываем объём найденной последней подходящей резервной копии.
Вывод зависит от данных прилагаемого файла: два числа — максимальная сумма данных от двух клиентов и объём последней резервной копии до 11:59:59.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать резервную копию после добавления запроса, хотя сначала нужно сохранить накопленные данные и освободить раздел.
Учитывать резервные копии после 11:59:59.
Искать двух клиентов с наибольшими отдельными запросами вместо двух наибольших сумм по клиентам.
Забыть обработать резервную копию, если условие её создания выполнено при добавлении очередного запроса.