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

27.07 Прочие прототипы

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

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

Задача 1#40719

На вход программы поступает последовательность из N  натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств длины 3, в которых сумма элементов кратна 3.

Пример входных данных:

Первая строка входного файла содержит число N  – общее количество чисел. Каждая из следующих N  строк содержит натуральные числа, не превышающих 10 000.

Пример входного файла

3

1

2

3

Для указанных данных ответом будет являться, {1, 2, 3}, то есть 1.

Вложения к задаче
Показать ответ и решение

Решение 1

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in range(2**n):
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
    if len(mn) == 3:
        if sum(mn) % 3 == 0:
            ans += 1

print(ans)

Решение 2

from itertools import combinations

f = open(’27A.txt’)
n = int(f.readline())

nums = []
for i in range(n):
    nums.append(int(f.readline()))

ans = 0
for i in combinations(nums, 3):
    if sum(i) % 3 == 0:
        ans += 1

print(ans)

Ответ: 357

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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