Обработка журнала сервера
Сервер выполняет запросы на передачу данных. Сведения о каждом выполненном запросе — время регистрации, идентификатор клиента и объём переданных данных — сохраняются в журнале работы, а сам запрос помещается в специальный раздел памяти сервера ограниченного объёма. Если для очередного запроса недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных данных, освобождает раздел и затем сохраняет очередной запрос.
Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор клиентского устройства, с которого на сервер был передан наибольший суммарный объём данных, не превышающий 150 000 Кбайт, а также сумму объёмов двух наибольших резервных копий специального раздела, выполненных не ранее 12:00:00.
Первая строка входного файла содержит два натуральных числа: $N$ — количество строк в журнале ($N < 1\,000\,000$) и $K$ — вместимость специального раздела памяти сервера в Кбайт ($K < 1\,000\,000$). Каждая из следующих $N$ строк содержит время регистрации запроса в формате ЧЧ:ММ:СС, идентификатор клиентского устройства $C$ ($C < 1\,000\,000$) и объём данных запроса $S$ ($S < K$) в Кбайт.
В ответ запишите два числа: сначала идентификатор устройства, с которого был передан наибольший суммарный объём данных, не превышающий 150 000 Кбайт, а затем сумму объёмов двух наибольших резервных копий, выполненных не ранее 12:00:00.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Какие данные достаточно хранить для каждого идентификатора клиента? Как определить момент создания резервной копии при последовательном просмотре журнала?
2Наводящая — какие числа считатьуровень 2 из 3
Поддерживайте словарь суммарных объёмов по клиентам и текущий объём занятой памяти. Если текущий объём плюс $S$ больше $K$, сначала сохраните текущий объём как резервную копию, затем обнулите его и добавьте новый запрос.
3Прямая — фактически решениеуровень 3 из 3
При переполнении запоминайте резервную копию только если время текущего запроса не меньше 12:00:00. После обработки журнала выберите максимальную сумму клиента, не превышающую 150 000, и два максимальных подходящих объёма резервных копий.