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 не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
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)