Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно два числа так, чтобы сумма всех выбранных чисел делилась на 
или на 
, но не делилась на оба этих числа одновременно, и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно.
Пример входного файла:
Ответ для данного примера: 
Метод минимальных разностей
f = open(’29.txt’)
n = int(f.readline())
mr = [10 ** 10] * (3 * 17) # Список для хранения минимальных разностей по остаткам
minS = 0 # Минимальная сумма чисел
for i in range(n):
a, b, c = sorted(map(int, f.readline().split())) # Считываем числа по возрастанию
minS += a + b # Прибавляем к сумме два наименьших числа из пары
r1 = c - b # Разность между ср. и макс. числами
r2 = c - a # Разность между мин. и макс. числами
for r in r1, r2: # Перебираем разности
mr1 = mr[:] # Создаём копию списка разностей
for j in range(51):
# Ищем минимальную сумму нескольких разностей
if r + mr1[j] < mr[(r + mr1[j]) % 51]:
mr[(r + mr1[j]) % 51] = r + mr1[j]
# Если текущая разность меньше разности в списке
if r < mr[r % 51]:
mr[r % 51] = r
# Сумма делится на оба числа
if minS % 3 == 0 and minS % 17 == 0:
# Нужно найти такую мин. разность, которая изменит только один остаток:
# либо остаток от деления на 3, либо остаток от деления на 17
d = 10 ** 10
for j in range(51):
count = 0 # Количество чисел, на которое делится сумма
if (minS + mr[j]) % 3 != 0:
count += 1
if (minS + mr[j]) % 17 != 0:
count += 1
if count == 1: # Если сумма не делится на одно число, запоминаем разность
d = min(mr[j], d)
minS += d # Прибавляем итоговую мин. разность
# Сумма не делится ни на одно число
elif minS % 3 != 0 and minS % 17 != 0:
# Также нужно найти мин. разность, которая даст кратность только одному числу
d = 10 ** 10
for j in range(51):
count = 0 # Количество чисел, на которое делится сумма
if (minS + mr[j]) % 3 == 0:
count += 1
if (minS + mr[j]) % 17 == 0:
count += 1
if count == 1: # Если сумма делится на одно число, запоминаем разность
d = min(mr[j], d)
minS += d # Прибавляем итоговую мин. разность
print(minS) # Выводим итоговую сумму выбранных чисел
Метод частичных сумм
# Так как 3 и 17 взаимно простые, все числа,
# дающие разные пары остатков при делении на 3 и 17,
# имеют разные остатки при делении на 51,
# поэтому найдем все минсуммы для всех остатков по модулю 51
# и выберем только те значения, которые кратны или 3 или 17
modul = 51
def fun(a, a_new, x):
for j in range(modul):
k = (a[j] + x) % modul
a_new[k] = min(a_new[k], a[j] + x)
a = [100000000000000000] * modul
a[0] = 0
f = open(’29.txt’)
n = int(f.readline())
for i in range(n):
x, y, z = map(int, f.readline().split())
a_new = [100000000000000000] * modul
fun(a, a_new, x+y)
fun(a, a_new, y+z)
fun(a, a_new, x+z)
for j in range(modul):
a[j] = a_new[j]
# Создадим массив b, в который поместим минсуммы
# с только интересными нам остатками
b = []
for i in range(1,17):
b.append(a[3*i]) # Все, кратные 3, но не 17
for i in range(1,3):
b.append(a[i*17]) # Все, кратные 17, но не 3
print(min(b))