Карточки
Тесты
Главная
Курсы
Подписка
26. Прикладная задача: #298085
Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос – в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наибольший суммарный объём данных, переданных на сервер с двух клиентских устройств, а также объём последней по времени резервной копии специального раздела (в Кбайт), выполненной не позднее $11{:}59{:}59$.
Обе величины считаются за один проход по журналу, но обратите внимание на разницу с похожей задачей: здесь ограничение по времени наложено только на резервные копии, а суммы по клиентам берутся за все сутки.
Моделирование раздела памяти прежнее. Держим счётчик накопленного объёма; если накопленное плюс новый запрос превышает вместимость $K$, сервер делает копию того, что уже лежит в разделе, обнуляет счётчик и только потом кладёт туда новый запрос. В копию попадает объём до добавления текущего запроса.
Нужна не самая большая копия, а последняя по времени среди сделанных не позднее $11{:}59{:}59$. Поскольку журнал идёт в хронологическом порядке, достаточно просто перезаписывать переменную при каждой подходящей копии — в конце в ней останется нужная. Время сравниваем прямо как строки: формат ЧЧ:ММ:СС с ведущими нулями упорядочен лексикографически так же, как хронологически.
Суммы по клиентам копим в словаре без всяких условий, затем берём два наибольших значения и складываем.
from collections import defaultdict
f = open('26-25.txt')
n, K = map(int, f.readline().split())
total = defaultdict(int)
cur = 0
last_backup = 0
for _ in range(n):
t, c, s = f.readline().split()
s = int(s)
if cur + s > K: # свободной памяти не хватает
if t <= '11:59:59': # копия сделана не позднее 11:59:59
last_backup = cur
cur = 0
cur += s
total[int(c)] += s
top = sorted(total.values(), reverse=True)
print(top[0] + top[1], last_backup) # 481895 21328
Проверка. В журнале $15007$ записей, вместимость раздела $23000$ Кбайт, копий получилось $1115$. Последняя до полудня сделана в $11{:}59{:}10$ в объёме $21328$ Кбайт. Два самых активных клиента — $5382$ с объёмом $246899$ Кбайт и $4637$ с $234996$, в сумме $481895$. На типовом примере из условия программа выдаёт $340000$ и $90000$.
20
