По каналу связи передаётся последовательность целых неотрицательных чисел – показания прибора, полученные с интервалом в 1 мин. в течение T мин. (T – целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее K мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число K – количество минут, которое должно пройти между двумя передачами показаний, а во второй – количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих N строк находится одно целое неотрицательное число, не превышающее 100 000, обозначающее количество осадков за соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
3
5
15
10
200
0
30
При таких исходных данных максимально возможное суммарное количество осадков равно 45 – это сумма осадков, выпавших на первой и пятой минутах.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Открытый вариант ИНФОРМАТИКА КИМ ЕГЭ 2023 ФИПИ – задание №27
Решение:
для файла A — полный перебор
|
1 2 3 4 5 6 7 8 9 10 |
f = open('27A.txt') n = int(f.readline()) k = int(f.readline()) nums = [int(x) for x in f.readlines()] mx = 0 # перебираем все индексы в парах for i in range(n-k): for j in range(i+k, n): mx = max(mx, nums[i] + nums[j]) print(mx) |
для файла B
неоптимальное по памяти
При решении будем руководствоваться рассуждением:
— перебираем числа, начиная с k+1
— для каждого перебираемого числа нам нужно только одно число из начала последовательности – максимум на расстоянии ≥ k
|
1 2 3 4 5 6 7 8 9 10 11 12 |
f = open('27B.txt') n = int(f.readline()) k = int(f.readline()) nums = [int(x) for x in range(f.readlines())] mx_left = mx = 0 for i in range(k, n): # переопределяем максимум # в начале последовательности mx_left = max(mx_left, nums[i-k]) # переопеделяем максимум если надо mx = max(mx, nums[i] + mx_left) print(mx) |
или
сохраняем только k значений
Для удобного хранения применим очередь со сдвигом начала очереди.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
f = open('27B.txt') n = int(f.readline()) k = int(f.readline()) nums = [int(f.readline()) for _ in range(k)] mx_left = mx = 0 for i in range(k, n): x = int(f.readline()) # переопределяем максимум # в начале последовательности mx_left = max(mx_left, nums[i%k]) # переопеделяем максимум если надо mx = max(mx, x + mx_left) # на место числа на K левее записываем х nums[i%k] = x print(mx) |
Ответ:
1608 (для файла A)
7142285 (для файла B)