На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента (это время известно заранее) прибор каждую минуту передаёт в обсерваторию по каналу связи положительное целое число, не превышающее 1000, — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах.
После окончания эксперимента передаётся контрольное значение — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух чисел, переданных в разные минуты;
2) R делится на 26.
Необходимо найти такое число R. Предполагается, что удовлетворяющее условиям контрольное значение существовало в момент передачи. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Если удовлетворяющее условию контрольное значение определить невозможно, то выводится число 0.
На вход программе в первой строке подаётся количество чисел 1 < N ≤ 100 000. В каждой из последующих N строк записано одно положительное целое число, не превышающее 1000.
Входные данные.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Пример организации исходных данных во входном файле:
5
52
12
39
55
23
Пример выходных данных для приведённого выше примера входных данных:
2860
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Ответ:
Можно заметить, что 26 = 13 · 2. Поэтому ответом является наибольшее из двух произведений:
a) максимальное нечетное число, кратное 13, умноженное на максимальное четное число из оставшихся;
b) максимальное число, кратное 26, умноженное на максимальное число из оставшихся.
Чтобы не взять в произведении одно и тоже число, можно хранить номер их поступления.
Если вдруг найдем повторяющиеся значения по этому номеру (например, на тесте из 3 элементов 52, 5 и 7 значение максимума и максимального числа кратного 26 совпадает), то найдем предмаксимумы для обоих случаев и возьмем более выгодный из них.
Приведём решение задачи на языке Pascal.
var
n, i, a, max2, max13, max26, max, predmax: integer;
index2, index13, index26, indexmax, ans, ans1, ans2: integer;
f: text;
begin
max:=0;
max26:=0;
max13:=0;
max2:=0;
ans:=0;
ans1:=0;
ans2:=0;
assign(f,'27988_A.txt');
reset(f);
readln(f, n);
for i := 1 to n do begin
readln(f, a);
if (a mod 13 = 0) and (a > max13) then begin
max13 := a;
index13 := i;
end;
if (a mod 2 = 0) and (a > max2) then begin
max2 := a;
index2 := i;
end;
if (a mod 26 = 0) and (a > max26) then begin
max26 := a;
index26 := i;
end;
if (a >= max) then begin
predmax:=max;
max := a;
indexmax := i;
end;
if(a < max) and (a >= predmax) then
predmax := a;
end;
if(index2 <> index13) then
ans1 := max2 * max13;
if(index26 <> indexmax) then
ans2 := max * max26
else
ans2 := predmax * max26;
if(ans1 > ans2) then
ans := ans1
else
ans := ans2;
writeln(ans);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 783900, из файла B — 988000.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.