Задача к ЕГЭ по информатике на тему «прочие прототипы» №2

Просмотров 12 Комментарии 0

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

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

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

f = open(’27A.txt’)

n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
k = 30
ans = 0

for i in range(1, 2**n):
    t = i
    s = 0
    for j in range(n):
        if t % 2 == 1:
            s += a[j]
        t //= 2

    if s % k == 0:
        ans += 1

print(ans)

Ответ: 35275