27.07 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
Шестиклассник Коля совсем недавно узнал, что такое НОД и НОК — наибольший общий делитель и наименьшее
общее кратное некоторого набора натуральных чисел. Ему так понравилась эта тема, поэтому он решил
потренироваться и в случайном порядке начал выписывать на доску от 
до 
натуральных чисел в строчку и
попарно начал находить для них НОКи. Его друг Ваня предложил Коле следующую задачу: из каждой строки
нужно выбрать один из НОКов, причем так, чтобы их сумма была наибольшей, а также кратна 
или
.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Формат входных данных
Первая строка входных данных содержит число n — количество строк, 
. Следующие 
строк содержат
натуральное число 
, обозначающее количество чисел в строке, затем 
натуральных чисел в этой
строке.
Формат выходных данных
Программа должна вывести целое число — максимальную сумму, кратную 
или 
.
Пример:
Ответом для примера будет: 
Рассмотрим пример из условия. Для указанных входных данных значения НОК для первой строки — 
; для второй
строки — 
для третьей группы — 
, для четвёртой группы — 
Значением искомой суммы
должно быть число 
.
def gcd(a, b): if b == 0: return a return gcd(b, a % b) def lcm(a, b): return (a*b)//gcd(a, b) def h(x, m, m_new): for j in range(88): ost = (m[j]+x) % 88 if (m[j]+x > m_new[ost]): m_new[ost] = m[j]+x f = open(’Задание 27 B.txt’) m = [-1000000]*88 m[0] = 0 n = int(f.readline()) for i in range(n): a = [int(p) for p in f.readline().split()] k = a[0] b = [] for i in range(1, len(a)): for j in range(i+1, len(a)): b.append(lcm(a[i], a[j])) m_new = [-10000000]*88 for x in b: h(x, m, m_new) for j in range(88): m[j] = m_new[j] ans = -10000000 for r in range(88): if r % 8 == 0 or r % 11 == 0: ans = max(ans, m[r]) print(ans)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
