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

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

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

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

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

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

$5$

$2$

$4$

$8$

$1$

$3$

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

def sol(k, data):
    ans = [0] * k
    for i in range(len(data)):
        x = data[i]
        ans_new = ans[:]  # Аналог ans.copy()

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

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

    return ans

f = open(’27A.txt’)
n = int(f.readline())
data = [int(f.readline()) for i in range(n)]
ans2 = sol(2, data)
ans6 = sol(6, data)
# Эквивалентные выводы
print(ans2[0] - ans6[0])
print(ans6[2] + ans6[4])

Ответ: 349440 422550200076076467165612474368