27.07 Макс/мин, кол-во пар, смешаное кратно/не кратно

Решение 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)