Задача к ЕГЭ по информатике на тему «подсчет количества слов/чисел» №4

Кристина составляет 6-буквенные слова, она может использовать все буквы из слова «ВЪЕЗД». При этом каждая буква может встречаться любое количество раз либо не встречаться вовсе. Твердый знак может стоять только после согласной буквы (причём два твёрдых знака стоять рядом не могут). Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько слов может составить Кристина?

Решение руками

Сначала найдем слова в которых твердого знака нет совсем: $46 = 4096$ .

Теперь найдем все слова, в которых твердый знак встречается 1 раз, так как твердый знак может стоять только после согласной, то рассматривать будем сразу парой (* обозначает любую букву кроме Ъ):

C ⋅Ъ ⋅∗⋅∗⋅∗ ⋅∗

Эта пара может распологаться в слове в 5 местах: с 1 позиции, со 2, с 3, с 4 и с 5. Следовательно таких слов $3 ⋅1⋅44 ⋅5 = 3840$ .

Теперь найдем все слова в которых твердый знак встречается дважды, так как твердый знак может стоять только после согласной, то рассматривать будем сразу парами (* обозначает любую букву кроме Ъ):

C ⋅Ъ ⋅C ⋅Ъ ⋅∗⋅∗

В таком случае существует всего 6 различных вариантов перестановок пар (первый вариант указан выше):

$C ⋅Ъ ⋅∗ ⋅C ⋅Ъ ⋅∗$

$C ⋅Ъ ⋅∗ ⋅∗⋅C ⋅Ъ$

$∗⋅C ⋅Ъ ⋅C ⋅Ъ ⋅∗$

$∗⋅C ⋅Ъ ⋅∗⋅C ⋅Ъ$

$∗⋅∗⋅C ⋅Ъ ⋅C ⋅Ъ$

Следовательно таких слов $3⋅1 ⋅3⋅1⋅42 ⋅6 = 864$ .

Теперь найдем все слова в которых твердый знак встречается трижды, так как твердый знак может стоять только после согласной, то рассматривать будем сразу парами:

C ⋅Ъ ⋅C ⋅Ъ ⋅C ⋅Ъ

Следовательно таких слов $3⋅1 ⋅3⋅1⋅3 ⋅1 = 27$ .

Большее число раз твердый знак встречаться не может. Тогда найдем сумму всех значений: $4096+ 3840 + 864 + 27 = 8827$ .

Решение через циклы

a = ’ВЪЕЗД’

count = set()

for x1 in ’ВЕЗД’: # твердый знак не может стоять на первом месте
    for x2 in a:
        for x3 in a:
            for x4 in a:
                for x5 in a:
                    for x6 in a:
                        s = x1+x2+x3+x4+x5+x6
                        if ’Ъ’ in s:
                            if (’ВЪ’ in s or ’ЗЪ’ in s or ’ДЪ’ in s) and ’ЕЪ’ not in s and ’ЪЪ’ not in s:
                                count.add(s)
                        else:
                            count.add(s)
print(len(count))

Решение через itertools

from itertools import product

count = set()

for x in product(’ВЪЕЗД’,repeat = 6):
    s = ’’.join(x)
    if ’Ъ’ in s and s[0] != ’Ъ’:
        if (’ВЪ’ in s or ’ЗЪ’ in s or ’ДЪ’ in s) and ’ЕЪ’ not in s and ’ЪЪ’ not in s:
            count.add(s)
    elif ’Ъ’ not in s:
        count.add(s)
print(len(count))

Ответ: 8827