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

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

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

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

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

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

$5$

$10$

$15$

$91$

$33$

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

f = open(’27A.txt’)
n = int(f.readline())
k = 5
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])

Ответ: 209727 253530120045645880299340640255