По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наименьшее число R, удовлетворяющее следующим условиям:
1) R является произведением двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R кратно 6.
Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения.
Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: …
Контроль пройден (или — Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N;
в программе можно считать, что 2 ≤ N ≤ 10 000. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение — натуральное число, не превышающее 1 000 000.
Пример входных данных:
6
30
6
5
3
4
300
12
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 12
Контроль пройден
Произведение двух чисел делится на 6, если:
− один из сомножителей делится на 6 (второй может быть любым), либо
− ни один из сомножителей не делится на 6, причём один из сомножителей делится на 2, а другой — на 3.
Поэтому программа, вычисляющая контрольное число, может работать так. Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырех величин:
М2 — самое маленькое чётное число, не кратное 3;
М3 — самое маленькое число, кратное 3, но не кратное 2;
М6 — самое маленькое число, кратное 6;
MIN — самое маленькое число среди всех элементов последовательности, отличное от M6 (если число М6 встретилось более одного раза и оно же является минимальным, то MIN = M6).
После того как все данные прочитаны, искомое контрольное слово вычисляется как минимум из произведений M6*MIN и М2*М3.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Пример правильной и эффективной программы на языке Паскаль:
Program C4;
var
M2, M3, M6, MIN, dat: integer;
R, res, i, N: longint;
begin
M2 := 1001; M3 := 1001; M6 := 1001; MIN := 1001;
readln(N);
for i := 1 to N do
begin
readln(dat);
if (dat mod 2 = 0) and (dat mod 3 > 0) and (dat < M2) then M2 := dat;
if (dat mod 3 = 0) and (dat mod 2 > 0) and (dat < M3) then M3 := dat;
if (dat mod 6 = 0) and (dat < M6) then
begin
if M6 < MIN then MIN := M6;
M6:= dat;
end
else
if dat < MIN then MIN:= dat;
end;
if (M2*M3 > M6*MIN) then res := M6*MIN else res := M2*M3;
if (M6 >= 1001) and ((M2 >= 1001) or (M3 >= 1001)) then res := 0;
writeln('Вычисленное контрольное значение: ',res);
readln(R);
if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден');
end.