Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

26. Прикладная задача: Ответ для приведённого примера: 101 252000

Задание #298074
Решено верно
Решено неверно
Сообщить о проблеме

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

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: $N$ ($N < 1000000$) – количество строк в журнале и $K$ ($K < 1000000$) – вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих $N$ строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: $C$ ($C < 1000000$) – идентификатор клиентского устройства и $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$ (в объёме $130000$ Кбайт), в $07{:}07{:}07$ (в объёме $90000$ Кбайт), в $21{:}21{:}21$ (в объёме $122000$ Кбайт) и в $23{:}23{:}23$ (в объёме $120000$ Кбайт). Ответ для приведённого примера: $101$ $252000$.

Задача распадается на две независимые части, которые считаются за один проход по журналу.

Первая — моделирование раздела памяти. Держим счётчик накопленного объёма. Для очередного запроса проверяем, влезает ли он: если накопленное плюс новый объём превышает вместимость $K$, сервер сначала делает резервную копию того, что уже лежит в разделе, и обнуляет счётчик, и только потом кладёт туда новый запрос. Обратите внимание на порядок: в копию попадает объём до добавления текущего запроса. В примере это хорошо видно — в $05{:}05{:}05$ копируются $130000$ Кбайт, накопленные первыми двумя запросами, а сам запрос на $90000$ уже начинает новый цикл.

Вторая — суммы по клиентам. Складываем объёмы по идентификаторам, но только для запросов не позднее $11{:}59{:}59$. Время удобно сравнивать прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически, поэтому разбирать его на числа не нужно.

from collections import defaultdict

f = open('26-20.txt')
n, K = map(int, f.readline().split())

total = defaultdict(int)
backups = []
cur = 0

for _ in range(n):
    t, c, s = f.readline().split()
    s = int(s)
    if cur + s > K:                  # свободной памяти не хватает
        backups.append(cur)          # резервная копия накопленного
        cur = 0
    cur += s
    if t <= '11:59:59':              # строки в формате ЧЧ:ММ:СС сравниваются как время
        total[int(c)] += s

backups.sort(reverse=True)
best = max(total, key=lambda c: total[c])

print(best, backups[0] + backups[1])   # 9517 46436

Проверка. В журнале $15005$ записей, вместимость раздела $23218$ Кбайт, резервных копий получилось $1116$. Две наибольшие оказались по $23218$ Кбайт каждая, то есть ровно под завязку, в сумме $46436$. По клиентам до полудня лидирует устройство $9517$ с объёмом $134167$ Кбайт, следующее за ним — $6877$ со $121879$. На типовом примере из условия программа выдаёт $101$ и $252000$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение