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