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

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

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

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

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

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

if s % 5 == 4:  # Если в итоге сумма в 5-ричной СС оканчивается на 4
    s -= mr  # От макс. суммы отнимаем минимальную разность для изменения остатка

print(s)

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

modul = 5


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(’14.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(max(a[:4]))