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

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

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

k = [7, 10]  # список чисел, одному из которых должна быть кратна итоговая сумма
mr = [[10 ** 10] * j for j in k]  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для минимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += min(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 = 10 ** 10  # Переменная для ответа
# Если сумма в итоге кратна одному из чисел
if s % k[0] == 0 or s % k[1] == 0:
    ans = s  # Сохраняем сумму
else:  # Иначе прибавляем к мин. сумме разность с недостающим остатком
    if s % k[0] != 0:
        ans = min(ans, s + mr[0][k[0] - s % k[0]])
    if s % k[1] != 0:
        ans = min(ans, s + mr[1][k[1] - s % k[1]])

print(ans)

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

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

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

    ans_new = [1000000000000] * 70

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

    ans = ans_new

print(min([i for i in ans if i % 10 == 0 or i % 7 == 0]))