Имеется набор данных, состоящий из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы восьмеричная запись суммы всех выбранных чисел не оканчивалась на четное число и при этом была максимально возможной. Если искомую сумму получить нельзя, то напечатайте 
. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи, записанную в десятичной системе счисления.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар 
(1 
100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 
.
Пример входных данных:
6
1 3
5 12
6 9
5 4
3 3
5 1
Для таких входных данных значением искомой суммы будет число 
.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Метод минимальных разностей
# Примечание: последняя цифра в 8-ричной записи - это остаток от деления на 8
f = open("6B.txt")
n = int(f.readline())
mr = 10 ** 10 # Минимальные нечётная разность, чтобы поменять остаток
s = 0 # Сумма выбранных чисел
for i in range(n):
a, b = map(int, f.readline().split())
s += max(a, b) # Прибавляем максимальное число в паре
r = abs(a - b) # Разность между элементами для замены мин. числа на макс. число
if (r < mr) and ((r % 8) % 2 != 0): # Если новая разность меньше и при этом нечётна
mr = r # Сохраняем её
# Если в итоге сумма в 8-ричной записи оканчивается на чётную цифру,
# то нужно попробовать вычесть разность
if (s % 8) % 2 == 0:
if mr == 10 ** 10: # Если разность не найдена (равна заданному изначально значению)
s = 0 # Меняем сумму на 0 (как просят в условии)
else:
s -= mr # Иначе вычитаем найденную разность для изменения остатка
print(s)
Метод частичных сумм
f = open("6B.txt")
n = int(f.readline())
ans = [0] * 8
for i in range(n):
a = [int(i) for i in f.readline().split()]
ans_new = [-1000000000] * 8
for k in range(len(a)):
for j in range(8):
ost = (ans[j] + a[k]) % 8
if ans[j] + a[k] > ans_new[ost]:
ans_new[ost] = ans[j] + a[k]
ans = ans_new.copy()
print(max(ans[i] for i in range(1, 8, 2)))