Дан набор из N целых положительных чисел. Из них нужно выбрать и вывести два числа так, чтобы их сумма была нечётна, а произведение делилось на 3 и при этом было максимально возможным. Выбранные числа можно выводить в любом порядке. Если есть несколько подходящих пар, можно выбрать любую из них. Если подходящих пар нет, нужно вывести 0.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 100.
Пример входных данных:
5
1
2
3
4
5
Пример выходных данных для приведённого выше примера входных данных:
3 4
Из 5 чисел можно составить 10 пар. В данном случае условиям удовлетворяют две пары: (2, 3) и (3, 4). Суммы чисел в этих парах (5 и 7) нечётны, а произведения (6 и 12) делятся на 3. У всех остальных пар как минимум одно из этих условий не выполняется. Из двух возможных пар выводим ту, в которой больше произведение элементов.
Разобьём все числа исходного набора на 4 группы в зависимости от их чётности и делимости на 3:
m1 нечётные числа, не кратные 3;
m2 чётные числа, не кратные 3;
m3 нечётные числа, кратные 3;
m6 чётные числа, кратные 3.
Чтобы сумма двух чисел было нечётной, одно из них должно быть чётным, а другое — нечётным. Чтобы произведение двух чисел делилось на 3, хотя бы одно из этих чисел должно делиться на 3. Таким образом, нужно выбрать два числа из групп m1 и m6, или из групп m2 и m3, или из групп m3 и m6. Чтобы получить пару с максимальным произведением, достаточно сохранить максимальный элемент из каждой группы, сравнить соответствующие произведения и выбрать из них наибольшее.
Сами числа при этом можно не хранить, достаточно при вводе определить остаток от деления очередного числа на 2 и на 3, сравнить число с текущим максимумом соответствующей группы и при необходимости обновить этот максимум и увеличить соответствующий счётчик. Таким образом, независимо от количества чисел в исходном наборе, после чтения исходных данных для хранения необходимой информации хватит 4 переменных, и программа получится эффективной по памяти.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).
Пример правильной и эффективной программы на языке Паскаль:
var
N: integer; {количество чисел}
a: integer; {очередное число}
m1: integer; {нечётные, не кратные 3}
m2: integer; {чётные, не кратные 3}
m3: integer; {нечётные, кратные 3}
m6: integer; {чётные, кратные 3}
x, y: integer; {выбранная пара}
i: integer;
begin
m1 := 0; m2 := 0; m3 := 0; m6 := 0;
readln(N);
for i:=1 to N do begin
readln(a);
if a mod 2 = 0 then begin
if a mod 3 = 0 then begin
if a>m6 then m6 := a
end
else begin
if a>m2 then m2 := a
end
end
else begin
if a mod 3 = 0 then begin
if a>m3 then m3 := a
else begin
if a>m1 then m1 := a
end
end
end;
end;
x := m1; y := m6;
if m2*m3 > x*y then begin
x := m2; y := m3;
end;
if m3*m6 > x*y then begin
x := m3; y := m6;
end;
if x*y = 0
then writeln(0)
else writeln(x, ' ', y);
end.
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и подсчитаем количество подходящих. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше двух баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример правильной, но неэффективной программы на языке Паскаль
var
N: integer; {количество чисел}
a: array [1..1000] of integer; {исходные данные}
x, y: integer; {выбранная пара}
i, j: integer;
begin
readln(N);
for i := 1 to N do readln(a[i]);
x := 0; y := 0;
for i := 1 to N − 1 do begin
for j := i + 1 to N do begin
if ((a[i] + a[j]) mod 2 = 1) and ((a[i]*a[j]) mod 3 = 0) and (a[i]*a[j] > x*y) then begin
x := a[i]; y := a[j];
end
end
end;
if x = 0
then writeln(0)
else writeln(x, ' ', y);
end.
Приводим эффективное решение Николая Артюхина на C++.
#include <iostream>
using namespace std;
int main()
{
int n, i, mch3=0, mch=0, mnch3=0, mnch=0,m1=0, m2=0, x;
cin >> n;
for(i=0;i<n;i++){
cin >> x;
if (x%2==0){
if ((x%3==0)&&(x>mch3)){
if(mch3>mch) mch = mch3;
mch3=x;
}
else if (x>mch) mch=x;
}
else{
if((x%3==0)&&(x>mnch3)) {
if(mnch3>mnch) mnch=mnch3;
mnch3=x;
}
else if (x>mnch) mnch=x;
}
}
if(mnch3*mch3>m1*m2){
m1=mnch3;
m2=mch3;
}
if(mch3*mnch>m1*m2){
m1=mch3;
m2=mnch;
}
if(mnch3*mch>m1*m2){
m1=mnch3;
m2=mch;
}
cout << m1 << " " << m2;
return 0;
}