Задание 26 ЕГЭ: интервалы и события во времени

Журнал событий во времени. Тема номера — обработка данных и моделирование. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

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

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные — в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер поступило наибольшее количество запросов, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 09:59:59.

Входные данные

Первая строка входного файла 26.txt (журнала работы сервера) содержит два натуральных числа: N (N < 1 000 000) — количество строк в журнале и K (K < 1 000 000) — вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: C (C < 1 000 000) — идентификатор клиентского устройства и S (S < K) — объём данных запроса в Кбайт. Запросы записаны в порядке возрастания времени регистрации.

Выходные данные

В ответе запишите два числа: сначала идентификатор устройства, с которого на сервер поступило наибольшее количество запросов, а затем сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 09: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 Кбайт). Больше всего запросов (три) поступило с устройства 101. Ответ для приведённого примера: 101 220 000.

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

Запишите два числа через пробел.

Скачать файл к примеру

Решение

Моделируем раздел: если очередной запрос не помещается (занято + S > K), делаем резервную копию текущего содержимого (её время — время этого запроса), очищаем раздел и кладём туда запрос. Параллельно считаем запросы каждого клиента. Время удобно перевести в секунды от начала суток.

Ответ: 748015 574280.

def seconds(t):
    h, m, s = map(int, t.split(":"))
    return h * 3600 + m * 60 + s

f = open("26.txt")
n, K = map(int, f.readline().split())
total = {}
used = 0
backups = []                        # (время копии в секундах, объём)
for _ in range(n):
    t, c, s = f.readline().split()
    c, s = int(c), int(s)
    total[c] = total.get(c, 0) + 1
    if used + s > K:
        backups.append((seconds(t), used))
        used = 0
    used += s

top = max(total, key=total.get)
limit = seconds("09:59:59")
early = sorted((v for t, v in backups if t <= limit), reverse=True)
print(top, early[0] + early[1])

Решить такую задачу — новый вариант с проверкой