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

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

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

mr = [10 ** 10] * (7 * 10)  # Список для хранения минимальных разностей по остаткам
maxS = 0  # Максимальная сумма чисел
for i in range(n):
    a, b, c = sorted(map(int, f.readline().split()))  # Считываем числа по возрастанию
    maxS += b + c  # Прибавляем к сумме два наибольших числа из пары
    r1 = b - a  # Разность между ср. и мин. числами
    r2 = c - a  # Разность между макс. и мин. числами

    for r in r1, r2:  # Перебираем разности
        mr1 = mr[:]  # Создаём копию списка разностей
        for j in range(70):
            # Ищем минимальную сумму нескольких разностей
            if r + mr1[j] < mr[(r + mr1[j]) % 70]:
                mr[(r + mr1[j]) % 70] = r + mr1[j]

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

# Сумма делится на оба числа
if maxS % 7 == 3 and maxS % 10 == 5:
    # Нужно найти такую мин. разность, которая изменит только один остаток:
    # либо остаток от деления на 7, либо остаток от деления на  10
    d = 10 ** 10
    for j in range(70):
        count = 0  # Количество чисел, на которое делится сумма
        if (maxS - mr[j]) % 7 != 3:
            count += 1
        if (maxS - mr[j]) % 10 != 5:
            count += 1
        if count == 1:  # Если сумма не делится на одно число, запоминаем разность
            d = min(mr[j], d)

    maxS -= d  # Прибавляем итоговую мин. разность

                                                                                                     
                                                                                                     
# Сумма не делится ни на одно число
elif maxS % 7 != 3 and maxS % 10 != 5:
    # Также нужно найти мин. разность, которая даст кратность только одному числу
    d = 10 ** 10
    for j in range(70):
        count = 0  # Количество чисел, на которое делится сумма
        if (maxS - mr[j]) % 7 == 3:
            count += 1
        if (maxS - mr[j]) % 10 == 5:
            count += 1
        if count == 1:  # Если сумма делится на одно число, запоминаем разность
            d = min(mr[j], d)

    maxS -= d  # Прибавляем итоговую мин. разность

print(maxS)  # Выводим итоговую сумму выбранных чисел

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

# Поледняя цифра числа x в СС по основанию n равна x%n,
# поэтому нам надо найти числа,
# которые имеют остаток 5 по модулю 10 или 3 по модулю 7

# Так как 7 и 10 взаимно простые, все числа,
# дающие разные пары остатков при делении на 10 и 7,
# имеют разные остатки при делении на 70,
# поэтому найдем все макссуммы для всех остатков по модулю 70

modul = 70


def fun(a, a_new, x):
    for j in range(modul):
        k = (a[j] + x) % modul
        a_new[k] = max(a_new[k], a[j] + x)


a = [-100000000000000000] * modul
a[0] = 0
f = open(’30.txt’)
n = int(f.readline())
for i in range(n):
    x, y, z = map(int, f.readline().split())
    a_new = [-100000000000000000] * modul
    fun(a, a_new, x + y)
    fun(a, a_new, y + z)
    fun(a, a_new, x + z)
    for j in range(modul):
        a[j] = a_new[j]

# Создадим массив b, в который поместим минсуммы
# с только интересными нам остатками
# Числа, с остатком 45 при делении на 70 оканчиваются
# на 5 в 10СС и на 3 в 7СС, пропустим их
b = []
for i in range(7):
    if i != 4:
                                                                                                     
                                                                                                     
        b.append(a[10 * i + 5])
for i in range(10):
    if i != 6:
        b.append(a[i * 7 + 3])
print(max(b))