27.04 Пары/тройки чисел, выбрать из каждой пары/тройки число, кратность
Ошибка.
Попробуйте повторить позже
Максим Сергеевич любит большие числа. Сегодня ему дали задачу - из каждой группы чисел нужно выбрать
ровно 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")
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
