Решения заданий ФИПИ ЕГЭ по информатике: «Алгоритмы и исполнители» — с ответами

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

После нескольких замен образуются цепочки из цифр 2. Как только появляется 22222, срабатывает первая ветвь условия: первое вхождение 22222 заменяется на 99.

Двоичное представление числа 2027 без ведущих нулей:$$2027_{10}=11111101011_2$$

Головка начинает работу с пустой ячейки справа, затем движется влево. Последовательно применяем команды программы к символам двоичной записи.

Символ «>» последовательно перемещается вправо по строке, обрабатывая каждую цифру. Порядок расположения цифр не влияет на итоговый вклад каждой цифры.

При обработке цифры 1 выполняется замена $>1 \to 22>$, поэтому одна цифра 1 превращается в две цифры 2 и даёт вклад $2 \cdot 2 = 4$.$$10 \cdot 4 = 40$$

Порядок цифр во входной строке не влияет на итоговое количество цифр: символ «>» последовательно обрабатывает каждую цифру.

Каждая цифра 1 заменяется двумя цифрами 2. Поэтому 11 единиц дают $11 \cdot 2 = 22$ двойки.$$1 \to 22$$

В начале строка имеет вид $10^{90}$: одна единица и 90 нулей справа от неё.

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

В начале строки есть только цепочка 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$.

Представим число 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.