Наткнулся на задачку с перебором, которую решил через 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)
product
?