По каналу связи каждую минуту передаётся положительное целое число, все числа не превышают 1000.Количество чисел известно и не превышает 10 000.Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить минимальное кратное 3 произведение двух чисел, между моментами передачи которых прошло не менее 5 минут. Если такое значение не удаётся получить, то вывести 0.
Описание входных и выходных данных.
В первой строке задаётся число N —общее количество передаваемых чисел. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число. Программа должна вывести одно число — описанное в условии произведение либо 0, если получить такое произведение не удаётся.
Пример входных данных:
12
4
22
15
3
9
11
14
20
21
17
16
18
Пример выходных данных для приведённого выше примера входных данных:
48
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N чисел. Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чиселN, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,— 4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Первые 6 введённых чисел положим в массив. Перед вводом каждого следующего числа проверим, является ли текущий элемент массива меньше предыдущего минимума (индекс текущего элемента массива —это порядковый номер введённого числа, делённый по модулю на 6). Сохраняем в отдельных переменных минимумы для чисел, кратных 3, и для чисел, не кратных 3.
Считываем следующее число последовательности. Сохраняем его в массиве на месте текущего элемента, т. к. мы уже проверили, является ли текущий элемент минимальным, и если является, то сохранили его в отдельной переменной.
Вычислим два произведения: введённое число, умноженное на минимум, кратный 3, и введённое число, умноженное на минимум, не кратный 3. Полученные произведения проверим на кратность 3.
Каждое из полученных произведений, кратное 3, сравним с текущим минимальным произведением, если новое произведение меньше текущего минимума, заменяем текущий минимум на новый.
Повторяем указанную процедуру до окончания ввода последовательности.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
const T = 6; {минимальное время между передачами}
var min, min3, {минимальный элемент, не кратный 3 и кратный 3}
p_min, {минимальное произведение}
p, {произведение элементов, один из которых кратен 3}
p3, {произведение элементов, каждый из которых кратен 3}
x, K, S, i ,j,
N: integer; {количество чисел в последовательности}
a: array[1..T] of integer; {значения шести последовательных чисел}
begin
min:=1001;
min3:=1001;
readln(N);
K:=(N-T) div T;
S:=(N-T) mod T;
p_min:=1001*1001;
p:=1001*1001;
p3:=1001*1001;
for i:=1 to T do
readln(a[i]);
{просматриваем по 5 идущих подряд элементов}
for j:=1 to K do
for i:=1 to T do begin {просматриваем
последовательность из Т элементов}
if (a[i] mod 3 <> 0) and (a[i] min:=a[i]; {находим наименьший
не кратный 3 из просмотренных}
if (a[i] mod 3 = 0) and (a[i] min3:=a[i]; {находим наименьший
кратный 3 из просмотренных}
readln(x);
a[i]:=x; {текущий элемент помещаем в массив
вместо уже просмотренного}
{находим наименьшее произведение, кратное 3, составленное из просмотренных элементов}
p3:=x*min3;
if x mod 3= 0 then p:=x*min;
if (p3
if (p3< p_min) then p_min:=p3;
end
else if (p end;
{просматриваем оставшиеся в последовательности элементы, выполняя те же действия, что и в предыдущем цикле}
for i:=1 to S do begin
if (a[i] mod 3 <> 0) and (a[i] min:=a[i];
if (a[i] mod 3 = 0) and (a[i] min3:=a[i];
readln(x);
a[i]:=x;
p3:=x*min3;
if x mod 3= 0 then
p:=x*min;
if (p3
if (p3 p_min:=p3;
end
else if (p p_min:=p;
end;
writeln(p_min);
end.