Задание EGEINF09681E: Сортировка, отбор и моделирование

Решение.
В исходном журнале N = 15005 запросов, вместимость раздела K = 23218 Кбайт. Упорядочим запросы по времени. Строки времени имеют одинаковый формат ЧЧ:ММ:СС, поэтому их обычная сортировка совпадает с хронологической.
Объёмы по клиентам и резервные копии считаем отдельно. Для каждого клиента складываем объёмы его запросов. Для раздела храним used — сумму данных, записанных после последнего освобождения.
Перед очередным запросом объёма size проверяем used + size > K. Если места не хватает, создаётся копия объёма used во время текущего запроса, затем раздел освобождается. Только после этого записывается новый запрос. Поэтому он не входит в создаваемую перед ним копию.
При used + size = K запрос помещается полностью и копия ещё не создаётся. В конце журнала оставшиеся данные сами по себе не образуют резервную копию: по условию копирование вызывается нехваткой места для следующего запроса.
До обработки первого запроса used = 0. После каждого шага used равен сумме именно тех запросов, которые находятся в разделе сейчас. Описанная проверка сохраняет этот инвариант и перечисляет все моменты копирования. Для ограничения по времени используем момент создания копии, а не время первого записанного в неё запроса.
Для первого числа суммируем запросы каждого клиента только до 12:00:00 и выбираем идентификатор с наибольшей суммой. Для второго числа ограничение по времени не задано: из всех резервных копий за день выбираем два наибольших объёма и складываем их.
Сохраните скачанный файл рядом с программой под исходным именем. Программа на Python:

with open("img1_1786621788.txt") as f:
    n, capacity = map(int, f.readline().split())
    log = []
    for line in f:
        time, client, size = line.split()
        log.append((time, int(client), int(size)))
log.sort(key=lambda row: row[0])
totals = {}
morning = {}
backups = []
used = 0
for time, client, size in log:
    totals[client] = totals.get(client, 0) + size
    if time < '12:00:00':
        morning[client] = morning.get(client, 0) + size
    if used + size > capacity:
        backups.append((time, used))
        used = 0
    used += size
first = max(morning, key=morning.get)
sizes = sorted((size for time, size in backups), reverse=True)
second = sizes[0] + sizes[1]
print(first, second)

Для первого числа отобраны клиент 9517: 134167 Кбайт. Среди подходящих устройств получен требуемый результат 9517.
Для второго числа выбраны копии 14:04:47: 23218 Кбайт; 15:06:41: 23218 Кбайт. Получаем 46436 Кбайт.
Проверка: найдено 1116 резервных копий, из них 560 до полудня и 556 начиная с полудня. В конце осталось 13562 Кбайт. Сумма объёмов всех копий и этого остатка равна сумме всех запросов 24927279 Кбайт.
Независимый расчёт использовал префиксные суммы запросов. Для каждого начала блока бинарным поиском найдена последняя граница, при которой сумма не превышает K; следующий запрос вызывает копию. Все границы блоков и объёмы совпали с пошаговой симуляцией.
Сортировка и выбор требуемых максимумов занимают O(N log N) времени; симуляция — O(N). Память для журнала, сумм и списка копий O(N).
Ответ: 9517 46436.