Как решить задачу без использования itertools.product?

Question

Наткнулся на задачку с перебором, которую решил через itertools.product, но хотелось бы увидеть варианты решения, желательно, без использования библиотек.

Задача:

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел была чётной и минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

На вход программе в первой строке подаётся количество троек чисел N (1 < N < 100 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

Входные данные:

Sample Input 1:
5
2 3 2
2 3 3
2 2 1
3 3 5
1 1 1
Sample Output 1:
10
Sample Input 2:
10
2 3 2
2 3 3
2 2 1
3 3 5
1 1 1
1 2 3
4 5 6
11 23 56
23 13 10
45 76 89
Sample Output 2:
80
Sample Input 3:
10
2 3 2
2 3 3
2 2 1
3 3 5
1 1 1
1 2 3
4 5 6
11 23 56
23 13 9
44 76 89
Sample Output 3:
78

Моё решение:

import itertools

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

min_number = 1_000_000
for items in itertools.product(*matrix):
    sum_number = sum(items)
    if sum_number % 2 == 0:
        min_number = min(min_number, sum_number)
print(min_number)

Понимая что удовольствия переписывать входные данные нет, привожу их в коде (Sample Input 2):

matrix = [list(map(int, line.split())) for line in """
2 3 2
2 3 3
2 2 1
3 3 5
1 1 1
1 2 3
4 5 6
11 23 56
23 13 10
45 76 89
""".strip().splitlines()]
n = len(matrix)

Answer 1

Как такой алгоритм:

Сложить минимальные числа из каждой тройки. Если сумма четная - профит.

Если нет:

В каждой тройке найти разницу между минимальным и средним (по величине, а не расположению) числом.
К нечетной сумме прибавить минимальную нечетную разницу.

Answer 2

В принципе, у меня получилось почти то же самое, что предложил Эникейщик. Правда я хранил не разницу, а само второе минимальное число.

Алгоритм таков:
Считается сумма минимальных чисел из каждой тройки.
Параллельно сохраняется второе минимальное число при условии что оно: имеет нечётную разницу с первым минимальным (чётным сумму не поправишь) и, в принципе, минимальное из всех найденных. Также сохраняется первое минимальное число (чтобы его потом выкинуть из суммы).
Если в конце концов сумма нечётная, то из неё вычитается сохранённое число и прибавляется второе минимальное. (Ну да, здесь, в принципе, можно сразу хранить просто разницу между этими числами.)

summ = 0
min2 = (float('inf'), None)

for _ in range(int(input())):
    numb1, numb2, numb3 = sorted(map(int, input().split()))
    summ += numb1
    if   numb2-numb1 & 1 and numb2 < min2[0]: min2 = (numb2, numb1)
    elif numb3-numb1 & 1 and numb3 < min2[0]: min2 = (numb3, numb1)

if summ & 1:
    summ += min2[0] - min2[1] if min2[1] != None else -summ

print(summ)

БЛОГ НА HUSL

Как решить задачу без использования itertools.product?

Задача:

Входные данные:

Моё решение:

Ответы (2 шт):