Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна 5 или 11, но не 5 и 11 одновременно. Определите, какую максимальную сумму, удовлетворяющую условиям задачи можно получить.
Формат входных данных
Набор данных состоит из пар натуральных чисел.
Первая строка входных данных содержит число n — количество строк, 
. Следующие n строк содержат пару натуральных чисел не превышающие 10000.
Формат выходных данных
Программа должна вывести целое число — максимальную сумму.
Пример:
Ответом для примера будет: 
Максимальная сумма, которую можно получить равна (5+50), но она кратна одновременно и 5, и 11, что недопустимо по условию задачи. Сумма 3+8 подходит по условиям задачи и является максимальной.
По китайской теореме об остатках гарантируется, что при перемножении взаимнопростых чисел найдется сумма, которая будет иметь какой-то остаток при делении на произведение и при этом будет кратно лишь одному из чисел, указанных в произведении.
Метод минимальных разностей
f = open(’27.txt’)
n = int(f.readline())
mr = [10 ** 10] * (5 * 11) # Список для хранения минимальных разностей по остаткам
maxS = 0 # Максимальная сумма чисел
for i in range(n):
a, b = map(int, f.readline().split()) # Считываем числа
maxS += max(a, b) # Прибавляем к сумме максимальное число из пары
r = abs(a - b) # Разность между элементами
mr1 = mr[:] # Создаём копию списка разностей
for j in range(55):
# Ищем минимальную сумму нескольких разностей
if r + mr1[j] < mr[(r + mr1[j]) % 55]:
mr[(r + mr1[j]) % 55] = r + mr1[j]
# Если текущая разность меньше разности в списке
if r < mr[r % 55]:
mr[r % 55] = r
# Сумма делится на оба числа
if maxS % 5 == 0 and maxS % 11 == 0:
# Нужно найти такую мин. разность, которая изменит только один остаток:
# либо остаток от деления на 5, либо остаток от деления на 11
d = 10 ** 10
for j in range(55):
count = 0 # Количество чисел, на которое делится сумма
if (maxS - mr[j]) % 5 != 0:
count += 1
if (maxS - mr[j]) % 11 != 0:
count += 1
if count == 1: # Если сумма не делится на одно число, запоминаем разность
d = min(mr[j], d)
maxS -= d # Вычитаем итоговую мин. разность
# Сумма не делится ни на одно число
elif maxS % 5 != 0 and maxS % 11 != 0:
# Также нужно найти мин. разность, которая даст кратность только одному числу
d = 10 ** 10
for j in range(55):
count = 0 # Количество чисел, на которое делится сумма
if (maxS - mr[j]) % 5 == 0:
count += 1
if (maxS - mr[j]) % 11 == 0:
count += 1
if count == 1: # Если сумма делится на одно число, запоминаем разность
d = min(mr[j], d)
maxS -= d # Вычитаем итоговую мин. разность
print(maxS) # Выводим итоговую сумму выбранных чисел
Метод частичных сумм
n = int(input())
ans = [0]*(5*11)
for i in range(n):
a = [int(i) for i in input().split()]
ans_new = [-1000000000]*55
for k in range(len(a)):
for j in range(55):
ost = (ans[j] + a[k]) % 55
if ans[j] + a[k] > ans_new[ost]:
ans_new[ost] = ans[j] + a[k]
ans = ans_new
print(max(max([i*(i % 5 == 0 and i % 11 != 0) for i in ans]),
max([i*(i % 5 != 0 and i % 11 == 0) for i in ans])
))