По каналу связи передаётся последовательность целых чисел...

Задание:

По каналу связи передаётся последовательность целых чисел – показания прибора. В течение N мин. (N – натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передаёт его на сервер.
Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин., а сумма этих трёх чисел была максимально возможной. Запишите в ответе найденную сумму.

Входные данные
Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число K – минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй – количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из Следующих N строк находится одно целое число, по модулю не превышающее 10 000 000, которое обозначает значение напряжения в соответствующую минуту.
Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

2
6
150
–150
20
–200
–300
0

При таких исходных данных искомая величина равна 170 – это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

Примечание: файлы в архиве с демоверсией ЕГЭ-2024 по информатике

Решение (программное, 27А)

Переберем все тройки с учетом указанного в условии расстояния.

with open('27_A_2024.txt') as f:
  k = int(f.readline())
  n = int(f.readline())
  nums = [int(f.readline()) for _ in range(n)]

mx = float('-inf')
for i in range(n):
   for j in range(i+k, n):
      for m in range(j+k, n):
         mx = max(mx, nums[i] + nums[j] + nums[m])
print(mx) 

Вывод:
189536

Решение (программное, массивы суффиксов и префиксов, 27В)

В списке suf будем хранить максимальные значения в последовательности, которые расположены правее соответствующего элемента в последовательности (с учетом этого элемента).
В списке pfx будем хранить максимальные значения в последовательности левее соответствующего элемента, включая соответствующий элемент.

Пример.
Список чисел:

С помощью таких списков мы сможем для каждого элемента определить максимальную сумму тройки. Например, для числа 1 на четвертой позиции и K = 2 максимальная сумма тройки будет prx[2] + 1 + suf[6] = 2 + 1 + 7 = 10

with open('27_B_2024.txt') as f:
 k = int(f.readline())
 n = int(f.readline())
 nums = [int(f.readline()) for _ in range(n)]

prx = [nums[0]]*n
for i in range(1, n):
  prx[i] = max(prx[i-1], nums[i])

suf = [nums[-1]]*n
for i in range(n-2, -1, -1):
  suf[i] = max(suf[i+1], nums[i])

mx = float('-inf')
for i in range(k, n-k):
  mx = max(mx, prx[i-k] + nums[i] + suf[i+k])
 
print(mx)
 

Вывод:
17210

Решение (электронные таблицы, массивы суффиксов и префиксов, 27В)

Вставим данные в электронную таблицу. Первые две строки (K=166251, N=997506) перенесем в столбец G (ячейки G3 и G4). Удалим две первые строки.

Массив префиксов (столбец В):
B1 =A1
B2 =МАКС(B1; A2)
B2 растягиваем до конца диапазона
Массив суффиксов (столбец С):
C1 =МАКС(C2; A1)
C1 растягиваем до конца диапазона.
C997506 = A997506

Теперь найдем максимальную сумму для 166252 строки и растянем формулу на весь диапазон (число 332503 = 166252+166251)
D166252 =A166252 + B1 + C332503
Растянем формулу до конца диапазона и определим последнюю ячейку, где должна быть эта формула.
997506 – 166251 = 831255
И удалим все ячейки с формулами после строки 831255.

Найдем максимальную сумму тройки.
F4 =МАКС(D:D)

Решение (программное, динамическое программирование, 27B)

Описание алгоритма:

• будем обновлять 3 суммы максимумов (lft, lft_sum, res_sum):
  • из одного элемента, самый правый элемент суммы не менее чем на 2k позиций левее от текущего элемента;
  •  из двух элементов, самый правый элемент суммы не менее чем на k позиций левее от текущего элемента;
  • из трех элементов, самый правый элемент суммы может быть текущим элементом

with open('27_B_2024.txt') as f:
  k = int(f.readline())
  n = int(f.readline())
  nums = [int(f.readline()) for _ in range(n)]
 
lft = lft_sm = res_sm = float('-inf')
for i in range(2*k, n):
  lft = max(lft, nums[i-2*k])
  lft_sm = max(lft_sm, lft + nums[i-k])
  res_sm = max(res_sm, lft_sm + nums[i])
 
print(res_sm) 

Также мы можем обобщить последовательный поиск сумм через работу со списком, для этого помимо элементов для сумм выделим нейтральный элемент со значением 0, чтобы обобщить поиск суммы из одного элемента. Для удобства работы с индексами расположим суммы справа налево – sm[2] – сумма из одного элемента, s[1] – сумма из двух, s[0] – сумма из трех

with open('27_B_2024.txt') as f:
  k = int(f.readline())
  n = int(f.readline())
  nums = [int(f.readline()) for _ in range(n)]

sm = [float('-inf')]*3 + [0]
for i in range(2*k, n):
   for j in range(2, -1, -1):
      sm[j] = max(sm[j], sm[j+1] + nums[i-j*k])
     
print(sm[0]) 

Можно заметить, что нет необходимости хранить элементы последовательности, расположенные на расстоянии больше, чем 2k от проверяемого элемента (с учетом проверяемого элемента 2k+1). Поэтому мы можем воспользоваться очередью и хранить в ней только последние 2k+1 считанных значений.

with open('27_B_2024.txt') as f:
  k = int(f.readline())
  n = int(f.readline())
  nums = [int(f.readline()) for _ in range(2*k)] + [0]
  sm = [float('-inf')]*3 + [0]
 
  for i in range(2*k, n):
   nums[i % (2*k+1)] = int(f.readline())
   for j in range(2, -1, -1):
     sm[j] = max(sm[j], sm[j+1] + nums[(i-j*k) % (2*k+1)])
     
print(sm[0]) 

Вывод:
17210

Источник: Информатика с Джобсом | ЕГЭ