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