Question

Дана последовательность целых чисел. Расстояние между элементами последовательности — это разность их порядковых номеров. Например, если два элемента стоят в последовательности рядом, расстояние между нимиравно 1, если два элемента стоят через один — расстояние равно 2 и так далее.Необходимо выбрать из последовательности три числа так, чтобы минимальное расстояние между выбранными числами было не меньше *K*, а их сумма была максимально возможной.В ответе запишите найденную сумму **Входные данные.**Файл АФайл В

Первая строка входного файла содержит целое число *K* — параметр для определения расстояния, вторая строка содержит число *N* — общее количество чисел в наборе (1 < 2*K* < *N*). Каждая из следующих *N* строк содержит одно число, не превышающее по модулю 107.*Пример входного файла:*26678235Из этого файла в соответствии с условиями можно выбрать числа 7, 8 и 5. Максимальное расстояние в данном случае равно 4 (между числами 7 и 5). Числа 6, 7 и 8 взять нельзя, так как максимальное расстояние в этом случае равно 2, а по условию оно должно быть не меньше 4. В ответе для этого примера надо написать число 20.Вам даны два входных файла (*A* и *B*), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала требуемую сумму для файла *A*, затем — для файла *B*.

Ответ:

Accepted Answer

Answer

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

Дана последовательность целых чисел. Расстояние между элементами — это разность их порядковых номеров (индексов). Требуется выбрать три числа так, чтобы минимальное расстояние между ними было не меньше $K$, а их сумма была максимальной.

**Входные данные:**

Первая строка — целое число $K$ (параметр расстояния).
Вторая строка — целое число $N$ (количество чисел в последовательности), где $1 < 2K < N$.
Следующие $N$ строк — по одному целому числу, не превышающему по модулю $10^7$.

**Пример:**

```
2
6
6
7
8
2
3
5
```

Из этого файла можно выбрать числа с индексами 0, 2, 4 (значения 6, 8, 3) или 0, 2, 5 (значения 6, 8, 5). Расстояния между ними: $2 - 0 = 2$, $4 - 2 = 2$, $5 - 2 = 3$ — все не меньше $K = 2$. Максимальная сумма: $6 + 8 + 5 = 19$.

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

---

### РЕШЕНИЕ

Идея решения: для каждой позиции $i$ третьего элемента найти максимальное значение среди элементов на расстоянии не менее $K$ слева (позиции $\le i - 2K$) и максимальное значение среди элементов на расстоянии не менее $K$ справа (позиции $\ge i + 2K$), затем выбрать комбинацию с наибольшей суммой.

Алгоритм:

1. Прочитаем $K$, $N$ и массив чисел.
2. Для каждой позиции $i$ вычислим максимум всех элементов с индексами $\le i - 2K$ (левый максимум).
3. Для каждой позиции $i$ вычислим максимум всех элементов с индексами $\ge i + 2K$ (правый максимум).
4. Переберём все возможные позиции среднего элемента и найдём максимальную сумму левого максимума, среднего элемента и правого максимума.

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

# Вычислим максимум слева для каждой позиции
left_max = [float('-inf')] * n
current_max = float('-inf')
for i in range(n):
    if i >= 2 * k:
        current_max = max(current_max, a[i - 2 * k])
    left_max[i] = current_max

# Вычислим максимум справа для каждой позиции
right_max = [float('-inf')] * n
current_max = float('-inf')
for i in range(n - 1, -1, -1):
    if i + 2 * k < n:
        current_max = max(current_max, a[i + 2 * k])
    right_max[i] = current_max

# Найдём максимальную сумму
result = float('-inf')
for i in range(2 * k, n - 2 * k):
    if left_max[i] != float('-inf') and right_max[i] != float('-inf'):
        current_sum = left_max[i] + a[i] + right_max[i]
        result = max(result, current_sum)

print(result)
```

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

---

### ОТВЕТ

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