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

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

f = open(’B5-8.txt’)
n = int(f.readline())

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

    # Если новая разность меньше текущей минимальной разности
    if (r < mr) and (r % k != 0):
        mr = r

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

print(s)

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

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

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

    # Если новая разность меньше текущей минимальной разности
    if (r < mr) and (r % k != 0):
        mr = r

if s % k == 0:  # Если в итоге сумма кратна k
    s += mr  # К мин. сумме прибавляем минимальную разность для изменения остатка

print(s)

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

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

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

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

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

# Если сумма в итоге не кратна k
if s % k != 0:
    # Прибавляем к мин. сумме разность с недостающим остатком
    s += mr[k - s % k]

print(s)

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

f = open(’B5-8.txt’)  # Открываем нужный файл
n = int(f.readline())
ans = 0  # Переменная для максимальной суммы
diff = 10000000000  # Минимальная разность, некратная 2
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans += max(a)  # Прибавляем максимальное число к сумме
    if abs(a[0] - a[1]) % 2 == 1:  # Если разность чисел некратна 2
        diff = min(diff, abs(a[0] - a[1]))  # Пробуем сохранить разность
if ans % 2 == 1:  # Если сумма в итоге некратна 2
    ans -= diff  # Вычитаем некратную разность, чтобы сумма в итоге стала кратной
print(ans)

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

# Примечание: если число кратно 3, то оно будет кратно 6. Так что будем искать только кратность 3.
f = open(’27B.txt’)  # Открываем нужный файл
n = int(f.readline())

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

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

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

# Если сумма в итоге не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком
    s -= mr[s % k]

print(s)

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

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

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

    ans_new = [-1000000000] * 3

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

    ans = ans_new

print(ans[0])

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

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]))

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

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

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

print(ans)

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

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

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

    ans_new = [-1000000000] * 60

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

    ans = ans_new

print(max([i for i in ans if i % 3 == 0 or i % 20 == 0]))

По китайской теореме об остатках гарантируется, что при перемножении взаимнопростых чисел найдется сумма, которая будет иметь какой-то остаток при делении на произведение и при этом будет кратно лишь одному из чисел, указанных в произведении.

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

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

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

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

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

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

    maxS -= d  # Вычитаем итоговую мин. разность

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

    maxS -= d  # Вычитаем итоговую мин. разность

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

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

n = int(input())
ans = [0]*(5*11)

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

    ans_new = [-1000000000]*55

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

    ans = ans_new

print(max(max([i*(i % 5 == 0 and i % 11 != 0) for i in ans]), \
          max([i*(i % 5 != 0 and i % 11 == 0) for i in ans])
          ))

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

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

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

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

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

# Обе суммы не удовлетворяют условию
if maxS % 5 == 0 and minS % 3 == 0:
    # Находим среди минимальных разностей по остаткам такую минимальную разность,
    # которая не будет кратна ни 3, ни 5, чтобы поменять остаток обеих сумм
    d = min(mr[j] for j in range(15) if (mr[j] % 5 != 0) and (mr[j] % 3 != 0))
    # Отнимаем разность от максимальной суммы и прибавляем к минимальной
    maxS -= d
    minS += d

# Сумма невыбранных чисел не удовлетворяет условию
elif maxS % 5 != 0 and minS % 3 == 0:
    # Остаток для максимальной суммы, вычитание которого даст кратность 5
    ost5 = maxS % 5
    # Находим среди минимальных разностей по остаткам такую минимальную разность,
    # которая не будет кратна 3, чтобы поменять остаток минимальной суммы,
    # и при этом остаток которой не будет равен ost5, чтобы не сделать макс. сумму кратной 5
                                                                                                     
                                                                                                     
    d = min(mr[j] for j in range(15) if (mr[j] % 5 != ost5) and (mr[j] % 3 != 0))
    # Отнимаем разность от максимальной суммы и прибавляем к минимальной
    maxS -= d
    minS += d

# Сумма выбранных чисел не удовлетворяет условию
elif maxS % 5 == 0 and minS % 3 != 0:
    # Остаток для минимальной суммы, прибавление которого даст кратность 3
    ost3 = 3 - minS % 3
    # Находим среди минимальных разностей по остаткам такую минимальную разность,
    # которая не будет кратна 5, чтобы поменять остаток максимальной суммы,
    # и при этом остаток которой не будет равен ost3, чтобы не сделать мин. сумму кратной 3
    d = min(mr[j] for j in range(15) if (mr[j] % 5 != 0) and (mr[j] % 3 != ost3))
    # Отнимаем разность от максимальной суммы и прибавляем к минимальной
    maxS -= d
    minS += d

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

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

#Для решения задачи будем искать макс. суммы с остатками по модулю 5
#и смотреть на их остатки по модулю 3 -
#чтобы сравнить с остатком суммы всех чисел.
#Если окажется, что эти остатки равны, то сумма нам не подходит
#(так как тогда (sum_all - current_sum) % 3 == 0, и надо смотреть на другую.
#Поэтому надо собрать суммы с разными парами остатков по модулю 5 и 3,
#а все такие суммы будут иметь разные остатки по модулю 3*5 = 15

modul = 15

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 = [0] * modul
n = int(input())
sum_all = 0
for i in range(n):
    x, y = map(int, input().split())
    a_new = [-100000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    sum_all += x + y
    a = a_new[:]
print(max([i for i in a if (i % 5 != 0 and i % 3 != sum_all % 3)]))

Неэффективный переборный алгоритм для малых N

f = open(’27.txt’)
n = int(f.readline())
a = []
minim = 10000000000000000
for i in range(n):
    a.append([int(x) for x in f.readline().split()])
for i in range(2 ** n):
    num = i
    s = 0
    for j in range(n):
        s += a[j][num % 2]
        num //= 2
    if s < minim and s % 8 == 0:
        minim = s
print(minim)

Эффективный алгоритм

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

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

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

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

# Если сумма в итоге не кратна k
if s % k != 0:
    # Прибавляем к мин. сумме разность с недостающим остатком
    s += mr[k - s % k]

print(s)

Неэффективный переборный алгоритм для малых N

f = open(’27.txt’)
n = int(f.readline())
a = []
maxim = -1
for i in range(n):
    a.append([int(x) for x in f.readline().split()])
for i in range(2 ** n):
    num = i
    s = 0
    for j in range(n):
        s += a[j][num % 2]
        num //= 2
    if s > maxim and s % 7 == 0:
        maxim = s
print(maxim)

Эффективный алгоритм

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

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

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

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

# Если сумма в итоге не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком
    s -= mr[s % k]

print(s)

Неэффективный переборный алгоритм для малых N

f = open(’27.txt’)
n = int(f.readline())
a = []
maxim = -1
for i in range(n):
    a.append([int(x) for x in f.readline().split()])
for i in range(3 ** n):
    num = i
    s = 0
    for j in range(n):
        s += a[j][num % 3]
        num //= 3
    if s > maxim and s % 17 == 0:
        maxim = s
print(maxim)

Эффективный алгоритм

f = open(’27.txt’)  # Открываем нужный файл
n = int(f.readline())
k = 17  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список минимальных разностей
s = 0  # Максимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z = sorted(map(int, f.readline().split()))
    s += z  # Прибавляем наибольшее число тройки
    d1 = z - y  # Разность для возможной замены на макс. числа на ср. число
    d2 = z - x  # Разность для возможной замены на макс. числа на мин. число

    mr1 = mr[:]  # Копия списка разностей
    # Перебираем обе разности
    for d in d1, d2:
        # Составляем суммы нескольких разностей для получения различных остатков
        for j in range(k):
            if d + mr1[j] < mr[(d + mr1[j]) % k]:
                mr[(d + mr1[j]) % k] = d + mr1[j]
        # Если сама по себе разность меньше, то заменяем соответствующую разность
        if d < mr[d % k]:
            mr[d % k] = d

# Если сумма по итогу оказалась не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком,
    # чтобы в итоге остаток стал равен 0
    s -= mr[s % k]

print(s)

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

f = open(’27B.txt’)
n = int(f.readline())
k = 6  # Число, которому сумма не должна быть кратна
mr = 10 ** 10  # Минимальная разность
s = 0  # Максимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z, w = sorted(map(int, f.readline().split()))
    s += w  # Прибавляем наибольшее число из четвёрки
    d1 = w - z  # Разность для возможной замены на макс. числа на предмакс. число
    d2 = w - y  # Разность для возможной замены на макс. числа на предмин. число
    d3 = w - x  # Разность для возможной замены на макс. числа на мин. число

    for d in d1, d2, d3:  # Перебираем разности
        # Если разность d меньше минимальной разности mr,
        # и при этом d не кратно k для изменения остатка
        if (d < mr) and (d % k != 0):
            mr = d

if s % k == 0:  # Если сумма по итогу оказалась кратна k
    s -= mr  # Отнимаем от максимальной суммы минимальную разность

print(s)

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

f = open(’27B.txt’)
n = int(f.readline())

k = 6
smax = [0] * k #здесь будут храниться максимальные суммы для каждого из остатков при делении на 6
               #первый элемент — макс.сумма, которая при делении на 6 дает остаток 0
               #второй элемент — макс.сумма, которая при делении на 6 дает остаток 1
               #третий элемент — макс.сумма, которая при делении на 6 дает остаток 2 и так далее

for i in range(n):
    # Сохраним здесь числа из текущей четвёрки
    quart = list(map(int, f.readline().split()))
    # Формируем суммы с текущими числами
    sums = [x + y for x in smax for y in quart]

    # Копируем smax во временную переменную smax_temp для сравнения сумм
    smax_temp = smax.copy()
    # Сравниваем получившиеся суммы с суммами из smax_temp, записываем результат
    for x in sums:
        smax_temp[x % k] = max(smax_temp[x % k], x)
    # Копируем получившийся список в smax
    smax = smax_temp.copy()
    print(smax)
a = smax.pop(0) #удаляем первый элемент, так как у него остаток 0 при делении на 6
print(max(smax))

Идея решения: Так как нужно получить минимальную сумму, то будем выбирать из каждой пары минимальное число, не обращая внимания на кратность. Если итоговая сумма получилась кратной 5, то необходимо заменить одно выбранное число другим числом из пары, при этом заменить нужно так, чтобы итоговая сумма увеличилась минимально. Для этого на каждом шаге будем сохранять минимальную разницу между элементами пары, такую что разница не кратна 5, потому что если разница будет кратна 5, то замена не даст другой кратности у итоговой суммы.

f = open(’1.txt’)
n = int(f.readline())
s = 0
# переменная для хранения минимальной разницы между числами пары
mr = 1000000500000
for i in range(n):
    # считываем числа
    a, b = map(int, f.readline().split())
    # для того чтобы итоговая сумма получилась минимальной берем минимальное из пары
    s += min(a, b)
    # обновляем минимальную разницу НЕ кратную 5
    if (abs(a-b) < mr) and (abs(a-b) % 5 != 0):
        mr = abs(a-b)
# если результирующая сумма получилась кратной 5, то прибавляем разницу
if s % 5 == 0:
    s += mr
print(s)

file = open(’27_B.txt’)  # Открываем нужный файл
n = int(file.readline())  # Считываем первое число
ans = 0  # Переменная, в которой будем складывать максимальные числа из каждой пары
for i in range(n):
    ans += max(map(int, file.readline().split()))  # Прибавляем макс. число к ans из текущей пары чисел
print(ans)

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

f = open("../27B.txt")  # Открываем нужный файл
n = int(f.readline())
k = 13  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список минимальных разностей
s = 0  # Минимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z = sorted(map(int, f.readline().split()))
    s += x  # Прибавляем наименьшее число тройки
    d1 = y - x  # Разность для возможной замены на мин. числа на ср. число
    d2 = z - x  # Разность для возможной замены на мин. числа на макс. число

    mr1 = mr[:]  # Копия списка разностей
    # Перебираем обе разности
    for d in d1, d2:
        # Составляем суммы нескольких разностей для получения различных остатков
        for j in range(k):
            if d + mr1[j] < mr[(d + mr1[j]) % k]:
                mr[(d + mr1[j]) % k] = d + mr1[j]
        # Если сама по себе разность меньше, то заменяем соответствующую разность
        if d < mr[d % k]:
            mr[d % k] = d

# Если сумма по итогу оказалась не кратна k
if s % k != 0:
    # Прибавляем к мин. сумме разность с недостающим остатком,
    # чтобы в итоге остаток стал равен 0
    s += mr[k - s % k]

print(s)

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

f = open(’27_A.txt’)
n = int(f.readline())
m = [10000000000] * 13
m[0] = 0
pair = 0,0
for i in range(n):
    x, y, z = list(map(int, f.readline().split()))
    m_new = [10000000000] * 13
    for t in range(13):
        if m[t] + x < m_new[(m[t] + x) % 13]:
            m_new[(m[t] + x) % 13] = m[t] + x

        if m[t] + y < m_new[(m[t] + y) % 13]:
            m_new[(m[t] + y) % 13] = m[t] + y

        if m[t] + z < m_new[(m[t] + z) % 13]:
            m_new[(m[t] + z) % 13] = m[t] + z

    m = m_new.copy()
print(m[0])

Идея решения: Так как нужно получить максимальную сумму, то будем выбирать из каждой пары максимальное число, не обращая внимания на кратность. Если итоговая сумма получилась кратной 8, то необходимо заменить одно выбранное число другим числом из пары, при этом заменить нужно так, чтобы итоговая сумма уменьшилась минимально. Для этого на каждом шаге будем сохранять минимальную разницу между элементами пары, такую что разница не кратна 8, потому что если разница будет кратна 8, то замена не даст другой кратности у итоговой суммы.

f = open(’1.txt’)
n = int(f.readline())
s = 0
# переменная для хранения минимальной разницы между числами пары
mr = 1000000500000
for i in range(n):
    # считываем числа
    a, b = map(int, f.readline().split())
    # для того чтобы итоговая сумма получилась максимальной берем максимальное из пары
    s += max(a, b)
    # обновляем минимальную разницу НЕ кратную 8
    if (abs(a-b) < mr) and (abs(a-b) % 8 != 0):
        mr = abs(a-b)
# если результирующая сумма получилась кратной 8, то отнимаем разницу
if s % 8 == 0:
    s -= mr
print(s)

Идея решения: Так как нужно получить минимальную сумму, то будем выбирать из каждой пары минимальное число, не обращая внимания на кратность. Если итоговая сумма получилась кратной 3, то необходимо заменить одно выбранное число другим числом из пары, при этом заменить нужно так, чтобы итоговая сумма увеличилась минимально. Для этого на каждом шаге будем сохранять минимальную разницу между элементами пары, такую что разница не кратна 3, потому что если разница будет кратна 3, то замена не даст другой кратности у итоговой суммы.

f = open(’1.txt’)
n = int(f.readline())
s = 0
# переменная для хранения минимальной разницы между числами пары
mr = 1000000500000
for i in range(n):
    # считываем числа
    a, b = map(int, f.readline().split())
    # для того чтобы итоговая сумма получилась минимальной берем минимальное из пары
    s += min(a, b)
    # обновляем минимальную разницу НЕ кратную 3
    if (abs(a-b) < mr) and (abs(a-b) % 3 != 0):
        mr = abs(a-b)
# если результирующая сумма получилась кратной 3, то прибавляем разницу
if s % 3 == 0:
    s += mr
print(s)

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

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

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

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

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

# Если сумма в итоге не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком
    s -= mr[s % k]

print(s)

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

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

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

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

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

# Если сумма в итоге не кратна k
if s % k != 0:
    # Прибавляем к мин. сумме разность с недостающим остатком
    s -= mr[k - s % k]

print(s)