Алфавит в порядке возрастания: А, Б, В, Г.
Рассматриваются все слова длины 9 из букв этого алфавита. Словом считается любая последовательность букв, не обязательно имеющая смысл.
В списке оставляют только слова, в которых буква А встречается ровно 3 раза и никакие две соседние буквы не совпадают. Другие буквы могут повторяться, если они не стоят рядом.
Оставшиеся слова располагают в лексикографическом порядке согласно указанному алфавиту: при первом различии раньше идёт слово с меньшей буквой. После фильтрации слова нумеруют подряд начиная с 1.
Слово: БАВБГАБАВ. Каков его номер в этом отфильтрованном списке? В ответе укажите одно целое число.
Ответ и разбор
Ответ: 3395
1. Проверим слово БАВБГАБАВ: длина 9, буква А встречается 3 раза, одинаковых соседних букв нет. Оно входит в список.
2. Считаем слова, стоящие раньше. У каждого из них есть единственная первая позиция, отличающаяся от заданного слова. До неё префикс совпадает, а в ней стоит меньшая буква. Такие блоки не пересекаются.
3. F(k,r,P) — число допустимых продолжений префикса: k — число оставшихся мест; r — сколько букв А ещё нужно; P — тип последней буквы уже выбранного префикса. S означает А, N — любую одну другую букву. Другие буквы равноправны для подсчёта продолжений. Всего букв m=4.
Базы: F(0,0,S)=F(0,0,N)=1 (пустой суффикс); F(0,r,P)=0 при r≠0. При r<0 или r>k ответ 0.
После S нельзя снова брать А; число вариантов другой буквы равно 3. Поэтому F(k,r,S) = 3 · F(k−1,r,N).
После N можно взять А либо одну из 2 других букв, отличных от предыдущей. Поэтому F(k,r,N) = F(k−1,r−1,S) + 2 · F(k−1,r,N).
4. Заполняем строки по возрастанию k, начиная с k=0, по этим двум формулам. Для каждой пары k и r через «/» записаны два числа: F(k,r,S) и F(k,r,N). Пары, где оба числа равны 0, не показаны:
- k=0, r=0: 1/1
- k=1, r=0–1: 3/2 | 0/1
- k=2, r=0–1: 6/4 | 3/5
- k=3, r=0–2: 12/8 | 15/16 | 0/3
- k=4, r=0–2: 24/16 | 48/44 | 9/21
- k=5, r=0–2: 48/32 | 132/112 | 63/90
- k=5, r=3: 0/9
- k=6, r=0–1: 96/64 | 336/272
- k=6, r=2–3: 270/312 | 27/81
- k=7, r=0–1: 192/128 | 816/640
- k=7, r=2–3: 936/960 | 243/432
- k=8, r=0–1: 384/256 | 1920/1472
- k=8, r=2–3: 2880/2736 | 1296/1800
Например, для первого ненулевого блока: F(8,2,S) = 3 · F(7,2,N) = 3 · 960 = 2880. Остальные ячейки получаются так же из предыдущей строки.
5. Ниже — все меньшие префиксы с ненулевым числом продолжений. Если новая буква совпала с предыдущей, весь блок сразу исключаем. Иначе берём F(k,r,P) из таблицы, учитывая и границу префикса с суффиксом:
- позиция 1, А: F(8,2,S) = 2880
- позиция 3, БАБ: F(6,2,N) = 312
- позиция 4, БАВА: F(5,1,S) = 132
- позиция 5, БАВБА: F(4,1,S) = 48
- позиция 5, БАВБВ: F(4,2,N) = 21
- позиция 9, БАВБГАБАБ: F(0,0,N) = 1
Остальные меньшие префиксы дают 0: в них совпадают соседние буквы.
Раньше заданного слова: 2880 + 312 + 132 + 48 + 21 + 1 = 3394.
6. Прибавляем 1 для самого слова: 3394 + 1 = 3395. Ответ: 3395.
Проверка размера всего списка: F(8,2,S) + 3 · F(8,3,N) = 2880 + 3 · 1800 = 8280. Ранг находится строго внутри списка.
На экзамене такой номер удобно проверить программой: перебрать все слова (в Python — функцией itertools.product), отфильтровать и найти номер.
Частая ошибка
Ловушка: нельзя вычислить обычный номер слова в системе счисления и оставить его после фильтрации. Размеры блоков зависят и от остатка нужных букв, и от последней буквы префикса. Нумерация оставшихся слов начинается заново с 1.
Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-lexrank-high-07
Открыть тренажёр