Question

На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний прибора минимальноенечётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным −1. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору.Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.Перед программой укажите версию языка программирования. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А — 2 балла.Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора *N*, то есть при увеличении *N* в *k* раз время работы программы должно увеличиваться не более чем в *k* раз.Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа *N* и не превышает 1 килобайта.Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задаётся число *N* — общее количество показаний прибора. Гарантируется, что *N* > 6. В каждой из следующих *N* строк задаётся одно неотрицательное целое число — очередное показание прибора.Пример входных данных:1112455317232120191226Программа должна вывести одно число — описанное в условии произведение, либо — 1, если получить такое произведение не удаётся. Пример выходных данных для приведённого выше примера входных данных:95

Accepted Answer

Answer

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

На спутнике установлен прибор для измерения солнечной активности. Каждую минуту прибор передаёт неотрицательное целое число — количество энергии солнечного излучения в условных единицах (не превышает 1000). Необходимо найти минимальное нечётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если такое произведение получить не удаётся, ответ равен −1.

**Входные данные:** первая строка содержит число $N$ (гарантируется $N > 6$) — количество показаний. Далее в каждой строке одно неотрицательное целое число.

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

**Пример:**
```
11
2
4
5
5
3
1
7
2
3
2
1
20
19
```

**Ожидаемый вывод:** `95`

---

### РЕШЕНИЕ

**Задание А (решение за 2 балла)**

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

```pascal
var n, i, j : integer;
    mul, ans : longint;
    a : array [1 .. 10000] of longint;
begin
  readln(n);
  for i := 1 to n do
    readln(a[i]);
  ans := -1;
  for i := 1 to n - 6 do
    for j := i + 6 to n do
    begin
      mul := a[i] * a[j];
      if (mul mod 2 = 1) and ((ans = -1) or (mul < ans)) then
        ans := mul;
    end;
  writeln(ans);
end.
```

Сложность: $O(n^2)$ — приемлемо для тестового файла с $n \le 10000$.

---

**Задание Б (решение за 4 балла)**

Идея решения: использовать скользящее окно размером 6 элементов. При обработке позиции $i$ отслеживаем минимальное нечётное значение среди элементов на позициях $[i-6, i-1]$. Когда текущий элемент нечётный, вычисляем произведение с этим минимумом и обновляем ответ. Для экономии памяти используем циклический буфер размером 6.

```python
n = int(input())
a = []
mx = 10 ** 9
m = 10 ** 9

for i in range(6):
    a.append(int(input()))

for i in range(6, n):
    x = int(input())
    if a[i % 6] < mx and a[i % 6] % 2 != 0:
        mx = a[i % 6]
    if x % 2 != 0 and mx * x < m:
        m = mx * x
    a[i % 6] = x

if m == 10 ** 9:
    print(-1)
else:
    print(m)
```

Сложность: $O(n)$ по времени, $O(1)$ по памяти (буфер фиксированного размера 6).

---

### ОТВЕТ

![Рисунок](https://ege.sdamgia.ru/formula/svg/b8/b80d21c698524c6e465ad73be2c2718a.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/46/469451398a39e16c7f1216dbc07959d1.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/b8/b80d21c698524c6e465ad73be2c2718a.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/ff/ff12a85a9f410bf7bdd77925709294e0.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/a2/a20ab28ef56a6f51dd900226e7fc4713.svg)

![Рисунок](https://ege.sdamgia.ru/get_file?id=19580)

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