Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 3 или 20. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.
Формат входных данных
Набор данных состоит из пар натуральных чисел.
Первая строка входных данных содержит число n — количество строк, 
. Следующие n строк содержат пару натуральных чисел не превышающие 10000.
Формат выходных данных
Программа должна вывести целое число — максимальную сумму.
Пример:
Ответом для примера будет: 
Максимальная сумма, которую можно получить равна 
.
Метод минимальных разностей
f = open(’27B.txt’) # Открываем нужный файл
n = int(f.readline())
k = [3, 20] # список чисел, одному из которых должна быть кратна итоговая сумма
mr = [[10 ** 10] * j for j in k] # Список для хранения минимальных разностей по остаткам
s = 0 # Переменная для максимальной суммы
for i in range(n):
a, b = map(int, f.readline().split()) # Считываем числа
s += max(a, b) # Прибавляем к сумме максимальное число из пары
r = abs(a - b) # Разность между элементами
for q in range(2): # Рассматриваем разности для двух чисел отдельно
new_mr = mr[q][:] # Создаём копию списка разностей
for j in range(k[q]):
# Ищем минимальную сумму нескольких разностей
if r + new_mr[j] < mr[q][(r + new_mr[j]) % k[q]]:
mr[q][(r + new_mr[j]) % k[q]] = r + new_mr[j]
# Если текущая разность меньше разности в списке
if r < mr[q][r % k[q]]:
mr[q][r % k[q]] = r
ans = 0 # Переменная для ответа
# Если сумма в итоге кратна одному из чисел
if s % k[0] == 0 or s % k[1] == 0:
ans = s # Сохраняем сумму
else: # Иначе отнимаем от макс. суммы разность с таким же остатком
ans = max(ans, s - mr[0][s % k[0]])
ans = max(ans, s - mr[1][s % k[1]])
print(ans)
Метод частичных сумм
f = open(’27B.txt’)
n = int(f.readline())
ans = [0] * (3*20)
for i in range(n):
a = [int(i) for i in f.readline().split()]
ans_new = [-1000000000] * 60
for k in range(len(a)):
for j in range(60):
ost = (ans[j] + a[k]) % 60
if ans[j] + a[k] > ans_new[ost]:
ans_new[ost] = ans[j] + a[k]
ans = ans_new
print(max([i for i in ans if i % 3 == 0 or i % 20 == 0]))