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