Решение: Обработка журнала сервера
Сервер выполняет запросы на передачу данных. Сведения о каждом выполненном запросе — время регистрации, идентификатор клиента и объём переданных данных — сохраняются в журнале работы, а сам запрос размещается в специальном разделе памяти сервера ограниченного объёма. Когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите идентификатор клиентского устройства, с которого на сервер был передан наибольший суммарный объём данных не позднее 11:59:59, а также сумму объёмов двух наибольших резервных копий специального раздела в Кбайт.
Входные данные находятся в прилагаемом файле. Первая строка содержит два натуральных числа: N — количество строк в журнале и K — вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит время регистрации запроса в формате ЧЧ:ММ:СС, идентификатор клиентского устройства C и объём данных запроса S в Кбайт. Известно, что N < 1 000 000, K < 1 000 000, C < 1 000 000, S < K.
В ответе запишите два числа: сначала идентификатор устройства, с которого был передан наибольший суммарный объём данных не позднее 11:59:59, затем сумму объёмов двух наибольших резервных копий.
Решение по шагам
5 шаговДля каждого запроса преобразуем время в секунды от начала суток и сравниваем его с 11:59:59. Если запрос подходит по времени, увеличиваем суммарный объём данных соответствующего клиента.
$$t = 3600h + 60m + s$$Перед размещением запроса проверяем, достаточно ли свободного места. Если текущий объём памяти вместе с новым запросом превысит K, текущий объём становится очередной резервной копией, после чего раздел освобождается.
$$M + S > K \Rightarrow B_i = M,\ M = 0$$После проверки добавляем объём запроса в специальный раздел.
$$M := M + S$$Для каждой резервной копии обновляем две наибольшие найденные величины, не сохраняя весь список копий.
После обработки всех строк находим идентификатор клиента с максимальной суммой и складываем две наибольшие резервные копии.
Идентификатор клиента и сумма двух наибольших резервных копий определяются по данным прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают для первого ответа запросы после 11:59:59.
Создают резервную копию после добавления запроса, хотя сначала нужно проверить нехватку свободной памяти.
Забывают обнулить текущий объём после создания резервной копии.
Суммируют все резервные копии вместо двух наибольших.
Сохраняют недостаточно большие значения при обновлении двух максимумов.