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

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