Задание 26 демоверсии ЕГЭ 2027 по информатике: разбор

Обработка данных с сортировкой. Реши сам, потом открой решение.

Задание 26

Задание выполняется с использованием прилагаемого файла.

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 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.

Типовой пример организации данных во входном файле

8 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 (в объёме 130 000 Кбайт), в 07:07:07 (в объёме 90 000 Кбайт), в 21:21:21 (в объёме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт). Всего на сервер передано 596 000 Кбайт данных: 158 000, 122 000, 182 000 и 134 000 Кбайт от клиентов с идентификаторами 101, 202, 303 и 404 соответственно.

Ответ для приведённого примера: 303 220 000.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию 26

Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 23

Решение и ответ

Моделируем раздел памяти: храним, сколько в нём занято. Если очередной запрос не помещается (занято + $S > K$ ), сервер делает копию всего занятого объёма с временем этого запроса, обнуляет раздел и только потом кладёт данные.
Параллельно копим суммарный объём по каждому клиенту в словаре. Записи в файле уже идут по времени; время ЧЧ:ММ:СС с ведущими нулями можно сравнивать как строки.

f = open('26.txt')
n, k = map(int, f.readline().split())
used, total, backups = 0, {}, []
for _ in range(n):
    t, c, s = f.readline().split()
    c, s = int(c), int(s)
    if used + s > k:              # места не хватает — резервная копия
        backups.append((t, used))
        used = 0
    used += s
    total[c] = total.get(c, 0) + s

best = max(total, key=total.get)
early = sorted((v for t, v in backups if t <= '11:59:59'), reverse=True)
print(best, sum(early[:2]))

Больше всего данных передал клиент 7040; две наибольшие копии до 11:59:59 дают в сумме 52204 Кбайт.

Ответ: 7040 52204