Задание № 7596
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание – 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Перед программой укажите версию языка программирования.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
11
12
45
5
3
17
23
21
20
19
18
17
Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:
54
Содержание верного ответа
Задание Б (решение для задания А приведено ниже, см. программу 4). Чтобы произведение было чётным, хотя бы один сомножитель должен быть чётным, поэтому при поиске подходящих произведений чётные показания прибора можно рассматривать в паре с любыми другими, а нечётные – только с чётными.
Для каждого показания с номером k, начиная с k = 7, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k – 6. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное – только чётным.
Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 6 элементов ранее, и выбрать минимальное из всех таких произведений.
Поскольку каждое текущее минимальное показание используется после ввода ещё 6 элементов и после этого становится ненужным, достаточно хранить только 6 последних минимумов. Для этого можно использовать массив из 6 элементов и циклически заполнять его по мере ввода данных. Размер этого массива не зависит от общего количества введённых показаний, поэтому такое решение будет эффективным не только по времени, но и по памяти. Чтобы хранить абсолютный и чётный минимумы, нужно использовать два таких массива.
Ниже приводится пример такой программы, написанной на языке Паскаль.
const s = 6; {требуемое расстояние между показаниями}
amax = 1001; {больше максимально возможного показания}
var
N: integer;
a: array[1..s] of integer; {хранение s показаний прибора}
a_: integer; {ввод очередного показания}
ma: integer; {минимальное число без s последних}
me: integer; {минимальное чётное число без s последних}
mp: integer; {минимальное значение произведения}
p: integer;
i, j: integer;
begin
readln(N);
{Ввод первых s чисел}
for i:=1 to s do readln(a[i]);
{Ввод остальных значений, поиск минимального произведения}
ma := amax; me := amax;
mp :=amax*amax;
for i := s + 1 to N do begin
readln(a_);
if a[1] < ma then ma := a[1];
if (a[1] mod 2 = 0) and (a[1] < me) then me := a[1];
if a_ mod 2 = 0 then p := a_ * ma
else if me < amax then p := a_ * me
else p := amax* amax;
if (p < mp) then mp := p;
{сдвигаем элементы вспомогательного массива влево}
for j := 1 to s - 1 do
a[j] := a[j + 1];
a[s] := a_
end;
if mp = amax*amax then mp:=-1;
writeln(mp)
end.Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.