Question

По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин. в течение *T* мин. (*T* — целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения. Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее *K* мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.Файл АФайл В

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

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин. в течение $T$ мин. ($T$ — целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения. Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее $K$ мин., а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.

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

**Выходные данные.** Запишите в ответе два числа: сначала значение искомой величины для файла A, затем — для файла B.

**Типовой пример.** При $K = 3$, $N = 5$, последовательность показаний: 15, 10, 20, 0, 30. Максимально возможное суммарное количество осадков равно 45 — это сумма осадков, выпавших на первой и пятой минутах (индексы 0 и 4, разница 4 ≥ 3).

### РЕШЕНИЕ

Идея решения: для каждой позиции $i$ найти максимальное значение среди всех элементов с индексами от 0 до $i - K$, затем вычислить максимальную сумму этого максимума и элемента в позиции $i$.

Алгоритм:
1. Прочитаем параметр $K$ и количество показаний $N$.
2. Загрузим все показания в массив.
3. Пройдём по массиву, начиная с позиции $K$. Для каждой позиции $i$ отслеживаем максимальное значение среди элементов с индексами $0, 1, \ldots, i - K$.
4. На каждом шаге вычислим сумму текущего максимума и элемента в позиции $i$, обновляя общий максимум суммы.

```python
with open('27_A.txt') as f:
    k = int(f.readline())
    n = int(f.readline())
    a = [int(f.readline()) for _ in range(n)]

max_left = 0
result = 0
for i in range(k, n):
    max_left = max(max_left, a[i - k])
    result = max(result, max_left + a[i])

print(result)
```

Для файла B применяем тот же алгоритм:

```python
with open('27_B.txt') as f:
    k = int(f.readline())
    n = int(f.readline())
    a = [int(f.readline()) for _ in range(n)]

max_left = 0
result = 0
for i in range(k, n):
    max_left = max(max_left, a[i - k])
    result = max(result, max_left + a[i])

print(result)
```

**Пояснение.** На каждой итерации переменная `max_left` хранит максимум среди всех элементов, которые находятся на расстоянии не менее $K$ позиций слева от текущей позиции $i$. Переменная `result` накапливает максимальную сумму пары элементов, удовлетворяющих условию расстояния.

Сложность: $O(n)$ — один проход по массиву с постоянными операциями на каждом шаге.

### ОТВЕТ

Задание №27ПрограммированиеЕГЭ по информатике