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

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

Даны числа $K0$ , $K1$ и $K2$ , которые являются количествами чисел с соответствующими остатками при делении на $3$ , указанными в названии. Нужно найти количество подмножеств, сумма элементов которых делится на $3$ .

from math import comb

f = open(’2.txt’)
ans = 0
k = [int(f.readline()) for _ in range(3)]

s2 = [0, 0, 0]
for i in range(3):
    for j in range(i, k[2] + 1, 3):
        s2[i] += comb(k[2], j)

s1 = [0, 0, 0]
for i in range(3):
    for j in range(i, k[1] + 1, 3):
        s1[i] += comb(k[1], j)

ans = s1[0] * s2[0] + s1[1] * s2[1] + s1[2] * s2[2]
ans = ans * 2 ** k[0]

print(ans)

Ответ: 11665337198842730263320011877960647281883570298097132994270776567519749329063338257192070288909533184