Задание 12. Информатика. ЕГЭ. Статград. 28.01.2025-1

Просмотры: 1390
Изменено: 2 февраля 2025

Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки цифр.
А) заменить \((v, \, w)\).
Эта команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Например, выполнение команды
заменить \((111, \, 27)\)
преобразует строку \(05111150\) в строку \(0527150.\) Если в строке нет вхождений цепочки \(v\), то выполнение команды заменить \((v, \, w)\) не меняет эту строку.
Б) нашлось \((v)\).
Эта команда проверяет, встречается ли цепочка \(v\) в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

  НАЧАЛО
     ПОКА нашлось (111) ИЛИ нашлось (22)
        заменить (111, 2)
        заменить (222, 1)
        заменить (221, 1)
        заменить (122, 1)
        заменить (22, 2)
     КОНЕЦ ПОКА
  КОНЕЦ

Определите, сколько различных строк, содержащих ровно \(5\) единиц, может получиться в результате применения этой программы к строкам, состоящим только из единиц и двоек.

Решение:

Для экспериментов со строками напишем программу.

Python


s = '21121121'

while '111' in s or '22' in s:
    s = s.replace('111', '2', 1)
    s = s.replace('222', '1', 1)
    s = s.replace('221', '1', 1)
    s = s.replace('122', '1', 1)
    s = s.replace('22', '2', 1)

print(s)

Нетрудно заметить, что строка не будет меняться циклом, если ней нет трёх и более подряд стоящих \(1\) и двух и более стоящих \(2\). Всего имеем три типа таких строк:
\(X1121121Y\)
\(X11212121Y
\(X121212121Y\)
Здесь вместо \(X\) и \(Y\) обозначает либо символ \(2\) либо отсутствие какого-либо символа (пустой символ). Строки первого типа — это строки, в которых есть две пары единиц \(11\) и одна единица \(1\). Всего существует три разных строк такого типа (одну единственную единицу мы можем поставить либо на первое место, либо на второе, либо на третье). С учётом того, что \(X\) и \(Y\) могут принимать два разных значения, получаем, что строк первого типа всего \(3 \cdot 4 = 12.\) Аналогично определяем, что разных строк второго типа \(4 \cdot 4 = 16,\) а третьего типа \(4 \cdot 1 = 4.\) Всего получаем \(12 + 4 + 16 = 32.\)

Ответ: \(32\)