Задание №8 — Комбинаторика
Все шестибуквенные слова, в составе которых могут быть только русские буквы П, О, Л, Ь, З, А, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка.
1. АААААА
2. АААААЗ
3. АААААЛ
4. АААААО
5. АААААП
6. АААААЬ
7. ААААЗА
...
Под каким номером в списке идёт первое слово, которое содержит не более одной буквы Ь, ровно одну букву А и не более двух букв З?
Правильный ответ
1599
Пояснение
Решение:
Буквы в алфавитном порядке: А, З, Л, О, П, Ь. Наименьшее подходящее слово строим жадно, слева направо выбирая минимальную букву, при которой оставшиеся условия ещё выполнимы.
Условия: буква Ь не более одного раза, буква А ровно один раз, буква З не более двух раз.
- 1-я буква — А (нужна ровно одна А, и выгодно поставить её первой, потому что А — минимальная буква);
- 2-я и 3-я — З: вторую А ставить нельзя, следующая по алфавиту буква З, а её разрешено использовать дважды;
- 4-я, 5-я и 6-я — Л: А исчерпана, З уже две, поэтому минимальная доступная буква — Л (ограничений на Л нет).
Получилось слово АЗЗЛЛЛ. Заменим буквы цифрами шестеричной системы (А=0, З=1, Л=2, О=3, П=4, Ь=5): АЗЗЛЛЛ → , значение Номер слова равен .
from itertools import product
for n, w in enumerate(product('АЗЛОПЬ', repeat=6), 1):
s = ''.join(w)
if s.count('Ь') <= 1 and s.count('А') == 1 and s.count('З') <= 2:
print(n, s)
break
Ответ: 1599