Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй – нечётной. Определите максимально возможную сумму всех чисел в третьей группе. Если искомую сумму получить невозможно, то в ответе укажите 0.
Пример входных данных:
Первая строка входного файла содержит число N – общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла
3
8 9 16
20 21 7
5 24 16
Для указанных данных искомая сумма равна 61, она соответствует такому распределению чисел по группам: (8, 20, 5), (9, 7, 16), (16, 21, 24).
f = open(’27A3.txt’)
n = int(f.readline())
mr = 10 ** 10 # Минимальная разность
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 # Прибавляем наибольшее число тройки
d1 = z - x # Разность для возможной замены на макс. числа на мин. число
d2 = z - y # Разность для возможной замены на макс. числа на ср. число
# В любом случае одна из сумм будет иметь остаток 0 или 1,
# так что достаточно будет поменять остаток второй суммы.
# Для этого нужно искать минимальную нечётную разность.
if (d1 < mr) and (d1 % 2 != 0):
mr = d1
if (d2 < mr) and (d2 % 2 != 0):
mr = d2
if (s1 % 2 == 0 and s2 % 2 == 1) or (s1 % 2 == 1 and s2 % 2 == 0):
print(s3)
else:
if mr == 10 ** 10: # Если нечётная разность не была найдена
print(0)
else: # Иначе вычитаем найденную разность для изменения остатка
print(s3 - mr)