Тема 27. Программирование – оптимизация по времени и по памяти

27.04 Пары/тройки чисел, выбрать из каждой пары/тройки число, кратность

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование – оптимизация по времени и по памяти
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#32960

Максим Сергеевич любит большие числа. Сегодня ему дали задачу - из каждой группы чисел нужно выбрать ровно 2 и найти их НОК. После этого находится сумма всех таких НОК. Также известно, что МС любит числа 5 и 7, но не оба одновременно. МС с лёгкостью решил бы эту задачу, но после щелчка ему нужен отдых, и он отправился путешествовать по маршруту Москва-Ярославль-Питер-Ярославль-Москва-Сочи.
Помогите МС. Найдите максимальную сумму НОК из каждой группы чисел, чтобы она делилась либо на 7, либо на 5, но не на оба числа одновременно.
Входные данные:
Даны два входных файла, каждый из которых содержит в первой строке количество чисел N  (2 ≤ N ≤ 100000  ). В каждой из следующих N  строк файлов записан сначала размер группы K  (K  ≤ 10  ), а затем K  натуральных чисел, не превышающих 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")

Ответ: 2257416 1254402115

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!