Дана последовательность, которая состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел как в первой, так и во второй группе должна быть чётной. Определите максимально возможную сумму всех чисел в третьей группе.
Пример входного файла:
Ответ для данного примера: 
В ответе запишите сначала результат для файла А, затем, через пробел, для файла Б.
Метод наименьших разностей
Идея решения:
Будем составлять из всех троек 3 суммы: первая будет состоять из минимальных чисел, вторая — из средних чисел, третья — из максимальных чисел.
Обозначим их как 
, 
и 
.
Задача состоит в том, чтобы максимизировать сумму 
, но при этом нужно, чтобы суммы 
и 
были чётными. Значит нужно найти такие минимальные разности, которыми можно заменить числа в суммах так, чтобы сумма 
уменьшилась как можно меньше. При этом разности должны быть нечётными, чтобы изменять чётность сумм.
Рассмотрим 3 случая неподходящих сумм:
нечётна, 
нечётна 
чётна, 
нечётна 
нечётна, 
чётна
В первом случае будет идеально, если между суммами 
и 
будет любая нечётная разность между минимальным числом и средним числом. В таком случае можно будет их поменять местами, тогда обе суммы станут чётны, не затрагивая сумму 
.
Однако нужно учесть вариант, что такой разности может и не быть. Тогда рассмотрим какие разности можно вычесть из максимальной суммы 
. Будем расписывать подходящие для замены виды троек по остаткам минимального, среднего и максимального числа соответственно, то есть по их позициям 1, 2 и 3:
В таких тройках можно будет менять максимальное число и с минимальным, и со средним для изменения чётности. Но так как мы хотим уменьшить сумму 
как можно меньше, то будем делать в таких случаях замену только со средним числом. Тогда тройки изменятся на следующий вид:
Если сделать 1 такую замену, то сумма 
станет чётна, а также в такой тройке появится возможность поменять первое и второе число в этой тройке, так как их разность станет нечётна. В итоге, чтобы обе суммы стали чётны, достаточно сделать в двух тройках замену среднего числа на максимальное. Тогда сумма 
останется нечётна (два раза изменили её остаток на 1), а также появятся две тройки с нечётными разностями для замены первого числа на второе. Таким образом, сделав замену только в одной из двух таких троек, получим чётные суммы 
и 
.
Во втором случае сумму 
уже трогать не нужно, нужно только сделать замену между суммами 
и 
, чтобы сумма 
стала чётна. Тогда подойдут тройки следующего вида, где 
– любой остаток:
То есть нужно сохранить все нечётные разности между средним и максимальным числом, чтобы только в одной тройке сделать замену минимальной разностью.
В третьем случае для идеальной замены распишем виды подходящих троек, где 
– любой остаток:
Среди них выделим тройки следующего вида:
В этих выделенных тройках, как в 1 случае, не важно какую делать замену: менять минимальное на максимальное или среднее на максимальное. Если поменять максимальное со средним, то в итоге можно будет сделать замену между 2 и 3 по позициям числами, а далее между 1 и 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:
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(’27.txt’)
n = int(f.readline())
s = [[0,0,0]]
for i in range(n):
tr = [int(x) for x in f.readline().split()]
s = [[a1+b1, a2+b2, a3+b3] for a1, a2, a3 in s for b1, b2, b3 in permutations(tr)]
s = {(x[1]%2, x[2]%2): x for x in sorted(s)}.values()
for a3, a2, a1 in s:
if a2 % 2 == 0 and a1 %2 == 0:
print(a3)