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

Длина слова n = 6. Алфавит в порядке возрастания: А, Е, Л, П, Р, Ь. Всего букв b = 6; повторения букв разрешены.

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

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

Условия отбора: первая буква не входит в А, Л; число букв П от 2 до 6 включительно; номер нечётный.

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

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

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

Начало «пусто»: А: 0, Е: 513, Л: 0, П: 2013, Р: 513, Ь: 513; выбираем Е.
Начало «Е»: А: 48, Е: 48, Л: 48, П: 273, Р: 48, Ь: 48; выбираем А.
Начало «ЕА»: А: 3, Е: 3, Л: 3, П: 33, Р: 3, Ь: 3; выбираем А.
Начало «ЕАА»: А: 0, Е: 0, Л: 0, П: 3, Р: 0, Ь: 0; выбираем П.
Начало «ЕААП»: А: 0, Е: 0, Л: 0, П: 3, Р: 0, Ь: 0; выбираем П.
Начало «ЕААПП»: А: 1, Е: 0, Л: 1, П: 0, Р: 1, Ь: 0; выбираем А.

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

Код слова: 100330.
Место 1: Е → 1; вклад = 1 · 6⁵ = 7776.
Место 2: А → 0; вклад = 0 · 6⁴ = 0.
Место 3: А → 0; вклад = 0 · 6³ = 0.
Место 4: П → 3; вклад = 3 · 6² = 108.
Место 5: П → 3; вклад = 3 · 6¹ = 18.
Место 6: А → 0; вклад = 0 · 6⁰ = 0.

N = 1 + 7776 + 0 + 0 + 108 + 18 + 0 = 7903.

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

Ответ: 7903.