Задание №8 — Комбинаторика
#69530Задание №8ФИПИ
Количество информации
Все шестибуквенные слова, в составе которых могут быть только русские буквы С, О, Р, Н, Я, К, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка.
1. КККККК
2. КККККН
3. КККККО
4. КККККР
5. КККККС
6. КККККЯ
7. ККККНК
...
Под каким номером в списке идёт первое слово, которое содержит не более трёх букв К и ровно две буквы Я?
Правильный ответ
72
Пояснение
Решение:
Буквы в алфавитном порядке: К, Н, О, Р, С, Я. Наименьшее подходящее слово строим жадно, слева направо ставя минимальную букву, при которой условия ещё можно выполнить.
Условия: букв К не более трёх, букв Я ровно две.
- 1-я, 2-я и 3-я буквы — К (минимальная буква, а три К разрешены);
- 4-я буква: К уже нельзя, следующая по алфавиту — Н. Она подходит: тогда на оставшиеся две позиции как раз встанут обе Я;
- 5-я буква не может быть Н (иначе для двух Я останется только одна позиция), поэтому 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('К') <= 3 and s.count('Я') == 2:
print(n, s)
break
Ответ: 72