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