Question

В текстовом файле содержится некоторое количество натуральных чисел. Определите и запишите в ответ максимальную сумму трех чисел, чтобы любые два числа находились на расстоянии не менее *К* друг от друга. **Входные данные.**Файл АФайл В

Первая строка файла содержит число *k* — расстояние между элементами, вторая строка файла содержит содержит количество элементов в файле.

Ответ:

Accepted Answer

Answer

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

В текстовом файле содержится некоторое количество натуральных чисел. Определите и запишите в ответ максимальную сумму трёх чисел, при условии, что любые два из них находятся на расстоянии не менее $k$ позиций друг от друга.

**Входные данные:**
- Первая строка: число $k$ — минимальное расстояние между элементами.
- Вторая строка: число $n$ — количество элементов в файле.
- Следующие $n$ строк: натуральные числа.

**Выходные данные:**
Максимальная сумма трёх чисел, удовлетворяющих условию расстояния.

### РЕШЕНИЕ

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

Обозначим позиции элементов как $0, 1, 2, \ldots, n-1$. Если выбраны три элемента на позициях $i$, $j$, $l$ (где $i < j < l$), то должны выполняться условия:
- $j - i \geq k$
- $l - j \geq k$

Следовательно, $l - i \geq 2k$, поэтому третий элемент может быть выбран только начиная с позиции $2k$.

Для каждой позиции $i$ вычислим:
- `st` — максимальное значение среди элементов на позициях $[0, i - 2k]$ (первый элемент тройки).
- `fin` — максимальная сумма первого и второго элементов, где второй находится на позициях $[k, i - k]$ (сумма первых двух).
- `summa` — максимальная сумма всех трёх элементов.

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

st = 0
fin = 0
summa = 0

for i in range(2 * k, n):
    st = max(st, a[i - 2 * k])
    fin = max(fin, st + a[i - k])
    summa = max(summa, fin + a[i])

print(summa)
```

На каждом шаге:
1. Обновляем `st` — максимум среди доступных первых элементов.
2. Обновляем `fin` — максимум суммы первого и второго элементов.
3. Обновляем `summa` — максимум суммы всех трёх элементов.

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

### ОТВЕТ

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