Дана последовательность из 
целых положительных чисел. Необходимо определить максимальное произведение пары элементов этой последовательности, произведение которой кратно 
, а сумма кратна 
.
В первой строке входных данных задаётся количество чисел N (1 
N 
10000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В ответе укажите два числа через пробел: сначала искомое произведение для файла A, а затем для файла B.
Решение 1 (неэффективное)
f = open("3.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
for j in range(i + 1, n):
if ((a[i] * a[j]) % 15 == 0) and ((a[i] + a[j]) % 53 == 0):
ans = max(ans, a[i] * a[j])
print(ans)
Решение 2 (эффективное)
file = open(’3.txt’, ’rt’)
n = int(file.readline())
max_kr_15 = [0] * 53
max_kr_5 = [0] * 53
max_kr_3 = [0] * 53
max_nekr = [0] * 53
ans = 0
for i in range(n):
x = int(file.readline())
ost = x % 53
dop = (53 - ost) % 53
if x % 15 == 0:
maxim = max(max_kr_15[dop], max_kr_5[dop],
max_kr_3[dop], max_nekr[dop])
ans = max(ans, x * maxim)
max_kr_15[ost] = max(max_kr_15[ost], x)
elif x % 5 == 0:
maxim = max(max_kr_15[dop], max_kr_3[dop])
ans = max(ans, x * maxim)
max_kr_5[ost] = max(max_kr_5[ost], x)
elif x % 3 == 0:
maxim = max(max_kr_15[dop], max_kr_5[dop])
ans = max(ans, x * maxim)
max_kr_3[ost] = max(max_kr_3[ost], x)
else:
ans = max(ans, x * max_kr_15[dop])
max_nekr[ost] = max(max_nekr[ost], x)
print(ans)
Решение 3 (эффективное)
f = open(’2_B.txt’)
k = 53
p = 15
# Делители числа p
d = [15, 5, 3, 1]
n = int(f.readline())
# Создаём список, где индексы элемента nums[x][y] обозначают следующее:
# x - индекс делителя числа p, на которое делится элемент
# y - остаток от деления элемента на k
# Элементами же списка являются максимальные числа,
# делящиеся на определенный делитель числа p
# и имеющие определенный остаток от деления на k
nums = [[-10 ** 10] * k for _ in range(p + 1)]
mx = -10 ** 10
for i in range(n):
x = int(f.readline())
# Вычисляем остаток от деления на k числа-пары для x
ost = (k - (x % k)) % k
# Ищем наибольший делитель, на который делится x
for j in d:
if x % j == 0:
# Обновляем максимум, умножая x на самое большое число,
# при умножении x на которое их произведение будет кратно p
mx = max(mx, x * nums[p // j][ost])
break
# Заполняем список максимальных чисел nums
for j in d:
if x % j == 0:
# Если x больше предыдущего числа кратному dl с таким же
# остатком от деления на k - обновляем число в списке
nums[j][x % k] = max(nums[j][x % k], x)
print(mx)