Question

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

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

Ответ:

Accepted Answer

Answer

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

По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин. в течение $T$ мин. ($T$ — целое число). Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения. Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее $K$ мин., а их произведение было минимально возможным. Укажите найденное произведение.

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

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

**Типовой пример организации данных во входном файле:**

```
3
5
1
5
10
2
0
3
```

При таких исходных данных минимально возможное произведение количество осадков равно 10 — это произведение осадков, выпавших на второй и пятой минутах.

### РЕШЕНИЕ

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

Алгоритм работает следующим образом:

1. Читаем значение $K$ и количество показаний $N$.
2. Загружаем все показания в массив.
3. Проходим по массиву, начиная с позиции $K$. Для каждой позиции $i$ отслеживаем минимальное значение среди элементов с индексами от 0 до $i - K$ включительно.
4. Вычисляем произведение текущего минимума и элемента на позиции $i$, обновляя глобальный минимум произведений.

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

pr = 10**18
mini = 10**18

for i in range(n):
    mini = min(mini, a[i])
    if i + k < len(a):
        pr = min(pr, mini * a[i + k])

print(pr)
```

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

### ОТВЕТ

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