Задача к ЕГЭ по информатике на тему «исполнитель «редактор»

Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

А) $заменить (v,w)$ .

Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$ . Например, выполнение команды

$заменить (111,27)$

преобразует строку $05111150$ в строку $0527150$ .

Если в строке нет вхождений цепочки $v$ , то выполнение команды заменить $(v,w)$ не меняет эту строку.

Б) $нашлось (v)$ .

Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

$П ОК А усл овие$

$посл едовательность ком анд$

$К ОН ЕЦ ПО КА$

выполняется, пока условие истинно.

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

$Н АЧА ЛО$

$П ОК А нашлось (4444)$

$зам енить (444,333)$

$зам енить (33,44)$

$К ОН ЕЦ ПО КА$

$К ОНЕ Ц$

Известно, что исходная строка содержала более $100$ четверок и не содержала других цифр. Укажите минимально возможную длину исходной строки, при которой в результате работы этой программы получится строка, содержащая минимально возможное четное количество четверок.

Изначально не совсем понятно как конечное количество четвёрок зависит от начального. Попробуем проделать вручную операции над несколькими строками. Пусть $n$ — начальное количество четверок.

1) $n = 10$ : $4444444444 → 4434444444 → 4444334444 → 4434334444 → 4434443334.$ Получили $6$ четверок

2) $n = 11$ : $44444444444 → 44344444444 → 44443344444 → 44343344444 → 44344433344.$ Получили $7$ четверок.

3) $n = 12$ : $444444444444 → 443444444444 → 444433444444 → 443433444444 → 443444333444.$ Получили $8$ четверок.

Теперь если мы возьмём $n = 13$ , то получим $4434443333334$ , что очень похоже на случай с $n = 10$ и при этом в строке снова $6$ четверок.

Мы получили закономерность, дальше количество четвёрок будет повторяться $(6,7,8)$ .

Значит нам нужно получить $6$ четверок в конце. Это возможно только при $n$ таком, что его остаток от деления на $3$ равен $1$ .

Минимальное такое число, большее $100$ — $103$ .

naim = 10 ** 10
ans = 0
for i in range(101, 1000):
    s = ’4’ * i
    while ’4444’ in s:
        s = s.replace(’444’, ’333’, 1)
        s = s.replace(’33’, ’44’, 1)
    if s.count(’4’) % 2 == 0 and s.count(’4’) < naim:
        ans = i
        naim = s.count(’4’)
print(ans)

Ответ: 103

Задача к ЕГЭ по информатике на тему «исполнитель «редактор» – прочие прототипы» №3