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

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

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

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

Условия отбора: число букв И от 1 до 1 включительно; запрещены соседние пары УУ.

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

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

Начало «пусто»: И: 560, Р: 472, С: 472, Т: 472, У: 408, Ц: 472; выбираем Ц.
Начало «Ц»: И: 116, Р: 73, С: 73, Т: 73, У: 64, Ц: 73; выбираем Ц.
Начало «ЦЦ»: И: 24, Р: 10, С: 10, Т: 10, У: 9, Ц: 10; выбираем Ц.
Начало «ЦЦЦ»: И: 5, Р: 1, С: 1, Т: 1, У: 1, Ц: 1; выбираем Ц.
Начало «ЦЦЦЦ»: И: 1, Р: 0, С: 0, Т: 0, У: 0, Ц: 0; выбираем И.

Полученное слово: ЦЦЦЦИ.

Код слова: 55550.
Место 1: Ц → 5; вклад = 5 · 6⁴ = 6480.
Место 2: Ц → 5; вклад = 5 · 6³ = 1080.
Место 3: Ц → 5; вклад = 5 · 6² = 180.
Место 4: Ц → 5; вклад = 5 · 6¹ = 30.
Место 5: И → 0; вклад = 0 · 6⁰ = 0.

N = 1 + 6480 + 1080 + 180 + 30 + 0 = 7771.

Проверка: из N − 1 = 7770 последовательным делением с остатком на 6 восстанавливается код 55550 длины 5, то есть слово ЦЦЦЦИ. Оно удовлетворяет всем ограничениям. Таблица продолжений исключила все слова, которые могли бы дать лучший номер.

Ответ: 7771.