Python. Задача 8-37

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000. Пример организации исходных данных во входном файле:

6
1  3
5  12
6  9
5  4
3  3
1  1

Для указанных входных данных значением искомой суммы должно быть число 32.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ
127127 399762080
Решение
f = open('c:\\work\\test-8-37-B.txt')
# Считывем из первой строки количество пар
N = int(f.readline())
# Минимальная разница в парах,
# которая не делится на 3
mindiff = 10001
# Максимальная сумма
msum = 0
# Выбираем максимальные числа из пар
for i in range(N):
    a, b = map(int, f.readline().split())
    msum += max(a, b)
    # Вычисляем минимальную разницу в парах
    a = abs(a - b)
    if a < mindiff and a % 3 != 0:
        mindiff = a
f.close()
# Максимальная сумма
if msum % 3 != 0:
    print(msum)
else:
    # Если максимальная сумма делится на 3, то
    # уменьшаем ее на минимальную разницу в парах
    print(msum - mindiff)