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

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

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

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

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

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

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

Начало «пусто»: К: 54, О: 54, С: 54, У: 108, Ф: 0; выбираем У.
Начало «У»: К: 27, О: 27, С: 27, У: 27, Ф: 0; выбираем У.
Начало «УУ»: К: 9, О: 9, С: 9, У: 0, Ф: 0; выбираем С.
Начало «УУС»: К: 3, О: 3, С: 3, У: 0, Ф: 0; выбираем С.
Начало «УУСС»: К: 1, О: 1, С: 1, У: 0, Ф: 0; выбираем С.

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

Код слова: 33222.
Место 1: У → 3; вклад = 3 · 5⁴ = 1875.
Место 2: У → 3; вклад = 3 · 5³ = 375.
Место 3: С → 2; вклад = 2 · 5² = 50.
Место 4: С → 2; вклад = 2 · 5¹ = 10.
Место 5: С → 2; вклад = 2 · 5⁰ = 2.

N = 1 + 1875 + 375 + 50 + 10 + 2 = 2313.

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

Ответ: 2313.