Задание №8 — Комбинаторика
Все пятибуквенные слова, в составе которых могут быть только русские буквы П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка.
1. ААААА
2. ААААП
3. ААААР
4. ААААС
5. ААААУ
6. АААПА
…
Под каким номером в списке идёт последнее слово, которое содержит не более одной буквы У и не содержит букв А, стоящих рядом?
Правильный ответ
2969
Пояснение
Решение:
Выпишем используемые буквы в алфавитном порядке: А, П, Р, С, У. Нужно последнее подходящее слово списка, то есть самое «старшее» по алфавиту слово, в котором буква У встречается не более одного раза и нет двух букв А подряд.
Строим его жадно, слева направо, беря на каждом месте максимально возможную букву. На первое место ставим У — это допустимо, ведь одна У разрешена. После этого У использовать уже нельзя, и старшая из оставшихся букв — С. Букв С подряд может стоять сколько угодно (ограничение касается только буквы А), поэтому остальные четыре места заполняем буквой С. Получаем слово УСССС: в нём одна У и нет сочетания АА.
Теперь найдём его номер. Занумеруем буквы по алфавиту: А — 0, П — 1, Р — 2, С — 3, У — 4. Тогда пятибуквенное слово превращается в пятизначное число в пятеричной системе счисления, а номер слова в списке на единицу больше значения этого числа (первому слову ААААА соответствует число 0).
Слову УСССС отвечает набор цифр 4, 3, 3, 3, 3:
Значит, слово УСССС стоит под номером .
from itertools import product
alpha = 'АПРСУ' # буквы уже в алфавитном порядке
answer = 0
for i, w in enumerate(product(alpha, repeat=5), 1):
s = ''.join(w)
if s.count('У') <= 1 and 'АА' not in s:
answer = i # запоминаем последнее подходящее слово
print(answer) # 2969
Ответ: 2969