Задание 12 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

В начале строки есть только цепочки 999, поэтому на первых шагах заменяется первое вхождение 999 на 3. Постепенно формируется цепочка из цифр 3.

Как только появляются пять подряд идущих цифр 3, условие ЕСЛИ становится истинным, поэтому заменяется цепочка 33333 на 99, а не цепочка 999.

В начале строки есть только цепочка 999, поэтому на каждом шаге первое вхождение 999 заменяется на 3.

После появления пяти подряд идущих цифр 3 начинает выполняться первая ветвь: первое вхождение 33333 заменяется на 99.

В начале строка состоит из 65 цифр 9, поэтому в ней есть цепочка $999$, а цепочки $222$ нет. Выполняется замена первого вхождения $999$ на $2$.

После появления трёх подряд идущих цифр 2 срабатывает условие нашлось (222), и цепочка $222$ заменяется на $19$. Далее снова проверяется строка с начала, поэтому возможные новые вхождения обрабатываются в установленном порядке.

Для каждого значения $n$ формируем исходную строку $5$ и $n$ цифр $2$, затем буквально выполняем команды программы: заменяем первое найденное вхождение $52$, затем первое найденное вхождение $2222$, затем первое найденное вхождение $1122$.

После завершения цикла вычисляем сумму цифр получившейся строки и перебираем значения $n$ в порядке возрастания, начиная с $4$.

Пока в строке встречается $111$, выполняется замена $111 \to 88$. Из 101 единицы можно выделить 33 непересекающиеся группы по 3 цифры, поэтому останутся 2 единицы.$$101 = 33 \cdot 3 + 2$$

Каждая из 33 замен создаёт две цифры 8, поэтому после первого этапа строка содержит 66 восьмёрок и две единицы.$$33 \cdot 2 = 66$$

Представим число 2027 в двоичной системе счисления:$$2027_{10}=11111101011_2$$

Из начальной пустой ячейки справа головка переходит влево и начинает обрабатывать двоичную запись в состоянии q_1. Далее по таблице последовательно выполняются команды состояний q_1, q_2 и q_3.

Пока в строке есть четыре последовательные единицы, программа заменяет 1111 на 888. При делении 91 на 4 получаем 22 полные группы и остаток 3.$$91 = 4 \cdot 22 + 3$$

После этих замен образуются 22 группы 888, то есть 66 восьмёрок, а в конце остаются три единицы.$$22 \cdot 3 = 66$$

В начале строки имеется фрагмент $19$, поэтому при первом выполнении цикла он заменяется на $9$. Строка становится последовательностью из $n$ цифр «9».

Затем программа последовательно заменяет первое вхождение $999$ на $4$. Если после такой замены возникает фрагмент $49$, он заменяется на $91$, а появившийся фрагмент $19$ снова заменяется на $9$.

Пока в строке есть 111, выполняется замена 111 на 88. Из 100 единиц можно выполнить 33 такие замены: останется одна единица, а появится 66 цифр 8.$$100 - 3 \cdot 33 = 1,\quad 2 \cdot 33 = 66$$

После этого строка имеет вид 66 восьмёрок и одна единица. Фрагмента 111 больше нет, поэтому выполняется замена 88888 на 8. Каждая такая замена уменьшает количество восьмёрок на 4.$$66 - 4 \cdot 16 = 2$$

В начале цепочка $22222$ отсутствует, поэтому выполняется замена первого вхождения $9999$ на $2$. Так продолжается до тех пор, пока в строке не появится цепочка из пяти двоек.$$9999 \to 2$$

Как только появляется $22222$, условие ЕСЛИ становится истинным, поэтому выполняется замена $22222$ на $99$, а не замена $9999$ на $2$.$$22222 \to 99$$

Для каждого допустимого значения $n$ рассматриваем исходную строку $5$ и $n$ цифр $2$ и последовательно выполняем команды программы до тех пор, пока в строке остаётся хотя бы одна из цепочек $52$, $2222$ или $1122$.

При моделировании важно выполнять проверки в указанном порядке: замена $52$ на $11$, затем замена $2222$ на $5$, затем замена $1122$ на $25$. Каждая команда заменяет только первое слева вхождение.

Для каждого значения $n>3$ моделируем работу программы: на каждом шаге последовательно выполняем доступные замены $25\to5$, $355\to52$ и $555\to3$.

После каждого прохода проверяем условие цикла. Работа программы заканчивается, когда в строке не остаётся ни одной из цепочек $25$, $355$ и $555$.

В исходной строке 81 единица. Каждая замена $111 \to 88$ удаляет три единицы, поэтому она выполняется $81 : 3 = 27$ раз.$$81 / 3 = 27$$

После этих замен единиц не останется, а число цифр 8 будет равно $27 \cdot 2 = 54$.$$27 \cdot 2 = 54$$

Для каждого $n$ строим исходную строку: цифра 1 и затем $n$ цифр 9.

Пока в строке встречается хотя бы одна из цепочек $19$, $399$ или $999$, последовательно выполняем все три условные команды. В каждой команде заменяется только первое слева вхождение соответствующей цепочки.

Пока в строке есть 9999 и нет 22222, каждая замена 9999 на 2 уменьшает число девяток в четыре раза. Из 104 девяток получается 26 двоек.$$104 : 4 = 26$$

В строке из 26 двоек пять групп по 5 двоек заменяются на 99, остаётся одна двойка. Поэтому получается десять девяток и одна двойка.$$26 = 5 \cdot 5 + 1$$

В строке ‘РОЗА’ четыре символа, поэтому сначала $i = 4$. При $k = 1$ значение $i$ на каждом шаге уменьшается на единицу.$$i=4,3,2,1$$

Символы извлекаются справа налево: сначала ‘А’, затем ‘З’, ‘О’ и ‘Р’.$$a_4=\text{‘А’},\ a_3=\text{‘З’},\ a_2=\text{‘О’},\ a_1=\text{‘Р’}$$

В начале строки нет цепочки 33333, поэтому на каждом шаге заменяется первое вхождение 777 на 3. Процесс продолжается, пока в строке остаётся хотя бы одна такая цепочка.

После образования пяти цифр 3 подряд срабатывает первая ветвь условия: цепочка 33333 заменяется на 7. Затем снова выполняются замены цепочек 777 на 3.

Исходная строка состоит из 70 цифр 6. Так как цепочки 5555 нет, на каждом шаге сначала заменяется первое слева вхождение 6666 на 55.

После каждой замены строка проверяется заново. Когда появляются четыре подряд идущие цифры 5, первое такое вхождение заменяется на 66. Далее снова выполняются доступные замены 6666 на 55.

Для каждого значения $n$ строим начальную строку $3$ и $n$ цифр $9$, затем буквально выполняем команды программы в указанном порядке: сначала при наличии заменяем первое вхождение $39$, после этого заменяем первое вхождение $999$ либо…

После каждой итерации проверяем условие цикла. Выполнение прекращается, когда в строке одновременно отсутствуют цепочки $39$, $999$ и $7777$.

Пока в строке есть цепочка $10$, выполняется замена $10$ на $0001$. Единица перемещается на одну позицию вправо, а число нулей увеличивается на 2.$$10 \to 0001$$

Изначально после единицы находятся 80 нулей, поэтому замена $10$ на $0001$ выполнится 80 раз. После этого единица окажется в конце строки, и цепочки $10$ больше не будет.$$80 \cdot 2 = 160$$