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

Будем собирать максимальную сумму, а потом посмотрим, что получится с остатками.

Если все хорошо, то так и выведем. Если где-то нарушена четность - заводим специальную переменную,

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

• у наибольшего числа 0, у меньшего - 1;
• у наибольшего 1, у меньшего - 0;
• оба числа нечетные.

Останется тогда из суммы с неверным остатком (возможно из обеих) вычесть нужную комбинацию минимальных сумм.

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

sMax = 0
sMin = 0
md01 = 10000000000000000
md10 = 10000000000000000
md11 = 10000000000000000

for i in range(n):
    x, y = map(int, f.readline().split())
    if x % 2 == 1:
        maxim = max(x, y)
        minim = min(x, y)
        sMax += maxim
        sMin += minim
        if maxim % 2 == 0 and minim % 2 == 1:
            md01 = min(md01, x + y)
        if maxim % 2 == 1 and minim % 2 == 0:
            md10 = min(md10, x + y)
        if maxim % 2 == 1 and minim % 2 == 1:
            md11 = min(md11, x + y)

if sMax % 2 == 1 and sMin % 2 == 0:
    print(sMax + sMin)
elif sMax % 2 == 1 and sMin % 2 == 1:
    # Обратим внимание, что остатки 01 может иметь
    # как пара с соответствующими остатками,
    # так и две пары с остатками 10 и 11. Учтем это
    print(sMax + sMin - min(md01, md10 + md11))
elif sMax % 2 == 0 and sMin % 2 == 0:
    # Аналогично 10 = 11 + 01
    print(sMax + sMin - min(md10, md11 + md01))
elif sMax % 2 == 0 and sMin % 2 == 1:
    # Аналогично 11 = 10 + 01
    print(sMax + sMin - min(md11, md10 + md01))

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

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 - чтобы сравнить с остатком суммы всех чисел.
# Если окажется, что эти остатки равны, то сумма нам не подходит
# (так как тогда summ_all - current_summ % 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 = [-100000000000000000] * modul
a[0] = 0
f = open(’22.txt’)
n = int(f.readline())
summ_all = 0
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)
    summ_all += x + y
    for j in range(modul):
        a[j] = a_new[j]

print(max([i for i in a if (i % 5 != 0 and i % 3 != summ_all % 3)]))

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

f = open(’23.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 += x + y  # Прибавляем два наименьших числа тройки
    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

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

print(s)

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

modul = 6


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(’23.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]

print(a[0])

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

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

# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*4
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] * 4
    # Перебор разных сумм со всеми суммами пар из тройки.
    # Суммы из m будут сравниваться между собой посредством условий.
    for t in range(4):
        for p in pairs:
            if m[t] + p > m_new[(m[t] + p) % 4]:
                m_new[(m[t] + p) % 4] = m[t] + p
    # Сохраняем получившийся массив в m
    m = m_new.copy()
# Просят максимальное, кратное 4.
# Значит выводим m[0]
print(m[0])

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

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

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

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

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

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

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

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

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

• 
• 

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

• 
• 

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

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

• 
• 

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

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

• 
• 

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

• 
• 

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

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

• → →
• → →

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

• 
• 

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

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

f = open(’27.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 += x  # Прибавляем минимальное число
    s2 += y  # Прибавляем среднее число
    s3 += z  # Прибавляем максимальное число

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

    if r12 % 2 == 1:  # Перестановка x,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(’27.txt’)
n = int(f.readline())
s = [[0,0,0]]
for i in range(n):
    tr = [int(x) for x in f.readline().split()]
    s = [[a1+b1, a2+b2, a3+b3] for a1, a2, a3 in s for b1, b2, b3 in permutations(tr)]
    s = {(x[1]%2, x[2]%2): x for x in sorted(s)}.values()
for a3, a2, a1 in s:
    if a2 % 2 == 0 and a1 %2 == 0:
        print(a3)

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

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

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

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

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

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

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

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

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

• 
• 

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

• 
• 

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

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

• 
• 

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

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

• 
• 

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

• 
• 

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

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

• → →
• → →

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

• 
• 

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

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

f = open(’26.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  # Прибавляем максимальное число

    r23 = y - x  # Разность для возможной замены ср. числа на мин. число
    r12 = z - y  # Разность для возможной перестановки ср. и макс. чисел
    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(’26.txt’)
n = int(f.readline())
s = [[0,0,0]]
for i in range(n):
    tr = [int(x) for x in f.readline().split()]
    s = [[a1+b1, a2+b2, a3+b3] for a1, a2, a3 in s for b1, b2, b3 in permutations(tr)]
    s = {(x[1]%2, x[2]%2): x for x in sorted(s, reverse=True)}.values()
for a3, a2, a1 in s:
    if a2 % 2 == 0 and a1 %2 == 0:
        print(a3)

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

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

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

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

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

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

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

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

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

• 
• 

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

• 
• 

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

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

• 
• 

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

• 
• 

Здесь придётся сделать замену максимального числа на минимальное, тогда суммы и станут чётными. Между ними, как в первом случае, останется сделать перестановку среднего и минимального числа в другой тройке.

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

• 
• 

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

• 
• 

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

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

• → →
• → →

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

• 
• 

В этих тройках, аналогично 2 случаю, можно сделать замену среднего числа на максимальное, а далее перестановку среднего и минимального чисел в другой тройке.

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

f = open(’27.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 += x  # Прибавляем минимальное число
    s2 += y  # Прибавляем среднее число
    s3 += z  # Прибавляем максимальное число

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

    if r12 % 2 == 1:  # Перестановка x,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) or (s1 % 2 == 0 and s2 % 2 != 0):
    mr = mr13_100_011 + mr23_010_101 + mr23_110_001  # Создаём обший список подходящих разностей
    r = min(mr)  # Находим минимальную подходящую разность
    s3 -= r

print(s3)

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

from itertools import permutations

f = open(’27.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)}.values()
for s1,s2,s3 in groupes:
    if s2 % 2 != 0 and s3 % 2 != 0:
        print(s1)

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

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

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

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

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

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

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

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

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

• 
• 

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

• 
• 

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

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

• 
• 

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

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

• 
• 

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

• 
• 

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

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

• → →
• → →

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

• 
• 

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

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

f = open(’28.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) or (s1 % 2 == 0 and s2 % 2 != 0):
    mr = mr13_100_011 + mr23_010_101 + mr23_110_001  # Создаём обший список подходящих разностей
    r = min(mr)  # Находим минимальную подходящую разность
    s3 += r

print(s3)

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

from itertools import permutations
f = open(’28.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(’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))

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

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

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

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

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

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

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

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

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

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

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

# Поледняя цифра числа x в СС по основанию n равна x%n,
# поэтому нам надо найти числа,
# которые имеют остаток 5 по модулю 10 или 3 по модулю 7

# Так как 7 и 10 взаимно простые, все числа,
# дающие разные пары остатков при делении на 10 и 7,
# имеют разные остатки при делении на 70,
# поэтому найдем все макссуммы для всех остатков по модулю 70

modul = 70


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(’30.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, в который поместим минсуммы
# с только интересными нам остатками
# Числа, с остатком 45 при делении на 70 оканчиваются
# на 5 в 10СС и на 3 в 7СС, пропустим их
b = []
for i in range(7):
    if i != 4:
                                                                                                     
                                                                                                     
        b.append(a[10 * i + 5])
for i in range(10):
    if i != 6:
        b.append(a[i * 7 + 3])
print(max(b))

f = open(’1.txt’)
n = int(f.readline())
krat = 2
mr = [100000000500000000]*krat
s = 0
for i in range(n):
    a,b = map(int, f.readline().split())
    s += max(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[s % krat]
if s % krat != 0:
    s -= mr[s % krat]
print(s)

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

f = open(’D:/ege/10_B.txt’)  # Открываем нужный файл
n = int(f.readline())

k = 16  # Число, которому должна быть кратна сумма
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)

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

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

# Список для сумм с определённым остатком
a = [-100000000] * 16
a[0] = 0

f = open(’D:/ege/10_B.txt’)
n = int(f.readline())
for i in range(n):
    s = f.readline()
    if len(s) > 0:
        x, y = map(int, s.split())
        a_new = [-100000000] * 16
        # Функция для перебора сумм
        fun(a, a_new, x)
        fun(a, a_new, y)
        # Сохраняем сумму
        for j in range(16):
            a[j] = a_new[j]
print(a[0])

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

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

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

f = open(’27_6A.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)

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

def f(a, a_new, k):
    for j in range(3):
        cur_summ = a[j] + k
        ost = cur_summ % 3
        if cur_summ > a_new[ost]:
            a_new[ost] = cur_summ

h = open(’1.txt’)
a = [-10000000] * 3
a[0] = 0
n = int(h.readline())
for i in range(n):
    x, y = map(int, h.readline().split())
    a_new = [-100000000] * 3
    f(a, a_new, x)
    f(a, a_new, y)
    for j in range(3):
        a[j] = a_new[j]
print(a[0])

f = open(’1.txt’)
n = int(f.readline())
krat = 17
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)

f = open(’Задание_27_A__k3bv.txt’)
n = int(f.readline())
sum = 0
big = 0
small = 0
m10, m11, m01 = 10**9, 10**9, 10**9
for i in range(n):
    x, y = [int(s) for s in f.readline().split()]
    if x % 2 == 0:
        x, y = min(x, y), max(x, y)
        sum += x + y
        big += y
        small += x
        if y % 2 == 1:
            if x % 2 == 1:
                m11 = min(m11, x + y)
            else:
                m10 = min(m10, x + y)
        else:
            if x % 2 == 1:
                m01 = min(m01, x + y)
if big % 2 == 0 and small % 2 == 1:
    print(sum)
elif big % 2 == 1 and small % 2 == 1:
    print(sum - min(m10, m01 + m11))
elif big % 2 == 0 and small % 2 == 0:
    print(sum - min(m01, m10 + m11))
else:
    print(sum - min(m11, m01 + m10))

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

f = open("2B.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 += 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("2B.txt")
n = int(f.readline())
p = 10
ans = [0]*p
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans_new = [-1000000000]*p
    for k in range(len(a)):
        for j in range(p):
            ost = (ans[j] + a[k]) % p
            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())

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

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

if (s1 % 2 == 0 and s2 % 2 == 1) or (s1 % 2 == 1 and s2 % 2 == 0):
    print(s3)
else:
    if mr == 10 ** 10:  # Если нечётная разность не была найдена
        print(0)
    else:  # Иначе вычитаем найденную разность для изменения остатка
        print(s3 - mr)

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

f = open(’Задание 27B.txt’)
n = int(f.readline())
s = 0
rem = 0
m = [0, -1000000000000]
for i in range(n):
    a, b, c = [int(k) for k in f.readline().split()]
    m_new = [-100000000, -100000000]
    for j in range(2):
        t = (m[j]+a) % 2
        if (m[j] + a > m_new[t]):
            m_new[t] = m[j]+a
    for j in range(2):
        t = (m[j]+b) % 2
        if (m[j] + b > m_new[t]):
            m_new[t] = m[j]+b
    for j in range(2):
        t = (m[j]+c) % 2
        if (m[j] + c > m_new[t]):
            m_new[t] = m[j]+c
    for j in range(2):
        m[j] = m_new[j]
print(m[0])

f = open(’Задание_27-B__c1mr.txt’)
n = int(f.readline())  # Общее количество чисел

count_even = 0  # Переменная для количества чётных чисел
summa = 0  # Переменная для максимальной суммы

# Списки для хранения разниц чисел в парах, где сумма двух чисел нечётная
diff_01 = []  # Разница для случая, когда b нечётное
diff_10 = []  # Разница для случая, когда b чётное

# Обрабатываем каждую пару чисел
for i in range(n):
    a, b = sorted(map(int, f.readline().split()))  # Считываем числа по возрастанию
    summa += b  # Добавляем большее число в общую сумму

    if b % 2 == 0:  # Увеличиваем счётчик взятых чётных чисел
        count_even += 1

    # Если сумма чисел нечётная, сохраняем разницу в соответствующий список
    if (a + b) % 2 == 1:
        if b % 2 == 0:  # Если b - чётная
            diff_10.append(b - a)
        else:  # Если b - нечётная
            diff_01.append(b - a)

count_odd = n - count_even  # Количество нечётных чисел

# 1 случай: сумма чётная, но чётных чисел меньше, чем нечётных
if summa % 2 == 0 and count_even < count_odd:
    # Замены для смены остатка суммы на 1
    change_ost = sum(sorted(diff_01)[:count_odd + 1])
    # Одна замена для чётного числа b
    d = min(diff_10)
    # Вычитаем минимальную замену
    summa -= min(change_ost, d)

# 2 случай: сумма нечётная, но чётных чисел больше, чем нечётных
elif summa % 2 == 1 and count_even > n - count_even:
    # Замены для смены остатка суммы на 0
                                                                                                     
                                                                                                     
    change_ost = sum(sorted(diff_10)[:count_even + 1])
    # Одна замена для нечётного числа b
    d = min(diff_01)
    # Вычитаем минимальную замену
    summa -= min(change_ost, d)

# 3 случай: количество чётных и нечётных чисел одинаково
elif count_even == 0:
    if summa % 2 == 1:  # Если сумма нечётная
        # Две замены для чётных чисел
        change_ost = sum(sorted(diff_10)[:2])
        # Одна замена для нечётного числа b
        d = min(diff_01)
        summa -= min(change_ost, d)
    else:  # Если сумма чётная
        # Две замены для нечётных чисел
        change_ost = sum(sorted(diff_01)[:2])
        # Одна замена для чётного числа b
        d = min(diff_10)
        summa -= min(change_ost, d)

# Выводим итоговую сумму
print(summa)