Задание №8. Подсчёт слов и чисел, порядок в списке

В задании №8 из заданных букв или цифр составляются последовательности. Требуется либо посчитать подходящие последовательности, либо найти место слова в упорядоченном списке. Эти вопросы используют одни ограничения, но разные ответы: количество найденных слов не равно номеру последнего из них.

Что именно составляется

Алфавит — набор разрешённых символов. Слово в таких задачах — любая последовательность заданной длины, даже бессмысленная. Если символов в алфавите q, длина слова n, повторения разрешены и иных ограничений нет, каждую из n позиций можно заполнить q способами. Всего получается q^n слов.

У записи числа есть дополнительное ограничение: первая цифра не может быть нулём. Поэтому строка 01234 допустима как пятисимвольный код, но не является записью пятизначного числа. Для q-ичной системы доступны цифры со значениями от 0 до q-1.

Номер слова: сначала слова перед ним

В задании EGE-08-0022 ↗ шестибуквенные слова из букв А, В, О, Р, Т записаны по алфавиту. Первое слово АААААА имеет номер 1. Требуется номер слова ВОРОТА.

Лексикографический порядок позволяет считать целые группы слов, не выписывая список. Перед ВОРОТА идут:

Эти группы не пересекаются: первое отличие от ВОРОТА у каждой группы на своём месте. Перед нужным словом находятся 3125+1250+375+50+20=4820 слов. Само слово занимает следующее место, поэтому ответ: 4821.

Тот же расчёт кратко записывается через цифры: \text{А}\to0,\ \text{В}\to1,\ \text{О}\to2,\ \text{Р}\to3,\ \text{Т}\to4. ВОРОТА превращается в 132240_5. Значение этой записи равно числу предшествующих слов, поэтому номер равен 132240_5+1=4821. Начальные нули у такой записи допустимы: они обозначают первые буквы алфавита.

Слово по номеру

Обратный переход начинается с вычитания единицы. В EGE-08-0122 ↗ требуется четырёхбуквенное слово под номером 65 для алфавита Е, И, О, У. Перед ним стоят 65-1=64 слова. Так как алфавит содержит четыре буквы, число 64 записывается в основании 4: 64=1\cdot4^3+0\cdot4^2+0\cdot4+0.

Полученная запись 1000_4 заменяется буквами: 1 — И, 0 — Е. Ответ: ИЕЕЕ. Если цифр меньше длины слова, слева добавляются нули до нужной длины. Они возвращают первые буквы, а не меняют числовое значение.

Первое подходящее слово и чётность номера

В EGE-08-0001 ↗ алфавит из слова АПРЕЛЬ упорядочен так: А, Е, Л, П, Р, Ь. Среди шестибуквенных слов нужно первое с нечётным номером, которое не начинается с А или Л и содержит не менее двух П.

Наименьшая допустимая первая буква — Е. Чтобы слово было как можно раньше, следующие позиции заполняются наименьшими буквами А, пока остаётся место для двух П. Без условия о номере получилось бы ЕАААПП, но его последняя буква П имеет код 3.

В основании 6 все веса разрядов, кроме последнего, чётные. Поэтому чётность числа предшествующих слов определяется последней цифрой. Номер на единицу больше этого числа: нечётному номеру нужна чётная последняя цифра. Значит, заканчивать на П нельзя. Самое раннее подходящее слово — ЕААППА: обе П сдвинуты на последние возможные места перед конечной А.

Его цифры — 100330_6, а номер равен 6^5+3\cdot6^2+3\cdot6+1=7903. Ответ: 7903. Начало ЕААА невозможно сохранить: в двух оставшихся позициях пришлось бы поставить ПП, что нарушает условие о номере.

Тот же поиск можно выполнить полным перебором. В Python product перебирает последовательности в порядке переданного алфавита, а enumerate(..., start=1) присваивает им номера исходного списка.

from itertools import product

alphabet = 'АЕЛПРЬ'
for number, letters in enumerate(product(alphabet, repeat=6), start=1):
    word = ''.join(letters)
    if number % 2 == 1 and word[0] not in 'АЛ' and word.count('П') >= 2:
        print(number, word)
        break

Программа выводит 7903 ЕААППА. Полный набор содержит 6^6=46656 слов; перебор идёт по порядку и останавливается на первом подходящем. Нумерация идёт до отбора: неподходящие слова тоже занимают места в исходном списке.

Если требуется последнее слово, как в EGE-08-0003 ↗, ранняя остановка не подходит: сохраняется каждый найденный номер, и после полного прохода остаётся последний. При поиске количества вместо номера увеличивается отдельный счётчик подходящих слов. Эти два счётчика нельзя заменять друг другом.

Подсчёт по позициям

В EGE-08-0044 ↗ составляются пятибуквенные слова из В, О, Л, К, причём В встречается ровно один раз. Сначала выбирается место для В: 5 вариантов. Каждая из четырёх оставшихся позиций заполняется одной из трёх других букв. Повторения О, Л и К разрешены, поэтому число вариантов равно 5\cdot3^4=405.

Множитель 3, а не 4 нужен именно из-за слова «ровно»: если оставить В среди вариантов для свободных мест, появятся слова с несколькими В. Если требуется ровно одна буква из группы, выбирается ещё и сама буква. В EGE-08-0057 ↗ гласные Э и А занимают одно место в пятибуквенном слове, остальные места заполняются согласными Т и Н. Получается 5\cdot2\cdot2^4=160 слов.

«Не более» объединяет несколько случаев, включая ноль вхождений; «не менее» допускает и больше указанного числа. Для сложных сочетаний ограничений удобен перебор, в котором каждое условие записано отдельно. Например, EGE-08-0010 ↗ допускает ноль, одну или две семёрки, а не только две.

Различные цифры и соседство

В EGE-08-0025 ↗ считаются десятичные четырёхзначные числа с различными цифрами и без соседних цифр одинаковой чётности. Возможны два порядка: чётная, нечётная, чётная, нечётная или наоборот.

• При первой чётной цифре доступны 2, 4, 6, 8: четыре варианта. Нечётных цифр пять. На третьей позиции остаются четыре чётные цифры, включая 0, а на четвёртой — четыре ещё не использованные нечётные. Получается 4\cdot5\cdot4\cdot4=320.
• При первой нечётной цифре есть пять вариантов. На второй позиции допустимы все пять чётных цифр, включая 0. После использования одной цифры каждого вида остаётся по четыре варианта: 5\cdot5\cdot4\cdot4=400.

Случаи различаются первой цифрой и не пересекаются, поэтому количества складываются: 320+400=720. Ответ: 720. Независимый программный подсчёт задаётся теми же ограничениями:

from itertools import permutations

count = 0
for digits in permutations(range(10), 4):
    if digits[0] == 0:
        continue
    if all(a % 2 != b % 2 for a, b in zip(digits, digits[1:])):
        count += 1
print(count)

permutations выбирает четыре различные цифры с учётом порядка. zip(digits, digits[1:]) образует пары соседей, а all требует выполнения условия для каждой пары. Для задач с разрешёнными повторениями вместо permutations нужен product.

Дополнительное ограничение на последнюю цифру применяется вместе с остальными. Например, десятичное число, делящееся на 5, заканчивается на 0 или 5: это сужает последнюю позицию в EGE-08-0018 ↗, но не отменяет различие цифр и чередование их чётности. Для других систем счисления правило делимости по последней цифре нельзя переносить без обоснования.

Запрет соседства может относиться только к особой цифре. В EGE-08-0008 ↗ ровно один ноль в девятеричном числе не должен соседствовать с нечётной цифрой. Проверяются обе стороны нуля; на краю сосед только один. Запрет всех нечётных цифр в числе был бы сильнее исходного условия и исключил бы допустимые варианты.

Возможные ловушки

• Буквы перечислены в порядке исходного слова. В EGE-08-0001 ↗ порядок АПРЕЛЬ не совпадает с порядком списка АЕЛПРЬ. Неверный алфавит меняет места всех слов. Надёжная опора — заданный порядок и приведённое начало списка.
• Номер начинается с нуля. В EGE-08-0022 ↗ позиционная запись даёт 4820 предшествующих слов, а нужен номер 4821. При обратном переходе, как в EGE-08-0122 ↗, единица сначала вычитается.
• Нумеруются только отобранные слова. В EGE-08-0001 ↗ это меняет и номер, и его чётность. Номер исходного списка присваивается каждому слову до проверки ограничений.
• Чётность номера всегда определяется последней буквой. При нечётном размере алфавита это неверно. В EGE-08-0017 ↗ букв семь, все степени семёрки нечётны, поэтому в чётность значения записи вносят вклад все цифры. Прямой расчёт номера через enumerate сохраняет условие без такого упрощения.
• Ноль исключён из всех позиций. В EGE-08-0025 ↗ он запрещён только в начале. Полное исключение нуля теряет допустимые числа; разрешение его в начале добавляет более короткие числа.
• Проверено лишь одно направление соседства. В EGE-08-0008 ↗ запрещены и пара 01, и пара 10. Проверка только символа после нуля пропустит нечётную цифру перед ним.