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

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

f = open(’29.txt’)
n = int(f.readline())

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

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

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

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

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

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

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

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

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

# Так как 3 и 17 взаимно простые, все числа,
# дающие разные пары остатков при делении на 3 и 17,
# имеют разные остатки при делении на 51,
# поэтому найдем все минсуммы для всех остатков по модулю 51
# и выберем только те значения, которые кратны или 3 или 17

modul = 51


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


a = [100000000000000000] * modul
a[0] = 0
f = open(’29.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, в который поместим минсуммы
# с только интересными нам остатками
b = []
for i in range(1,17):
    b.append(a[3*i])    # Все, кратные 3, но не 17
for i in range(1,3):
    b.append(a[i*17])   # Все, кратные 17, но не 3
print(min(b))