На вход программы поступает последовательность из N натуральных чисел. Необходимо найти такую пару различных элементов последовательности, находящихся на расстоянии не менее 4, чтобы их произведение было максимально и кратно 3, сумма кратна 8 и хотя бы один элемент пары был больше 30.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 
100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.
В ответе укажите два числа: сначала значение произведения искомой пары для файла А, затем для файла B.
Решение 1 (неэффективное)
f = open("16_A.txt")
n = int(f.readline())
a = [int(i) for i in f]
ans = -10 ** 10
for i in range(n):
for j in range(i + 1, n):
if a[i] * a[j] % 3 == 0 and (a[i] + a[j]) % 8 == 0:
if (a[i] > 30 or a[j] > 30) and j - i >= 4:
ans = max(ans, a[i] * a[j])
print(ans)
Решение 2 (эффективное)
f = open(’27.txt’)
kr_3 = [[0] * 8, [0] * 8] # первая ячейка --- > или <= 30, вторая ячейка --- остатки от деления на 8
nekr_3 = [[0] * 8, [0] * 8]
n = int(f.readline())
line = []
for i in range(3):
line.append(int(f.readline()))
ans = 0
for i in range(n - 3):
x = int(f.readline())
dop = (8 - x % 8) % 8
# числа больше 30 можно использовать всегда, поэтому используем if только для тех, что <= 30
ans = max(ans, kr_3[0][dop] * x, nekr_3[0][dop] * x * (x % 3 == 0))
if x > 30:
ans = max(ans, kr_3[1][dop] * x, nekr_3[1][dop] * x * (x % 3 == 0))
t = line[i % 3]
if t % 3 == 0:
kr_3[t <= 30][t % 8] = max(t, kr_3[t <= 30][t % 8])
else:
nekr_3[t <= 30][t % 8] = max(t, nekr_3[t <= 30][t % 8])
line[i % 3] = x
print(ans)
Решение 3 (эффективное)
f = open(’16_B.txt’)
s = 4 # Расстояние между элементами
k = 8 # Чему должна быть кратна сумма
p = 3 # Чему должно быть кратно произведение
n = int(f.readline())
a = [int(i) for i in f]
# Список с максимальными числами, удовлетворяющими определенным условием
# Индексы числа nums[x][y][z] обозначают следующее:
# x - больше ли число чем 30 (1 - да, 0 - нет)
# y - кратно ли число 3 (1 - да, 0 - нет)
# z - остаток от деления числа на k
nums = [[[-10 ** 10] * k for _ in range(2)] for _ in range(2)]
ans = -10 ** 10
for i in range(s, n):
# Находим остаток первого числа пары
ost1 = a[i - s] % k
# Обновляем число в списке с такими же характеристиками
nums[int(a[i - s] > 30)][int(a[i - s] % 3 == 0)][ost1] = max(
nums[int(a[i - s] > 30)][int(a[i - s] % 3 == 0)][ost1],
a[i - s]
)
# Вычисляем остаток от деления на k числа-пары для x
ost2 = (k - (a[i] % k)) % k
ans = max(ans, a[i] * nums[1][1][ost2])
if a[i] % 3 == 0:
ans = max(ans, a[i] * nums[1][0][ost2])
if a[i] > 30:
ans = max(ans, a[i] * nums[0][0][ost2])
if a[i] > 30:
ans = max(ans, a[i] * nums[0][1][ost2])
print(ans)