Задание EGEINF043370: Подсчёт слов и последовательностей

Длина слова n = 6. Алфавит в порядке возрастания: А, Г, М, Н, С, Т, У. Всего букв b = 7; повторения букв разрешены.

Сопоставим буквам цифры от 0 до b − 1: А → 0, Г → 1, М → 2, Н → 3, С → 4, Т → 5, У → 6. Алфавитное сравнение слов одинаковой длины совпадает со сравнением позиционных записей: решает первая различающаяся буква слева. Начальные нули сохраняем, поскольку длина слова фиксирована.

Номер в списке на единицу больше значения записи. Для цифр d₁, …, dₙ формула имеет вид N = 1 + d₁ · bⁿ⁻¹ + d₂ · bⁿ⁻² + … + dₙ. Единица нужна потому, что первое слово состоит из минимальных букв, его код равен нулю, а номер равен 1.

Условия отбора: первая буква не входит в У; число букв М от 2 до 2 включительно; число букв Г от 0 до 1 включительно.

Докажем выбор слова последовательно слева направо. D(q) — число допустимых полных слов с началом q. Для полного слова D равно 1, если выполнены все ограничения, иначе 0. Для более короткого начала D(q) = сумма D(qc) по всем буквам c. Так перебираются все продолжения без пропусков и повторов; запрещённая буква, лишнее вхождение или запрещённая соседняя пара сразу дают ноль.

На каждом шаге выбираем наибольшую букву с положительным числом продолжений. Ниже числа D(qc) перечислены в порядке алфавита АГМНСТУ. Нули у всех более подходящих букв доказывают невозможность улучшить выбор.

Начало «пусто»: А: 2000, Г: 1250, М: 5625, Н: 2000, С: 2000, Т: 2000, У: 0; выбираем Т.
Начало «Т»: А: 210, Г: 150, М: 800, Н: 210, С: 210, Т: 210, У: 210; выбираем У.
Начало «ТУ»: А: 18, Г: 15, М: 105, Н: 18, С: 18, Т: 18, У: 18; выбираем У.
Начало «ТУУ»: А: 1, Г: 1, М: 12, Н: 1, С: 1, Т: 1, У: 1; выбираем У.
Начало «ТУУУ»: А: 0, Г: 0, М: 1, Н: 0, С: 0, Т: 0, У: 0; выбираем М.
Начало «ТУУУМ»: А: 0, Г: 0, М: 1, Н: 0, С: 0, Т: 0, У: 0; выбираем М.

Полученное слово: ТУУУММ.

Код слова: 566622.
Место 1: Т → 5; вклад = 5 · 7⁵ = 84035.
Место 2: У → 6; вклад = 6 · 7⁴ = 14406.
Место 3: У → 6; вклад = 6 · 7³ = 2058.
Место 4: У → 6; вклад = 6 · 7² = 294.
Место 5: М → 2; вклад = 2 · 7¹ = 14.
Место 6: М → 2; вклад = 2 · 7⁰ = 2.

N = 1 + 84035 + 14406 + 2058 + 294 + 14 + 2 = 100810.

Проверка: из N − 1 = 100809 последовательным делением с остатком на 7 восстанавливается код 566622 длины 6, то есть слово ТУУУММ. Оно удовлетворяет всем ограничениям. Таблица продолжений исключила все слова, которые могли бы дать лучший номер.

Ответ: 100810.