Question

Метеорологическая станция ведёт наблюдение за количеством выпавших осадков. Показания записываются каждую минуту в течение *N* минут.Определяется пара измерений, между которыми прошло не менее *K* минут. Найдите максимальную сумму показаний среди таких пар. Файл АФайл В

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

**Предупреждение:** для обработки файла *B* не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:

Accepted Answer

Answer

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

Метеорологическая станция ведёт наблюдение за количеством выпавших осадков. Показания записываются каждую минуту в течение *N* минут. Определяется пара измерений, между которыми прошло не менее *K* минут. Найдите максимальную сумму показаний среди таких пар.

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

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

**Предупреждение:** для обработки файла *B* не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

### РЕШЕНИЕ

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

**Решение для файла A (тестовый файл):**

```python
f = open('27A.txt')
n = int(f.readline())
k = int(f.readline())
a = [int(x) for x in f]

max_sum = 0
max_prev = 0

for i in range(k, n):
    max_prev = max(max_prev, a[i - k])
    max_sum = max(max_sum, a[i] + max_prev)

print(max_sum)
```

Алгоритм работает следующим образом:
- Начиная с позиции *K*, для каждого текущего измерения `a[i]` отслеживаем максимальное значение среди всех измерений на позициях `[0, i-K]`.
- На каждом шаге обновляем `max_prev` — максимум на допустимом расстоянии.
- Вычисляем сумму текущего измерения и `max_prev`, обновляя общий максимум.

Сложность: $O(n)$ — один проход по массиву.

**Решение для файла B (оптимизированное):**

```python
a = [int(s) for s in open('27B.txt')]
k = a[1]
max_sum = 0
max_prev = 0
a = a[2:]

for i in range(k, len(a)):
    max_prev = max(max_prev, a[i - k])
    max_sum = max(max_sum, max_prev + a[i])

print(max_sum)
```

Этот вариант использует ту же логику, но читает данные более компактно. Сложность остаётся $O(n)$, что позволяет обработать большие файлы за приемлемое время.

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

### ОТВЕТ

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