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

Идея решения: Так как нужно получить максимальную сумму, то будем выбирать из каждой пары максимальное число, не обращая внимания на кратность. Если итоговая сумма получилась кратной 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 += max(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)

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

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

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

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

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

f = open(’4.txt’)
n = int(f.readline())
s = 0  # Переменная для конечной суммы

# Список для хранения различных по остаткам разностей между элементами
mr = [10 ** 10] * 8

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(8):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 8]:
            mr[(r + mr1[j]) % 8] = r + mr1[j]

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

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

print(s)

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

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


a = [100000000] * 8
a[0] = 0

f = open(’4.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000] * 8
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(8):
        a[j] = a_new[j]
print(a[5])

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

f = open(’5.txt’)
n = int(f.readline())
s = 0  # Переменная для конечной суммы

# Список для хранения различных по остаткам разностей между элементами
mr = [10 ** 10] * 3

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(3):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 3]:
            mr[(r + mr1[j]) % 3] = r + mr1[j]

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

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

print(s)

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

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

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

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

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

f = open(’6.txt’)
n = int(f.readline())
s = 0  # Переменная для конечной суммы

# Список для хранения различных по остаткам разностей между элементами
mr = [10 ** 10] * 16

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(16):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 16]:
            mr[(r + mr1[j]) % 16] = r + mr1[j]

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

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

print(s)

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

modul = 16


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 = [100000000000] * modul
a[0] = 0

f = open(’6.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]
print(a[11])

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

f = open(’7.txt’)
n = int(f.readline())
s = 0  # Переменная для конечной суммы

# Список для хранения различных по остаткам разностей между элементами
mr = [10 ** 10] * 11

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(11):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 11]:
            mr[(r + mr1[j]) % 11] = r + mr1[j]

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

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

print(s)

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

modul = 11


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 = [100000000000] * modul
a[0] = 0

f = open(’7.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000000] * modul
    # Функция для перебора сумм
    fun(a, a_new, x)
    fun(a, a_new, y)
    # Сохраняем сумму
    for j in range(modul):
        a[j] = a_new[j]
print(a[0])

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

f = open(’8.txt’)
n = int(f.readline())
s = 0  # Переменная для конечной суммы

# Список для хранения различных по остаткам разностей между элементами
mr = [10 ** 10] * 21

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(21):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 21]:
            mr[(r + mr1[j]) % 21] = r + mr1[j]

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

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

print(s)

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

modul = 21


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 = [100000000000] * modul
a[0] = 0

f = open(’8.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]
print(a[17])

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

f = open(’9.txt’)
n = int(f.readline())
minS = 0  # Переменная для конечной суммы
maxS = 0  # Переменная для максимальной суммы

# Так как нужна одинаковая последняя цифра,
# которая находится с помощью взятия остатка при делении на 10,
# будем искать минимальные разности по остатку при делении на 10.
mr = [10 ** 10] * 10

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

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

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

# Если конечная мин. сумма оканчивается не на ту же цифру, что и макс. сумма
if minS % 10 != maxS % 10:
    # Прибавляем к мин. сумме разность с недостающим остатком
    # Тогда мин. сумма будет оканчиваться на нужную цифру
    minS += mr[((maxS % 10) - (minS % 10)) % 21]

print(minS)

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

# По сути, последняя цифра - остаток при делении на 10,
# найдем макссумму, ее остаток и возьмем из массива нужную ячейку
modul = 10


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 = [100000000000] * modul
a[0] = 0
maxSum = 0
f = open(’9.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    maxSum += max(x, y)
    a_new = [100000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]
r = maxSum % 10
print(a[r])

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

f = open(’10.txt’)
n = int(f.readline())
minS = 0  # Переменная для минимальной суммы
maxS = 0  # Переменная для конечной суммы

# Так как нужна одинаковая последняя цифра,
# которая находится с помощью взятия остатка при делении на 10,
# будем искать минимальные разности по остатку при делении на 10.
mr = [10 ** 10] * 10

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

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

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

# Если конечная макс. сумма оканчивается не на ту же цифру, что и мин. сумма,
# то значит их разность не оканчивается на 0
if (maxS - minS) % 10 != 0:
    # Отнимаем от макс. суммы разность с остатком разности мин. и макс. сумм
    # Тогда макс. сумма будет оканчиваться на нужную цифру
    maxS -= mr[(maxS - minS) % 10]

print(maxS)

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

# По сути, последняя цифра - остаток при делении на 10,
# найдем минсумму, ее остаток и возбмем из массива нужную ячейку
modul = 10


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 = [-100000000000] * modul
a[0] = 0
minSum = 0
f = open(’10.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    minSum += min(x, y)
    a_new = [-100000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]
r = minSum % 10
print(a[r])

Решение №1

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

mp = [10 ** 10] * 54  # Список для хранения минимальных пар по остаткам
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    p = a + b  # Сумма элементов пары

    mp1 = mp[:]  # Создаём копию списка пар
    for j in range(54):
        # Ищем минимальную сумму нескольких пар
        if p + mp1[j] < mp[(p + mp1[j]) % 54]:
            mp[(p + mp1[j]) % 54] = p + mp1[j]

    # Если текущая сумма пары меньше сумм пар в списке
    if p < mp[p % 54]:
        mp[p % 54] = p

print(mp[37])  # Выводим минимальную сумму пар с остатком 37

Решение №2

# Не выбрать пару равносильно вместо пары взять 0,
# поэтому решим классическую задачу для пар чисел,
# где первое число - сумма входных чисел, а второе - 0
modul = 54


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

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

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

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

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

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

if s % 8 == 2:  # Если сумма по итогу в 8-ричной СС оканчивается на 2
    s += mr  # Прибавляем минимальную разность к минимальной сумме, меняя остаток

print(s)

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

modul = 8


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

print(min(a[0:2], a[3:]))

Решение №1

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

mp = [10 ** 10] * 123  # Список для хранения минимальных пар по остаткам
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    p = a + b  # Сумма элементов пары

    mp1 = mp[:]  # Создаём копию списка пар
    for j in range(123):
        # Ищем минимальную сумму нескольких пар
        if p + mp1[j] < mp[(p + mp1[j]) % 123]:
            mp[(p + mp1[j]) % 123] = p + mp1[j]

    # Если текущая сумма пары меньше сумм пар в списке
    if p < mp[p % 123]:
        mp[p % 123] = p

print(mp[101])  # Выводим минимальную сумму пар с остатком 101

Решение №2

modul = 123


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

print(a[101])

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

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

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

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

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

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

print(s)

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

modul = 5


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


a = [100000000000000000] * modul
a[0] = 0
f = open(’14.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]

print(max(a[:4]))

Идея: соберем сумму из всех максимумов, если ее четность совпадает с четностью большинства, то все хорошо. Если нет, то может быть два случая - чисел какой-то четности намного больше, чем другой (>=3), либо количества отличаются на 1.

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

Во втором случае может так случиться, что при такой замене (для примера у нас сейчас четных на 1 больше, чем нечетных, а сумма нечетна) мы заменим одно четное четное на нечетное, теперь сумма стала четной, но нечетных стало больше. У нас есть два варианта - либо произведем одну замену нечет/чет, тогда четность суммы изменится, а баланс сохранится, либо произведем две замены чет/нечет, тогда баланс изменится, а четность суммы сохранится.

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

sMax = 0  # Максимальная сумма, которую можно собрать
count = [0, 0]  # Счетчик четных и нечетных чисел
md01 = 10000000000000000  # миндифф для пары чет/нечет
pmd01 = 10000000000000000  # предминдифф для пары чет/нечет
md10 = 10000000000000000  # миндифф для пары нечет/чет
pmd10 = 10000000000000000  # предминдифф для пары нечет/чет

for i in range(n):
    x, y = map(int, f.readline().split())
    sMax += max(x, y)
    count[max(x, y) % 2] += 1
    diff = max(x, y) - min(x, y)
    if diff % 2 == 1:
        # Соберем мин разности для конкретных замен нечет/чет и чет/нечет
        if max(x, y) % 2 == 1:
            if diff < md10:
                pmd10 = md10
                md10 = diff
            elif diff < pmd10:
                pmd10 = diff
        else:
            if diff < md01:
                pmd01 = md01
                md01 = diff
            elif diff < pmd01:
                pmd01 = diff

if count[sMax % 2] == max(count):
    print(sMax)
elif max(count) - min(count) == 1:
    if max(count) == count[0]:
        print(sMax - min(md10, md01 + pmd01))
    else:
        print(sMax - min(md01, md10 + pmd10))
else:
                                                                                                     
                                                                                                     
    if max(count) == count[0]:
        print(sMax - min(md10, md01))
    else:
        print(sMax - min(md10, md01))

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

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

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

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

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

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

print(s)

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

modul = 13


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


a = [100000000000000000] * modul
a[0] = 0
f = open(’16.txt’)
n = int(f.readline())
for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [100000000000000000] * modul
    fun(a, a_new, x)
    fun(a, a_new, y)
    for j in range(modul):
        a[j] = a_new[j]

print(min(a[:12]))

Идея: соберем сумму из всех минимумов, если ее четность совпадает с четностью большинства, то все хорошо. Если нет, то может быть два случая - чисел какой-то четности намного больше, чем другой (>=3), либо количества отличаются на 1.

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

Во втором случае может так случиться, что при такой замене (для примера у нас сейчас четных на 1 больше, чем нечетных, а сумма нечетна) мы заменим одно четное четное на нечетное, теперь сумма стала четной, но нечетных стало больше. У нас есть два варианта - либо произведем одну замену нечет/чет, тогда четность суммы изменится, а баланс сохранится, либо произведем две замены чет/нечет, тогда баланс изменится, а четность суммы сохранится.

f = open(’17.txt’)
n = int(f.readline())
sMin = 0
count = [0, 0]
md01 = 10000000000000000  # миндифф для пары чет/нечет
pmd01 = 10000000000000000  # предминдифф для пары чет/нечет
md10 = 10000000000000000  # миндифф для пары нечет/чет
pmd10 = 10000000000000000  # предминдифф для пары нечет/чет
for i in range(n):
    x, y = map(int, f.readline().split())
    sMin += min(x, y)
    count[min(x, y) % 2] += 1
    diff = max(x, y) - min(x, y)
    if diff % 2 == 1:
        if min(x, y) % 2 == 0:
            if diff < md01:
                pmd01 = md01
                md01 = diff
            elif diff < pmd01:
                pmd01 = diff
        else:
            if diff < md10:
                pmd10 = md10
                md10 = diff
            elif diff < pmd10:
                pmd10 = diff
if count[sMin % 2] == max(count):
    print(sMin)
elif max(count) - min(count) == 1:
    if max(count) == count[0]:
        print(sMin + min(md10, md01 + pmd01))
    else:
        print(sMin + min(md01, md10 + pmd10))
else:
    if max(count) == count[0]:
        print(sMin + min(md10, md01))
    else:
        print(sMin + min(md10, md01))

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

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

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

mr = [10 ** 10] * 3  # Список для хранения минимальных разностей по остаткам
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(3):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 3]:
            mr[(r + mr1[j]) % 3] = r + mr1[j]

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

# Если конечная сумма в 3-ичной СС не оканчивается на 2
if s % 3 != 2:
    # Отнимаем от макс. суммы разность с таким остатком,
    # чтобы при вычитании остаток изменился на (s%3 - 2)
    s -= mr[(s % 3 - 2) % 3]

print(s)

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

modul = 3


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

print(a[2])

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

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

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

mr = [10 ** 10] * 7  # Список для хранения минимальных разностей по остаткам
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(7):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 7]:
            mr[(r + mr1[j]) % 7] = r + mr1[j]

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

# Если конечная сумма в 7-ричной СС не оканчивается на 4
if s % 7 != 4:
    # Прибавляем к мин. сумме разность с недостающим остатком
    s += mr[(4 - s % 7) % 7]

print(s)

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

modul = 7


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

print(a[4])

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

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

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

mr = [10 ** 10] * 14  # Список для хранения минимальных разностей по остаткам
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(14):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 14]:
            mr[(r + mr1[j]) % 14] = r + mr1[j]

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

# Если конечная сумма в 14-ричной СС не оканчивается на ’B’
# То есть остаток при делении на 14 не равен 11
if s % 14 != 11:
    # Прибавляем к мин. сумме разность с недостающим остатком
    s += mr[(11 - s % 14) % 14]

print(s)

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

modul = 14


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

print(a[11])