Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел НЕ делилась на 6 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A и файл B, каждый из которых содержит в первой строке количество троек N (
). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
пример входного файла:
6
8 3 4
3 8 12
9 5 6
2 8 3
12 3 5
7 3 12
Для указанных входных данных значением искомой суммы должно быть число 94.
В ответе укажите два числа через пробел: сначала значение искомой суммы для файла А, затем для файла B.
Метод минимальных разностей
f = open(’D:/5_A.txt’)
n = int(f.readline())
mr = 10 ** 10 # Минимальная разность
s = 0 # Максимальная сумма
for i in range(n):
# Считывание чисел по возрастанию с помощью сортировки sorted()
x, y, z = sorted(map(int, f.readline().split()))
s += y + z # Прибавляем два наибольших числа тройки
d1 = z - x # Разность для возможной замены на ср. числа на мин. число
d2 = y - x # Разность для возможной замены на макс. числа на мин. число
# Потенциальную замену разностью можно сделать, если:
# 1) разность меньше минимальной в mr
# 2) разность не кратна 6, чтобы остаток суммы при её вычитании изменился
if (d1 < mr) and (d1 % 6 != 0):
mr = d1
if (d2 < mr) and (d2 % 6 != 0):
mr = d1
if s % 6 == 0: # Если сумма по итогу оказалась кратна 9
s -= mr # Вычитаем минимальную разность из максимальной суммы
print(s)
Метод частичных сумм
f = open(’D:/5_A.txt’)
n = int(f.readline())
sm = 0
# Список с суммами с разными остатками.
# Изначально суммы пустые.
m = [0]*6
for i in range(n):
nums = list(map(int, f.readline().split()))
# Собираем в отдельном списке суммы из всевозможных пар из тройки
pairs = []
for j in range(len(nums)):
for k in range(j+1, len(nums)):
pairs.append(nums[j]+nums[k])
# Временный массив с суммами.
m_new = [0] * 6
# Перебор разных сумм со всеми суммами пар из тройки.
# Суммы из m будут сравниваться между собой посредством условий.
for t in range(6):
for p in pairs:
if m[t] + p > m_new[(m[t] + p) % 6]:
m_new[(m[t] + p) % 6] = m[t] + p
# Сохраняем получившийся массив в m
m = m_new.copy()
# Просят максимальное, не кратное 6.
# Значит берём максимальное из m[1:]
print(m[1:])