Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 19. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
5
38
12
57
16
57
Пример выходных данных для приведённого выше примера входных данных:
57 57
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (38, 12), (38, 16), (57, 57). Наибольшая сумма получается в паре (57, 57). Эта пара допустима, так как число 57 встречается в исходной последовательности дважды.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, — 4 балла. Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти.
var
N: integer;
a: integer;
i: integer;
max: array [0..1] of integer;
max19: array [0..1] of integer;
begin
max[0] := 0;
max[1] := 0;
max19[0] := 0;
max19[1] := 0;
readln(N);
for i := 1 to N do
begin
readln(a);
if (a mod 19 = 0) and (a mod 2 = 0) and (a >= max19[0]) then begin
if max19[0] > max[0] then max[0] := max19[0];
max19[0] := a;
end
else if (a mod 19 = 0) and (a mod 2 = 1) and (a >= max19[1]) then begin
if max19[1] > max[1] then max[1] := max19[1];
max19[1] := a;
end
else if (a mod 19 > 0) and (a mod 2 = 0) and (a > max[0]) then max[0] := a
else if (a mod 19 > 0) and (a mod 2 = 1) and (a > max[1]) then max[1] := a;
end;
if (max[0] = 0) or (max19[0] = 0) then begin
max[0] := 0;
max19[0] := 0;
end;
if (max[1] = 0) or (max19[1] = 0) then begin
max[1] := 0;
max19[1] := 0;
end;
if (max[0] + max19[0]) > (max[1] + max19[1]) then writeln(max[0], ' ', max19[0])
else writeln(max[1], ' ', max19[1]);
end.