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