Question

Все пятибуквенные слова, составленные из букв Б, А, Т, Ы, Р, записаны в алфавитном порядке и пронумерованы начиная с 1. Начало списка:

1. ААААА
2. ААААБ
3. ААААР
4. ААААТ
5. ААААЫ
6. АААБА
...

Найти номер первого слова, которое не содержит букву Ы и не содержит двух подряд идущих букв А.

Accepted Answer

131

Answer

Идея решения: закодировать буквы цифрами (А → 0, Б → 1, Р → 2, Т → 3, Ы → 4), найти первое слово, удовлетворяющее условиям, интерпретировать его как число в пятеричной системе и перевести в десятичную.

Первое слово без буквы Ы и без двух подряд идущих А — это АБАБА. Это слово минимально в лексикографическом порядке среди всех подходящих.

Закодируем АБАБА в виде последовательности цифр: 01010 (в пятеричной системе).

Переведём $01010_5$ в десятичную систему:

$$01010_5 = 0 \cdot 5^4 + 1 \cdot 5^3 + 0 \cdot 5^2 + 1 \cdot 5^1 + 0 \cdot 5^0 = 125 + 5 = 130_{10}$$

Поскольку нумерация начинается с 1, а не с 0, номер слова АБАБА равен $130 + 1 = 131$.

Проверим перебором:

```python
from itertools import product

count = 0
for word_tuple in product('АБРТЫ', repeat=5):
    word = ''.join(word_tuple)
    count += 1
    if 'Ы' not in word and 'АА' not in word:
        print(count)
        break
```

Программа выведет 131.

Задание №8Системы счисления и арифметикаЕГЭ по информатике