Задача к ЕГЭ по информатике на тему «пары/тройки чисел, выбрать из каждой, кратность» №2

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

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

Будем составлять из всех троек 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)