.04 Пары/тройки чисел, выбрать из каждой, кратность

Метод минимальных разностей

f = open(’27B.txt’)  # Открываем нужный файл
n = int(f.readline())

k = [3, 20]  # список чисел, одному из которых должна быть кратна итоговая сумма
mr = [[10 ** 10] * j for j in k]  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для максимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += max(a, b)  # Прибавляем к сумме максимальное число из пары
    r = abs(a - b)  # Разность между элементами

    for q in range(2):  # Рассматриваем разности для двух чисел отдельно
        new_mr = mr[q][:]  # Создаём копию списка разностей
        for j in range(k[q]):
            # Ищем минимальную сумму нескольких разностей
            if r + new_mr[j] < mr[q][(r + new_mr[j]) % k[q]]:
                mr[q][(r + new_mr[j]) % k[q]] = r + new_mr[j]

        # Если текущая разность меньше разности в списке
        if r < mr[q][r % k[q]]:
            mr[q][r % k[q]] = r

ans = 0  # Переменная для ответа
# Если сумма в итоге кратна одному из чисел
if s % k[0] == 0 or s % k[1] == 0:
    ans = s  # Сохраняем сумму
else:  # Иначе отнимаем от макс. суммы разность с таким же остатком
    ans = max(ans, s - mr[0][s % k[0]])
    ans = max(ans, s - mr[1][s % k[1]])

print(ans)

Метод частичных сумм

f = open(’27B.txt’)
n = int(f.readline())
ans = [0] * (3*20)

for i in range(n):
    a = [int(i) for i in f.readline().split()]

    ans_new = [-1000000000] * 60

    for k in range(len(a)):
        for j in range(60):
            ost = (ans[j] + a[k]) % 60
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]

    ans = ans_new

print(max([i for i in ans if i % 3 == 0 or i % 20 == 0]))