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