Форум: «ЕГЭ по информатике»

Дан набор из N целых положительных чисел. Из них нужно выбрать и вывести два числа так, чтобы их сумма была нечётна, а произведение делилось на 5 и при этом было максимально возможным. Выбранные числа можно выводить в любом порядке. Если есть несколько подходящих пар, можно выбрать любую из них. Если подходящих пар нет, нужно вывести 0.

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 100.

Пример входных данных:

5

1

2

4

5

7

Пример выходных данных для приведённого выше примера входных данных:

4 5

Из 5 чисел можно составить 10 пар. В данном случае условиям удовлетворяют две пары: (2, 5) и (4, 5). Суммы чисел в этих парах (7 и 11) нечётны, а произведения (10 и 20) делятся на 5. У всех остальных пар как минимум одно из этих условий не выполняется. Из двух возможных пар выводим ту, в которой больше произведение элементов.

Решение:
n=int(input())
a=[[0]*2,[0]*2]
b=[]
max_n=0
for i in range(n):
x=int(input())
ch=x%2 #признак четности
k5=x%5 #признак кратности 5
if k5>0:
k5=1
if a[ch][k5]<x:
a[ch][k5]=x
for i in range(2):
for j in range(2):
b.append((a [ i] [j]))
for i in range(len(b)-1):
for j in range(i+1,len(b)):
if (b [ i]+b[j])%2!=0 and b [ i]*b[j]%5==0 and b[ i]*b[j]>max_n:
max_n=b[ i]*b[j]
x1=b[ i]
x2=b[ j]
if max_n==0:
print(0)
else:
print(x1,x2)

for i in range(2):
for j in range(2):
b.append((a [ i] [j]))
for i in range(len(b)-1):
for j in range(i+1,len(b)):
if (b [ i]+b[j])%2!=0 and b [ i]*b[j]%5==0 and b[ i]*b[j]>max_n:
max_n=b[ i]*b[j]
x1=b[ i]
x2=b[ j]