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

Сумма чисел оканчивается на C в 13-ричной системе счисления, если остаток суммы при делении на 13 равен 12.

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

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

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

    # Если найдена новая минимальная разность, не кратная 13,
    # то в конце можно будет её прибавить к сумме для изменения остатка
    if (r < mr) and (r % 13 != 0):
        mr = r

if s % 13 == 12:  # Если в итоге сумма в 13-ричной СС оканчивается на ’C’ (то есть 12)
    s += mr  # К мин. сумме прибавляем минимальную разность для изменения остатка

print(s)

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

modul = 13


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(’16.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]

print(min(a[:12]))