Сервер выполняет запросы на передачу данных, при этом сведения о каждом выполненном запросе (время регистрации, идентификатор клиента, объём переданных данных) сохраняются в журнале работы, а переданные данные – в специальном разделе памяти сервера, имеющем ограниченный объём.
Каждый раз, когда остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу обработки журнала работы сервера и определите идентификатор клиентского устройства, с которого на сервер был передан наибольший общий объём данных, а также сумму объёмов (в Кбайт) двух наибольших резервных копий специального раздела, созданных не позднее 11:59:59.
Входные данные
Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: N (N < 1 000 000) – количество строк в журнале и K (K < 1 000 000) – вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: C (C < 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 соответственно.
Ответ для приведённого примера: 303 220 000.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Демонстрационный вариант ЕГЭ 2027 по информатике – задание №26
Решение:
Нужно определить:
- идентификатор клиента, который передал на сервер наибольший суммарный объём данных;
- сумму объёмов двух наибольших резервных копий, созданных не позднее
11:59:59.
Используем следующий код:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
f = open('26.txt') N, K = map(int, f.readline().split()) clients = {} backup = [] used = 0 for _ in range(N): time, client, size = f.readline().split() client = int(client) size = int(size) # Суммарный объём данных каждого клиента clients[client] = clients.get(client, 0) + size # Если очередной запрос не помещается в специальный раздел if used + size > K: # В этот момент создаётся резервная копия if time <= '11:59:59': backup.append(used) # После создания резервной копии раздел очищается used = 0 # Данные текущего запроса записываются в раздел used += size # Клиент с максимальным суммарным объёмом данных max_client = max(clients, key=clients.get) # Находим две наибольшие резервные копии backup.sort(reverse=True) backup_sum = backup[0] + backup[1] print(max_client, backup_sum) |
Разбор программы
Сначала открываем файл и считываем значения N и K:
|
1 2 3 |
f = open('26.txt') N, K = map(int, f.readline().split()) |
Здесь:
N— количество запросов;K— размер специального раздела памяти сервера.
Создаём словарь для хранения суммарного объёма данных каждого клиента:
|
1 |
clients = {} |
Также создаём список для объёмов резервных копий:
|
1 |
backup = [] |
Переменная used хранит текущий объём данных в специальном разделе:
|
1 |
used = 0 |
Далее обрабатываем все запросы:
|
1 2 |
for _ in range(N): time, client, size = f.readline().split() |
Идентификатор клиента и объём запроса переводим в целые числа:
|
1 2 |
client = int(client) size = int(size) |
Для каждого клиента накапливаем общий объём переданных данных:
|
1 |
clients[client] = clients.get(client, 0) + size |
Метод get() возвращает уже накопленное значение для клиента,
а если клиент встречается впервые — значение 0.
Создание резервной копии
Перед добавлением нового запроса проверяем, помещается ли он в оставшееся место:
|
1 |
if used + size > K: |
Если объёма памяти недостаточно, сервер создаёт резервную копию всех данных,
которые уже находятся в специальном разделе.
Если резервная копия создаётся не позднее 11:59:59,
сохраняем её объём:
|
1 2 |
if time <= '11:59:59': backup.append(used) |
После создания копии раздел освобождается:
|
1 |
used = 0 |
Затем в раздел записываются данные текущего запроса:
|
1 |
used += size |
Важно, что запрос, который не поместился, не входит в созданную резервную копию.
Сначала копируются уже накопленные данные, затем раздел очищается,
и только после этого записывается новый запрос.
Поиск клиента с наибольшим объёмом данных
После обработки всех запросов находим клиента,
у которого суммарный объём переданных данных максимален:
|
1 |
max_client = max(clients, key=clients.get) |
Поиск двух наибольших резервных копий
Сортируем объёмы резервных копий по убыванию:
|
1 |
backup.sort(reverse=True) |
После этого первые два элемента списка являются двумя наибольшими резервными копиями:
|
1 |
backup_sum = backup[0] + backup[1] |
В конце выводим требуемые два числа:
|
1 |
print(max_client, backup_sum) |
Идея решения
Программа за один проход по файлу одновременно считает суммарный объём данных каждого клиента
и моделирует заполнение специального раздела памяти.
Каждый раз, когда очередной запрос не помещается, фиксируется объём создаваемой резервной копии.
После обработки всех данных выбирается клиент с максимальным суммарным объёмом
и сумма двух наибольших резервных копий, созданных не позднее 11:59:59.
Ответ: 7040 52204