Алфавит в порядке возрастания: А, Б, В, Г. Рассматриваются… — ЕГЭ по информатике

ЕГЭ Информатика сложность в тренажёре: высокая

Алфавит в порядке возрастания: А, Б, В, Г. Рассматриваются все слова длины 9 из букв этого алфавита. Словом считается любая последовательность букв… Ответ и подробный разбор. ЕГЭ по информатике, тема «Правило умножения и кодовые слова».

Условие

Алфавит в порядке возрастания: А, Б, В, Г.

Рассматриваются все слова длины 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

Открыть тренажёр

Система Git появилась в 2005 году для работы над ядром Linux. Она хранит историю изменений, а ветки позволяют разрабатывать несколько вариантов проекта параллельно и затем объединять результаты.

Формулы и приём

Число кодовых слов

Сколько разных паролей из 4 цифр можно составить?

N = mk

N
количество различных слов, штук
m
размер алфавита (сколько символов доступно), штук
k
длина слова, символов

На каждую позицию — m вариантов, позиций k. Для четырёхзначного PIN это 10⁴ = 10 000 комбинаций: перебрать их вручную нереально, а компьютером — мгновенно.

Формула считает варианты С ПОВТОРЕНИЯМИ: «1111» тоже пароль.

Условие Фано

Как код читается однозначно, если между буквами нет разделителей?

ни одно кодовое слово — не начало другого → сообщение декодируется однозначно

Если ни одно кодовое слово не совпадает с началом другого, сообщение читается слева направо без запятых единственным способом. Код {0, 10, 110, 111} условие выполняет: строка 0110111 разбирается только как 0|110|111. В задании 4 из подходящих вариантов выбирай самое короткое слово, которое не нарушает условие для всего набора.

Достаточно любого из двух условий: прямого Фано (не начало другого) или обратного (не окончание другого) — второе означает однозначное чтение справа налево. Проверять оба сразу не требуется.

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.