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

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

Виктор составляет слова длины 6 из букв русского алфавита в верхнем и нижнем регистрах. Все составляемые слова являются палиндромами, в которых все буквы могут встречаться любое количество раз, а символ Й может стоять только рядом с другим символом Й. Сколько слов может составить Виктор?

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

Слова без Й могут быть любыми, слова с И подчиняются определенным правилам:

*** -> ****** — подходит: $64 ⋅64 ⋅64$

**Й -> **ЙЙ** — подходит: $64⋅64⋅2$

*Й* -> *Й**Й* — не подходит

Й** -> Й****Й — не подходит

*ЙЙ -> *ЙЙЙЙ* — подходит: $64 ⋅2⋅2$

Й*Й -> Й*ЙЙ*Й — не подходит

ЙЙ* -> ЙЙ**ЙЙ — подходит: $2 ⋅2⋅64$

ЙЙЙ -> ЙЙЙЙЙЙ — подходит: $2⋅2 ⋅2$

Если сложим все эти выражения, получим ответ: $270856$ .

Решение:

from itertools import product

# Алфавит в верхнем регистре
s = ’АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ’
# Добавляем также алфавит в нижнем регистре
s = s + s.lower()
ans = set()

# Палиндром - значит последние 3 символа это перевернутые первые 3 символа
# значит можем составить только первую половину и мысленно её продублировать и развернуть
for i in product(s, repeat=3):
    word_ = ’’.join(i)
    word = word_.upper()
    # Нужно пропустить неподходящие слова:
    # **Й -> **ЙЙ** - подходит
    # *Й* -> *Й**Й* - не подходит
    # Й** -> Й****Й - не подходит
    # *ЙЙ -> *ЙЙЙЙ* - подходит
    # Й*Й -> Й*ЙЙ*Й - не подходит
    # ЙЙ* -> ЙЙ**ЙЙ - подходит
    # ЙЙЙ -> ЙЙЙЙЙЙ - подходит
    # Делаем вывод, что не подходят слова с одной Й, у которых она не на последнем месте,
    # а также с двумя Й, которые не стоят рядом (в центре не Й)
    if ’Й’ in word:
        if word.count(’Й’) == 1 and word[-1] != ’Й’ or word.count(’Й’) == 2 and word[1] != ’Й’:
            continue
    ans.add(word_)

print(len(ans))

Ответ: 270856