На вход программы поступает последовательность из N натуральных чисел, все числа в последовательности различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна 2.
Пример входных данных:
Первая строка входного файла содержит число N – общее количество чисел. Каждая из следующих N строк содержит натуральные числа, не превышающих 10 000.
Пример входного файла
3
2
10
5
Для указанных данных ответом будут являться {2}, {10}, {2, 10}, то есть 3.
Решение 1
f = open(’27A.txt’)
n = int(f.readline())
nums = []
for i in range(n):
nums.append(int(f.readline()))
ans = 0
for i in range(2**n):
t = i
mn = []
for j in range(n):
if t % 2 == 1:
mn.append(nums[j])
t //= 2
if len(mn) > 0:
if sum(mn) % 2 == 0:
ans += 1
print(ans)
Решение 2
f = open(’27A.txt’)
n = int(f.readline())
k = 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]
ans_new[x % k] += 1
ans = ans_new[:]
print(ans[0])