Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел НЕ делилась на 5 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должны напечатать одно – минимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл А.txt и файл В.txt, каждый из которых содержит в первой строке количество пар N. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входного файла:
6
3 5
5 12
6 9
5 4
7 9
5 1
Для указанных входных данных значением искомой суммы должно быть число 26.
В ответе укажите два числа через пробел: сначала значение искомой суммы для файла А, затем для файла В.
Идея решения: Так как нужно получить минимальную сумму, то будем выбирать из каждой пары минимальное число, не обращая внимания на кратность. Если итоговая сумма получилась кратной 5, то необходимо заменить одно выбранное число другим числом из пары, при этом заменить нужно так, чтобы итоговая сумма увеличилась минимально. Для этого на каждом шаге будем сохранять минимальную разницу между элементами пары, такую что разница не кратна 5, потому что если разница будет кратна 5, то замена не даст другой кратности у итоговой суммы.
f = open(’1.txt’)
n = int(f.readline())
s = 0
# переменная для хранения минимальной разницы между числами пары
mr = 1000000500000
for i in range(n):
# считываем числа
a, b = map(int, f.readline().split())
# для того чтобы итоговая сумма получилась минимальной берем минимальное из пары
s += min(a, b)
# обновляем минимальную разницу НЕ кратную 5
if (abs(a-b) < mr) and (abs(a-b) % 5 != 0):
mr = abs(a-b)
# если результирующая сумма получилась кратной 5, то прибавляем разницу
if s % 5 == 0:
s += mr
print(s)