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

Длина слова 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 включительно; номер чётный.

Основание b чётное: все позиционные слагаемые, кроме последнего, чётные. Поэтому чётность N определяется числом 1 + dₙ.

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

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

Начало «пусто»: А: 0, К: 0, О: 225, Р: 225, С: 375, Т: 225; выбираем Т.
Начало «Т»: А: 30, К: 30, О: 30, Р: 30, С: 75, Т: 30; выбираем Т.
Начало «ТТ»: А: 3, К: 3, О: 3, Р: 3, С: 15, Т: 3; выбираем Т.
Начало «ТТТ»: А: 0, К: 0, О: 0, Р: 0, С: 3, Т: 0; выбираем С.
Начало «ТТТС»: А: 0, К: 1, О: 0, Р: 1, С: 0, Т: 1; выбираем Т.

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

Код слова: 55545.
Место 1: Т → 5; вклад = 5 · 6⁴ = 6480.
Место 2: Т → 5; вклад = 5 · 6³ = 1080.
Место 3: Т → 5; вклад = 5 · 6² = 180.
Место 4: С → 4; вклад = 4 · 6¹ = 24.
Место 5: Т → 5; вклад = 5 · 6⁰ = 5.

N = 1 + 6480 + 1080 + 180 + 24 + 5 = 7770.

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

Ответ: 7770.