Question

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

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

Ответ:

Accepted Answer

Answer

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

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

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

**Пример.** При $K = 2$, $N = 6$ и последовательности 15, 14, 20, 23, 21, 10 ответ равен 45 (сумма значений на позициях 1, 3 и 6: $15 + 20 + 10 = 45$).

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

### РЕШЕНИЕ

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

Обозначим позиции как $0, 1, 2, \ldots, N-1$. Если выбраны три позиции $i < j < k$, то должны выполняться условия:
- $j - i \geq K$
- $k - j \geq K$

Для каждой позиции $i \geq 2K$ рассмотрим её как третий (последний) элемент тройки. Тогда второй элемент должен быть на позиции $j$ такой, что $K \leq i - j$, то есть $j \leq i - K$. Первый элемент должен быть на позиции $p$ такой, что $K \leq j - p$, то есть $p \leq j - K$.

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

Реализация:

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

st = 10**10
fin = 10**10
summa = 10**10

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

print(summa)
```

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

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

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

### ОТВЕТ

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