Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел делилась на 8 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A и файл B, каждый из которых содержит в первой строке количество троек N (
). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
пример входного файла:
6
8 3 4
3 8 12
9 5 6
2 8 3
12 3 5
7 4 12
Для указанных входных данных значением искомой суммы должно быть число 56.
В ответе укажите два числа через пробел: сначала значение искомой суммы для файла А, затем для файла B.
f = open(’3_B.txt’) # для ответа на A требуется подключить 3_A.txt
n = int(f.readline()) # Считываем количество пар из первой строки
s = 0 # Инициализируем переменную для хранения суммы
mr = [10000005000000] * 8 # Cписок минимальных остатков от деления на 8
for i in range(n): # Проходим по каждой тройке чисел
a, b, c = map(int, f.readline().split()) # Считываем тройку чисел
mx = max(a, b, c)
mn = min(a, b, c)
md = a + b + c - mx - mn # Находим максимальное, минимальное и среднее числа
d1 = mx - md
d2 = mx - mn # Вычисляем разности для двух возможных минимальных разностей
s += mx # Добавляем максимальное число к сумме
mr1 = mr[:] # Создаем копию списка ’mr’
# Проходим по каждому остатку от деления на 8 для первой разности
for j in range(8):
# Если сумма разности и элемента списка меньше чем элемент списка
if d1 + mr1[j] < mr[(d1 + mr1[j]) % 8]: # по остатку от деления
# Заменяем элемент списка на сумму разности и элемента
mr[(d1 + mr1[j]) % 8] = d1 + mr1[j]
# Проходим по каждому остатку от деления на 8 для второй разности
for j in range(8):
# Если сумма разности и элемента списка меньше чем элемент списка
if d2 + mr1[j] < mr[(d2 + mr1[j]) % 8]:
# Заменяем элемент списка на сумму разности и элемента
mr[(d2 + mr1[j]) % 8] = d2 + mr1[j]
# Заменяем элемент списка по остатку на минимум между элементом и
mr[d1 % 8] = min(mr[d1 % 8], d1) # разностью для обеих разностей
mr[d2 % 8] = min(mr[d2 % 8], d2)
if s % 8 != 0: # Если сумма не делится на 8 без остатка
s -= mr[s % 8] # Вычитаем из суммы минимальный остаток
print(s)