Question

В первых двух строках подаются два натуральных числа: сначала N — количество натуральных чисел в последовательности, затем K — минимальное расстояние, допустимое между любыми двумя элементами.Требуется найти минимальное значение произведения тройки элементов так, что между любыми элементами тройки расстояние между двумя элементами не менее K (то есть разность их индексов по модулю больше или равна K).**Входные данные.**Файл АФайл В

Ответ:

Accepted Answer

Answer

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

В первых двух строках файла подаются два натуральных числа: $N$ — количество элементов в последовательности и $K$ — минимальное расстояние между элементами. Требуется найти минимальное произведение тройки элементов последовательности таких, что расстояние (разность индексов) между любыми двумя элементами тройки не менее $K$.

**Входные данные:** файл содержит $N$ натуральных чисел, начиная со строки 3.

**Выходные данные:** одно натуральное число — минимальное произведение.

### РЕШЕНИЕ

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

Обозначим элементы последовательности как $a_0, a_1, \ldots, a_{n-1}$. Для тройки $(a_i, a_j, a_k)$ с $i < j < k$ условие расстояния требует $j - i \geq K$ и $k - j \geq K$, то есть $k \geq i + 2K$.

Алгоритм:
1. Для каждой позиции $i$ вычислим минимум среди всех элементов на позициях $[0, i - K]$ — это будет первый элемент тройки.
2. Для каждой позиции $j$ вычислим минимум произведения первого и второго элементов среди всех допустимых пар $(i, j)$ с $j - i \geq K$.
3. Для каждой позиции $k \geq 2K$ найдём минимум произведения всей тройки.

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

st = 10**10
fin = 10**10
proizved = 10**10

for i in range(2 * k, n):
    st = min(st, a[i - 2 * k])
    fin = min(fin, st * a[i - k])
    proizved = min(proizved, fin * a[i])

print(proizved)
```

Логика работы:
- `st` хранит минимум первого элемента тройки (из позиций $[0, i - 2K]$).
- `fin` хранит минимум произведения первого и второго элементов (из допустимых пар).
- `proizved` накапливает минимум произведения всей тройки.

На каждом шаге $i$ мы рассматриваем третий элемент $a_i$, обновляя минимум произведения с учётом уже найденных оптимальных первого и второго элементов.

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

### ОТВЕТ

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