Задача #4267

Сортировка

Уровень ЕГЭ

Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос - в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела (в Кбайт), выполненной не позднее 11:59:59.
Входные данные
Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: N (N< 1 000 000) - количество строк в журнале и К (К < 1 000 000) - вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ: CC (часы, минуты, секунды) и два натуральных числа: (С < 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 соответственно. Ответ для приведённого примера: 340 000 90 000.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файлы к задаче

Скачать 26.txt

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

481895

21328

f = open('26.txt')

N, K = [int(x) for x in f.readline().split()]

a = []

for s in f:
    t, idd, r = s.split()
    idd, r = int(idd), int(r)
    a.append([t,idd,r])

a.sort()

d = [0]*1_000_000

backup = []
server = 0
for t,idd,r in a:
    d[idd]+=r
    server += r
    if server>K:
        if int(t[:2])<12: backup.append(server-r)
        server = r

d.sort()

print(d[-1]+d[-2],backup[-1])

Номер