По каналу связи передавалась последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно. Затем передаётся контрольное значение последовательности — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 14.
Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Программа должна напечатать одно число — вычисленное контрольное значение, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Пример организации исходных данных во входном файле:
6
77
14
7
9
499
100
Пример выходных данных для приведённого выше примера входных данных:
7700
В ответе укажите два числа: сначала значение искомое контрольное значение для файла А, затем для файла B.
Ответ:
Произведение двух чисел делится на 14, если:
— один из сомножителей делится на 14 (второй может быть любым) либо
— ни один из сомножителей не делится на 14. причём один из сомножителей делится на 2, а другой — на 7.
Поэтому программа, вычисляющая кодовое число, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырех величин:
М2 — самое большое чётное число, не кратное 7;
М7 — самое большое число, кратное 7. но не кратное 2;
М14 — самое большое число, кратное 14;
МАХ — самое большое число среди всех элементов последовательности, отличное от M14 (если число М14 встретилось более одного раза и оно же является максимальным, то МАХ = M14).
После того как все данные прочитаны, искомое кодовое слово вычисляется как максимум из произведений M14*МАХ и М2*М7.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы. Допускаются решения, записанные на других языках программирования.
Приведём решение задачи на языке Pascal.
var M2, M7, M14, MAX, dat, res, N: longint; f: text;
begin
M2 := 0; M7 := 0; M14 := 0; MAX := 0;
assign(f,'27985_A.txt');
reset(f);
readln(f, N);
while not eof(f) do begin
readln(f, dat);
if ((dat mod 2) = 0) and ((dat mod 7) >0) and (dat > M2) then M2 := dat;
if ((dat mod 7) = 0) and ((dat mod 2) > 0) and (dat > M7) then M7 := dat;
if (dat mod 14 = 0) and (dat > M14) then begin
if M14 > MAX then MAX := M14;
M14 := dat;
end
else
if dat > MAX then MAX := dat;
end;
if (M2*M7 < M14 *MAX) then
res := M14*MAX
else
res := M2*M7;
writeln(res);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 719740, из файла B — 994000.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.