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

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

f = open("27B.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)

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

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

k = 13  # Число, которому должна быть кратна сумма
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())
s = [0]#массив,в котором будут храниться суммы промежуточные каждой строки
for i in range(n):
    pair = [int(x) for x in f.readline().split()]#разбиение строки на пары чисел
    s = [a+b for a in s for b in pair]#всевозможные суммы на строке
    s ={x % 13:x for x in sorted(s)}.values()#словарь,в котором ключ- это остаток числа на 13,значение это
    #отсортированные по возрастанию всевозможные суммы на этой строке
print(max(x for x in s if x % 13 == 0))

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

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 += 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 = 13
smax = [0]*k
#в smax содержится 13 элементов
#первый элемент — максимальная сумма, делящаяся на 13 без остатка
#второй элемент — максимальная сумма, которая при делении на 13 дает остаток 1 и тд
for i in range (n):
    troyka = list(map(int,f.readline().split()))
    sums = [x+y for x in smax for y in troyka]

    smax_temp = [0]*k
    for x in sums:
        smax_temp[x % k] = max(smax_temp[x % k],x)

    smax = [x for x in smax_temp if x != 0]

print(smax[0])

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

f = open("27B.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)

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

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

k = 7
smax = [0]*k
# в smax содержится 1 элементов
# первый элемент — максимальная сумма, делящаяся на 7 без остатка
# второй элемент — максимальная сумма, которая при делении на 7 дает остаток 1 и тд
for i in range(n):
    para = list(map(int, f.readline().split()))
    sums = [x+y for x in smax for y in para]

    smax_temp = [0]*k
    for x in sums:
        smax_temp[x % k] = max(smax_temp[x % k],x)

    smax = [x for x in smax_temp if x != 0]

print(smax[0])

f = open(’3_B.txt’)  # для ответа на A требуется подключить 3_A.txt
n = int(f.readline())  # Считываем количество пар из первой строки
s = 0  # Инициализируем переменную для хранения суммы
mr = [10000005000000] * 8  # Cписок минимальных остатков от деления на 8
for i in range(n):  # Проходим по каждой тройке чисел
    a, b, c = map(int, f.readline().split())  # Считываем тройку чисел
    mx = max(a, b, c)
    mn = min(a, b, c)
    md = a + b + c - mx - mn  # Находим максимальное, минимальное и среднее числа
    d1 = mx - md
    d2 = mx - mn  # Вычисляем разности для двух возможных минимальных разностей
    s += mx  # Добавляем максимальное число к сумме
    mr1 = mr[:]  # Создаем копию списка ’mr’
    # Проходим по каждому остатку от деления на 8 для первой разности
    for j in range(8):
        # Если сумма разности и элемента списка меньше чем элемент списка
        if d1 + mr1[j] < mr[(d1 + mr1[j]) % 8]:  # по остатку от деления
            # Заменяем элемент списка на сумму разности и элемента
            mr[(d1 + mr1[j]) % 8] = d1 + mr1[j]
    # Проходим по каждому остатку от деления на 8 для второй разности
    for j in range(8):
        # Если сумма разности и элемента списка меньше чем элемент списка
        if d2 + mr1[j] < mr[(d2 + mr1[j]) % 8]:
            # Заменяем элемент списка на сумму разности и элемента
            mr[(d2 + mr1[j]) % 8] = d2 + mr1[j]
    # Заменяем элемент списка по остатку на минимум между элементом и
    mr[d1 % 8] = min(mr[d1 % 8], d1)  # разностью для обеих разностей
    mr[d2 % 8] = min(mr[d2 % 8], d2)
if s % 8 != 0:  # Если сумма не делится на 8 без остатка
    s -= mr[s % 8]  # Вычитаем из суммы минимальный остаток
print(s)

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

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

k = 17 # Число, которому должна быть кратна сумма
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("27A.txt") # Открываем файл
n = int(f.readline())

k = 17
smax = [0]*k
#в smax содержится 1 элементов
#первый элемент — максимальная сумма, делящаяся на 17 без остатка
#второй элемент — максимальная сумма, которая при делении на 17 дает остаток 1 и тд
for i in range (n):
    para = list(map(int,f.readline().split()))
    sums = [x+y for x in smax for y in para]

    smax_temp = [0]*k
    for x in sums:
        smax_temp[x % k] = max(smax_temp[x % k],x)

    smax = [x for x in smax_temp if x != 0]

print(smax[0])

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

f = open("27B.txt")
n = int(f.readline())
k = 6  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список минимальных разностей
s = 0  # Максимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z = sorted(map(int, f.readline().split()))
    s += z + y  # Прибавляем 2 наибольших числа тройки
    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[s % k]

print(s)

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 6, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 6 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 6 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/5_A.txt’)
n = int(f.readline())
sm = 0
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*6
for i in range(n):
    nums = list(map(int, f.readline().split()))
    # Собираем в отдельном списке суммы из всевозможных пар из тройки
    pairs = []
    for j in range(len(nums)):
        for k in range(j+1, len(nums)):
            pairs.append(nums[j]+nums[k])
    # Временный массив с суммами.
    m_new = [0] * 6
    # Перебор разных сумм со всеми суммами пар из тройки.
    # Суммы из m будут сравниваться между собой посредством условий.
    for t in range(6):
        for p in pairs:
            if m[t] + p > m_new[(m[t] + p) % 6]:
                m_new[(m[t] + p) % 6] = m[t] + p
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят максимальное, не кратное 6.
# Значит берём максимальное из m[1:]
print(m[1:])

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

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)
    # обновляем минимальную разницу НЕ кратную 28
    if (abs(a-b) < mr) and (abs(a-b) % 28 != 0):
        mr = abs(a-b)
# если результирующая сумма получилась кратной 28, то отнимаем разницу
if s % 28 == 0:
    s -= mr
print(s)

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

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)
    # обновляем минимальную разницу НЕ кратную 2
    if (abs(a-b) < mr) and (abs(a-b) % 2 != 0):
        mr = abs(a-b)
# если результирующая сумма получилась кратной 2, то прибавляем разницу
if s % 2 == 0:
    s += mr
print(s)

f = open(’27a.txt’)
n = int(f.readline())
r = [100000000000]*5
s = 0
for i in range(n):
    a, b = map(int, f.readline().split())
    s += max(a, b)
    d = abs(a - b)
    r1 = r[:]
    for j in range(5):
        if d+r1[j] < r1[(d+r1[j]) % 5]:
            r[(d + r1[j]) % 5] = d+r1[j]
    if d < r[d % 5]:
        r[d % 5] = d
if s % 5 != 0:
    s -= r[s % 5]
print(s)

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

Идея решения:

Будем составлять из всех троек 3 суммы: первая будет состоять из максимальных чисел, вторая - из средних чисел, третья - из минимальных чисел.

Обозначим их как , и .

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

Рассмотрим 3 случая неподходящих сумм:

• чётна, чётна
• нечётна, чётна
• чётна, нечётна

В первом случае будет идеально, если между суммами и будет любая нечётная разность между максимальным числом и средним числом. В таком случае можно будет их поменять местами, тогда обе суммы станут нечётны, не затрагивая сумму .

Однако нужно учесть вариант, что такой разности может и не быть. Тогда рассмотрим, какие разности можно прибавить к минимальной сумме . Будем расписывать подходящие для замены виды троек по остаткам максимального, среднего и минимального числа соответственно, то есть по их позициям 1, 2 и 3:

• 
• 

В таких тройках можно будет менять минимальное число и с максимальным, и со средним для изменения чётности. Но так как мы хотим увеличить сумму как можно меньше, то будем делать в таких случаях замену только со средним числом. Тогда тройки изменятся на следующий вид:

• 
• 

Если сделать 1 такую замену, то сумма станет нечётна, а также в такой тройке появится возможность поменять первое и второе число в этой тройке, так как их разность станет нечётна. В итоге, чтобы обе суммы стали нечётны, достаточно сделать в двух тройках замену среднего числа на минимальное. Тогда сумма останется чётна (два раза изменили её остаток на 1), а также появятся две тройки с нечётными разностями для замены первого числа на второе. Таким образом, сделав замену только в одной из двух таких троек, получим нечётные суммы и .

Во втором случае сумму уже трогать не нужно, нужно только сделать замену между суммами и , чтобы сумма стала нечётна. Тогда подойдут тройки следующего вида, где – любой остаток:

• 
• 

То есть нужно сохранить все нечётные разности между средним и минимальным числом, чтобы только в одной тройке сделать замену минимальной разностью.

В третьем случае для идеальной замены распишем виды подходящих троек, где – любой остаток:

• 
• 

Среди них выделим тройки следующего вида:

• 
• 

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

Если расписывать подробно, то будут произведены следующие замены попарно:

• → →
• → →

Если же тройки следующего вида:

• 
• 

То тогда можно сделать только замену между минимальным и максимальным числом.

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

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

mr12 = 0
mr23_110_001 = []  # Если r12 чётна, будем сохранять нечётные r23
mr13_100_011 = []  # Если r12 нечётна, будем сохранять нечётные r13
mr23_010_101 = []  # Если r12 нечётна, будем сохранять нечётные r23

s1 = 0  # Первая "нечётная" сумма
s2 = 0  # Вторая "нечётная" сумма
s3 = 0  # Третья минимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z = sorted(map(int, f.readline().split()))
    s1 += z  # Прибавляем максимальное число
    s2 += y  # Прибавляем среднее число
    s3 += x  # Прибавляем минимальное число

    r12 = z - y  # Разность для возможной перестановки ср. и макс. чисел
    r23 = y - x  # Разность для возможной замены ср. числа на мин. число
    r13 = z - x  # Разность для возможной замены макс. числа на мин. число

    if r12 % 2 == 1:  # Перестановка z,y в s1 и s2 поменяет чётность обеих сумм
        mr12 = r12
        if r13 % 2 == 1:
            mr13_100_011.append(r13)
        if r23 % 2 == 1:
            mr23_010_101.append(r23)
    elif r23 % 2 == 1:  # Заменять мин. число в таких тройках выгодно только на ср. число
        mr23_110_001.append(r23)

# Обе суммы не подходят, а разность mr12 не нашлась
if s1 % 2 == 0 and s2 % 2 == 0 and mr12 == 0:
    for _ in range(2):  # Берём разность 2 раза
        r = min(mr23_110_001)  # Берём минимальную разность
        mr23_110_001.remove(r)  # Убираем её из списка разностей
        s3 += r

# Только вторая сумма не подходит
elif s1 % 2 != 0 and s2 % 2 == 0:
    mr23_x10_x01 = mr23_010_101 + mr23_110_001  # Создаём обший список подходящих разностей
    r = min(mr23_x10_x01)  # Находим минимальную подходящую разность
                                                                                                  
                                                                                                  
    s3 += r

# Только первая сумма не подходит
elif s1 % 2 == 0 and s2 % 2 != 0:
    mr13_1x0_0x1 = mr13_100_011 + mr23_110_001  # Создаём обший список подходящих разностей
    r = min(mr13_1x0_0x1)  # Находим минимальную подходящую разность
    s3 += r

print(s3)

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

from itertools import permutations
f = open(’27b.txt’)
n = int(f.readline())
groupes = [[0,0,0]]
for t in f:
    new_groupes = []
    for last_groupe in groupes:
        s1,s2,s3 = last_groupe
        for a,b,c in permutations(list(map(int,t.split()))):
            new_groupes.append((s1+a,s2+b,s3+c) )
    groupes = {(x[1] % 2,x[2] % 2):x for x in sorted(new_groupes, reverse=True)}.values()
for s1,s2,s3 in groupes:
    if s2 % 2 != 0 and s3 % 2 != 0:
        print(s1)

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 9, чтобы остаток суммы поменялся
    if (d1 < mr) and (d1 % 9 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 9 != 0):
        mr = d1

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

print(s)

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 11, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 11 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 11 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/5A.txt’)
n = int(f.readline())
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*11
for i in range(n):
    x, y, z = list(map(int, f.readline().split()))
    # Временный массив с суммами.
    m_new = [0] * 11
    # Перебор разных сумм со всеми числами из тройки.
    # Суммы будут сравниваться между собой посредством условий.
    for t in range(11):
        if m[t] + x > m_new[(m[t] + x) % 11]:
            m_new[(m[t] + x) % 11] = m[t] + x

        if m[t] + y > m_new[(m[t] + y) % 11]:
            m_new[(m[t] + y) % 11] = m[t] + y

        if m[t] + z > m_new[(m[t] + z) % 11]:
            m_new[(m[t] + z) % 11] = m[t] + z
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят максимальное, не кратное 11.
# Значит берём максимальное из m[1:]
print(max(m[1:]))

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 100, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 100 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 100 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/6A.txt’)
n = int(f.readline())
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*100
for i in range(n):
    x, y, z = list(map(int, f.readline().split()))
    # Временный массив с суммами.
    m_new = [0] * 100
    # Перебор разных сумм со всеми числами из тройки.
    # Суммы будут сравниваться между собой посредством условий.
    for t in range(100):
        if m[t] + x > m_new[(m[t] + x) % 100]:
            m_new[(m[t] + x) % 100] = m[t] + x

        if m[t] + y > m_new[(m[t] + y) % 100]:
            m_new[(m[t] + y) % 100] = m[t] + y

        if m[t] + z > m_new[(m[t] + z) % 100]:
            m_new[(m[t] + z) % 100] = m[t] + z
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят максимальное, не кратное 100.
# Значит берём максимальное из m[1:]
print(max(m[1:]))

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 5, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 5 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 5 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/7A.txt’)
n = int(f.readline())
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*5
for i in range(n):

    x, y, z = list(map(int, f.readline().split()))
    # Временный массив с суммами.
    # Изначально выставляем большое значение,
    # чтобы в самом начале проставились суммы из m
    # вне зависимости от их значения.
    # Далее суммы будут сравниваться между собой посредством условий.
    m_new = [10**10] * 5
    # Перебор разных сумм со всеми числами из тройки
    for t in range(5):
        if m[t] + x < m_new[(m[t] + x) % 5]:
            m_new[(m[t] + x) % 5] = m[t] + x

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

        if m[t] + z < m_new[(m[t] + z) % 5]:
            m_new[(m[t] + z) % 5] = m[t] + z
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят минимальное, не кратное 5.
# Значит берём минимальное из m[1:]
print(min(m[1:]))

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 12, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 12 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 12 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/8A.txt’)
n = int(f.readline())
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*12
for i in range(n):
    x, y, z = list(map(int, f.readline().split()))
    # Временный массив с суммами.
    # Изначально выставляем большое значение,
    # чтобы в самом начале проставились суммы из m
    # вне зависимости от их значения.
    # Далее суммы будут сравниваться между собой посредством условий.
    m_new = [10**10] * 12
    # Перебор разных сумм со всеми числами из тройки
    for t in range(12):
        if m[t] + x < m_new[(m[t] + x) % 12]:
            m_new[(m[t] + x) % 12] = m[t] + x

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

        if m[t] + z < m_new[(m[t] + z) % 12]:
            m_new[(m[t] + z) % 12] = m[t] + z
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят минимальное, не кратное 12.
# Значит берём минимальное из m[1:]
print(min(m[1:]))

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 113, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 113 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 113 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/9B.txt’)
n = int(f.readline())
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*113
for i in range(n):
    x, y, z = list(map(int, f.readline().split()))
    # Временный массив с суммами.
    # Изначально выставляем большое значение,
    # чтобы в самом начале проставились суммы из m
    # вне зависимости от их значения.
    # Далее суммы будут сравниваться между собой посредством условий.
    m_new = [10**10] * 113
    # Перебор разных сумм со всеми числами из тройки
    for t in range(113):
        if m[t] + x < m_new[(m[t] + x) % 113]:
            m_new[(m[t] + x) % 113] = m[t] + x

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

        if m[t] + z < m_new[(m[t] + z) % 113]:
            m_new[(m[t] + z) % 113] = m[t] + z
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят минимальное, не кратное 113.
# Значит берём минимальное из m[1:]
print(min(m[1:]))

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

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

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна 18, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % 18 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 18 != 0):
        mr = d1

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

print(s)

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

f = open(’D:/10B.txt’)
n = int(f.readline())
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*18
for i in range(n):
    x, y, z = list(map(int, f.readline().split()))
    # Временный массив с суммами.
    m_new = [0] * 18
    # Перебор разных сумм со всеми числами из тройки.
    # Суммы будут сравниваться между собой посредством условий.
    for t in range(18):
        if m[t] + x > m_new[(m[t] + x) % 18]:
            m_new[(m[t] + x) % 18] = m[t] + x

        if m[t] + y > m_new[(m[t] + y) % 18]:
            m_new[(m[t] + y) % 18] = m[t] + y

        if m[t] + z > m_new[(m[t] + z) % 18]:
            m_new[(m[t] + z) % 18] = m[t] + z
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят максимальное, не кратное 18.
# Значит берём максимальное из m[1:]
print(max(m[1:]))

f = open(’1.txt’)
n = int(f.readline())
krat = 13
mr = [100000000500000000]*krat
s = 0
for i in range(n):
    a,b = map(int, f.readline().split())
    s += min(a, b)
    d = abs(a-b)
    mr1 = mr[:] #копия mr
    for j in range(krat):
        #берем разность и складываем с каждым элементом списка mr1
        #сравниваем получившуюся сумму с mr
        #если она меньше, то записываем данную сумму в mr
        if d + mr1[j] < mr[(d+mr[j]) % krat]:
            mr[(d+mr[j]) % krat] = d + mr1[j]
    #проверка, что если разность меньше соответствующего элемента в списке
    #то записываем эту разность в список
    if d < mr[d % krat]:
        mr[d % krat] = d

#Если сумма s не делится на krat, то сумма корректируется
#путем добавления значения из mr[krat - s % krat]
if s % krat != 0:
    s += mr[krat - s % krat]
print(s)