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

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

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны.

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

Уникальным множеством считается то, что встречается один раз (то есть перестановки элементов внутри множества не делают его уникальным).

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

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

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

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

ans = 0
for i in range(1, 2**n): # i = 0 нам не подходит, так как задает пустое подмножество
    t = i
    mn = []
    for j in range(n):
        if t % 2 == 1:
            mn.append(nums[j])
        t //= 2
        if len(mn) > 10:
            break

    if len(mn) == 10 and sum(mn) % 3 != 0:
            ans += 1

print(ans)

Ответ: 123157