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

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

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

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

Условия отбора: первая буква не входит в Е, К; полностью исключены буквы А; число букв Ц от 1 до 5 включительно; номер чётный.

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

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

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

Начало «пусто»: А: 0, Е: 0, К: 0, Н: 247, Т: 247, Ц: 375; выбираем Н.
Начало «Н»: А: 0, Е: 43, К: 43, Н: 43, Т: 43, Ц: 75; выбираем Е.
Начало «НЕ»: А: 0, Е: 7, К: 7, Н: 7, Т: 7, Ц: 15; выбираем Е.
Начало «НЕЕ»: А: 0, Е: 1, К: 1, Н: 1, Т: 1, Ц: 3; выбираем Е.
Начало «НЕЕЕ»: А: 0, Е: 0, К: 0, Н: 0, Т: 0, Ц: 1; выбираем Ц.

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

Код слова: 31115.
Место 1: Н → 3; вклад = 3 · 6⁴ = 3888.
Место 2: Е → 1; вклад = 1 · 6³ = 216.
Место 3: Е → 1; вклад = 1 · 6² = 36.
Место 4: Е → 1; вклад = 1 · 6¹ = 6.
Место 5: Ц → 5; вклад = 5 · 6⁰ = 5.

N = 1 + 3888 + 216 + 36 + 6 + 5 = 4152.

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

Ответ: 4152.