Условие задачи
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
5
34
12
51
52
51
Пример выходных данных для приведённого выше примера входных данных:
51 51
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.
Напишите эффективную по времени и памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Ответ
Разность двух чисел четна, если оба числа одинаковой четности. Максимальная сумма элементов получится, если оба элемента будут максимальными.
Программа читает числа и запоминает в переменную max17_0 наибольшее четное, кратное 17, в max0 – наибольшее четное, не совпадающее с max17_0, в max17_1 - наибольшее нечетное, кратное 17, в max1 – наибольшее нечетное, не совпадающее с max17_1.
Сумма двух целых положительных чисел наибольшая, если наибольшее их произведение, поэтому программа сравнивает произведения (max17_0 * max0) и (max17_1 * max1) и множители большего произведения запоминает в переменные a и b.
В последовательности участвуют только положительные числа, поэтому стартовые значения переменных равны нулю.
Пример правильной и эффективной программы на языке Паскаль:
var max17_0, max0, max17_1, max1, i, n, dat, a, b : int;
begin
max17_0 := 0; {четный максимум кратный 17}
max0 :=0; {четный максимум}
max17_1 :=0; {нечетный максимум кратный 17}
max1 :=0; {нечетный максимум}
a:=0;
b:=0;
readln(n); {ввод количества чисел последовательности}
for i := 1 to n do
begin
readln(dat); {ввод очередного числа}
if (dat mod 2 = 0) then
if (dat mod 17 = 0) and (dat > max17_0) then begin
if (max17_0 > max0) then
max0 :=max17_0;
max17_0 := dat
end
else
if dat > max0 then
max0 := dat;
if (dat mod 2 <> 0) then
if (dat mod 17 = 0) and (dat > max17_1) then begin
if (max17_1 > max1) then
max1 :=max17_1;
max17_1 := dat
end
else
if dat > max1 then
max1 := dat
end;
if (max17_0 * max0 = 0) and (max17_1 * max1 = 0) then begin {не нашлось таких пар}
a:=0;
b:=0
end
else
if (max17_0 * max0 > max17_1 * max1) then begin
a:= max17_0;
b:=max0
end
else begin
a:= max17_1;
b:=max1
end;
writeln(a, ' ', b)
end.
