Набор данных состоит из пар натуральных чисел. Необходимо выбрать из каждой пары одно число так, чтобы сумма выбранных чисел была максимально возможной и не делилась на 
, при этом сумма невыбранных чисел не делилась на 
. Какую наибольшую сумму выбранных чисел можно при этом получить?
Пример входного файла:
Ответ для данного примера: 
Метод наименьших разностей
f = open(’22.txt’)
n = int(f.readline())
mr = [10 ** 10] * (3 * 5) # Список для хранения минимальных разностей по остаткам
maxS = 0 # Сумма выбранных чисел
minS = 0 # Сумма невыбранных чисел
for i in range(n):
a, b = map(int, f.readline().split()) # Считываем числа
maxS += max(a, b) # Прибавляем к сумме максимальное число из пары
minS += min(a, b) # Прибавляем к сумме минимальное число из пары
r = abs(a - b) # Разность между элементами
mr1 = mr[:] # Создаём копию списка разностей
for j in range(15):
# Ищем минимальную сумму нескольких разностей
if r + mr1[j] < mr[(r + mr1[j]) % 15]:
mr[(r + mr1[j]) % 15] = r + mr1[j]
# Если текущая разность меньше разности в списке
if r < mr[r % 15]:
mr[r % 15] = r
# Обе суммы не удовлетворяют условию
if maxS % 5 == 0 and minS % 3 == 0:
# Находим среди минимальных разностей по остаткам такую минимальную разность,
# которая не будет кратна ни 3, ни 5, чтобы поменять остаток обеих сумм
d = min(mr[j] for j in range(15) if (mr[j] % 5 != 0) and (mr[j] % 3 != 0))
# Отнимаем разность от максимальной суммы и прибавляем к минимальной
maxS -= d
minS += d
# Сумма невыбранных чисел не удовлетворяет условию
elif maxS % 5 != 0 and minS % 3 == 0:
# Остаток для максимальной суммы, вычитание которого даст кратность 5
ost5 = maxS % 5
# Находим среди минимальных разностей по остаткам такую минимальную разность,
# которая не будет кратна 3, чтобы поменять остаток минимальной суммы,
# и при этом остаток которой не будет равен ost5, чтобы не сделать макс. сумму кратной 5
d = min(mr[j] for j in range(15) if (mr[j] % 5 != ost5) and (mr[j] % 3 != 0))
# Отнимаем разность от максимальной суммы и прибавляем к минимальной
maxS -= d
minS += d
# Сумма выбранных чисел не удовлетворяет условию
elif maxS % 5 == 0 and minS % 3 != 0:
# Остаток для минимальной суммы, прибавление которого даст кратность 3
ost3 = 3 - minS % 3
# Находим среди минимальных разностей по остаткам такую минимальную разность,
# которая не будет кратна 5, чтобы поменять остаток максимальной суммы,
# и при этом остаток которой не будет равен ost3, чтобы не сделать мин. сумму кратной 3
d = min(mr[j] for j in range(15) if (mr[j] % 5 != 0) and (mr[j] % 3 != ost3))
# Отнимаем разность от максимальной суммы и прибавляем к минимальной
maxS -= d
minS += d
print(maxS) # Выводим итоговую сумму выбранных чисел
Метод частичных сумм
# Для решения задачи будем искать макс суммы с остатками по модулю 5
# и смотреть на их остатки по модулю 3 - чтобы сравнить с остатком суммы всех чисел.
# Если окажется, что эти остатки равны, то сумма нам не подходит
# (так как тогда summ_all - current_summ % 3 ==0), и надо смотреть на другую.
# Поэтому надо собрать суммы с разными парами остатков по модулю 5 и 3,
# а все такие сумы будут иметь разные остатки по модулю 3 * 5 = 15
modul = 15
def fun(a, a_new, x):
for j in range(modul):
k = (a[j] + x) % modul
a_new[k] = max(a_new[k], a[j] + x)
a = [-100000000000000000] * modul
a[0] = 0
f = open(’22.txt’)
n = int(f.readline())
summ_all = 0
for i in range(n):
x, y = map(int, f.readline().split())
a_new = [-100000000000000000] * modul
fun(a, a_new, x)
fun(a, a_new, y)
summ_all += x + y
for j in range(modul):
a[j] = a_new[j]
print(max([i for i in a if (i % 5 != 0 and i % 3 != summ_all % 3)]))