Максим Сергеевич любит большие числа. Сегодня ему дали задачу — из каждой группы чисел нужно выбрать ровно 2 и найти их НОК. После этого находится сумма всех таких НОК. Также известно, что МС любит числа 5 и 7, но не оба одновременно. МС с лёгкостью решил бы эту задачу, но после щелчка ему нужен отдых, и он отправился путешествовать по маршруту Москва-Ярославль-Питер-Ярославль-Москва-Сочи.
Помогите МС. Найдите максимальную сумму НОК из каждой группы чисел, чтобы она делилась либо на 7, либо на 5, но не на оба числа одновременно.
Входные данные:
Даны два входных файла, каждый из которых содержит в первой строке количество чисел 
(
). В каждой из следующих 
строк файлов записан сначала размер группы 
(
), а затем 
натуральных чисел, не превышающих 500.
Пример входного файла:
4
2 8 6
3 2 7 8
2 6 5
4 7 3 8 6
Примечание:
Для указанных входных данных значения НОК для первой группы — 24; для второй группы — 14, 8, 56; для третьей группы — 30, для четвёртой группы — 6, 21, 24, 24, 42, 56. Значением искомой суммы должно быть число 110 (24+14+30+42). В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение №1.
def evklid(a, b): # поиск НОДа
if b > a:
a, b = b, a
if a != 0 and b != 0:
return evklid(a % b, b)
return a + b # одно из чисел = 0
def nok(a, b): # НОК(a, b) = a * b // НОД(a, b)
return a * b // evklid(a, b)
f = open(’test.txt’)
n = int(f.readline())
ans = [-10000000] * 35
ans[0] = 0
for i in range(n):
a = [int(x) for x in f.readline().split()] # a[0] - количество элементов
ans_new = [-10000000] * 35
for q in range(1, len(a)):
for k in range(q + 1, len(a)):
NOK = nok(a[q], a[k])
for j in range(35):
ost = (ans[j] + NOK) % 35
if ans[j] + NOK > ans_new[ost]:
ans_new[ost] = ans[j] + NOK
ans = ans_new.copy()
maxim = -1
for i in ans:
if (i % 5 == 0 or i % 7 == 0) and i % 35 != 0:
maxim = max(i, maxim)
print(maxim)
Решение №2.
from math import gcd
def solve(file):
f = open(file)
n = int(f.readline())
curr = [-1] * 35
curr[0] = 0
for q in range(n):
a = list(map(int, f.readline().split()))
cnt = a[0]
del a[0]
temp = [-1] * 35
for i in range(cnt - 1):
for j in range(i + 1, cnt):
x, y = a[i], a[j]
nod = gcd(x, y)
nok = x * y // nod
for k in range(35):
if curr[k] == -1:
continue
ost = (curr[k] + nok) % 35
temp[ost] = max(temp[ost], curr[k] + nok)
curr = temp.copy()
ans = -1
for i in range(35):
if (i % 7 == 0 or i % 5 == 0) and i % 35 != 0:
ans = max(ans, curr[i])
print(ans)
f.close()
solve("27-A.txt")
solve("27-B.txt")