Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №9

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

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

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

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

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

$5$

$18$

$1$

$2$

$3$

$36$

Для указанных данных ответом будет являться $3$ .

f = open(’27A.txt’)
n = int(f.readline())
k = 9*2
ans = [0]*k
for i in range(n):
    x = int(f.readline())
    ans_new = ans[:] #Аналог ans.copy()

    #Подсчет ответа для уже существующих подмножеств
    for j in range(k):
        ans_new[(j+x) % k] += ans[j]
    #Составление нового множества из одного числа x
    ans_new[x % k] += 1

    #Сохранение нового количества множеств
    ans = ans_new[:]

print(ans[0])

Ответ: 58283 70425033346012744527579710463