Информатика ЕГЭ — решения заданий ФИПИ с ответами

Для каждого целого $n>3$ формируем начальную строку вида $3$ и $n$ цифр «5», затем последовательно применяем команды программы до тех пор, пока в строке встречается хотя бы одна из цепочек $25$, $355$ или $555$.$$s=3\underbrace{55\ldots5}_{n}$$

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

Пока в строке есть пять единиц подряд, заменяем цепочку 11111 на 88. Из 83 единиц можно выполнить 16 таких замен, так как 83 = 16 · 5 + 3.$$83 - 16 \cdot 5 = 3$$

После 16 замен образуется строка из 32 восьмёрок и 3 единиц.$$16 \cdot 88 + 111 = 8^{32}1^3$$

Изначально единица стоит перед 55 нулями, поэтому в строке есть цепочка $10$.

Каждое выполнение команды заменить (10, 001) увеличивает число нулей на один и перемещает единицу на одну позицию вправо.

Представим число 1514 в двоичной системе счисления.$$1514 = 2^{10}+2^8+2^7+2^6+2^5+2^3+2^1 = 10111101010_2$$

В состоянии q₀ головка с пустой ячейки справа сдвигается влево и переходит в состояние q₁.

Пока в строке есть цепочка 11111, она заменяется на 88. Из 84 единиц можно выполнить 16 таких замен, так как 84 = 16 · 5 + 4.$$84 - 16 \cdot 5 = 4$$

Каждая из 16 замен добавляет две цифры 8, поэтому образуется цепочка из 32 цифр 8, после которой стоят 4 цифры 1.$$16 \cdot 2 = 32$$

Цикл продолжается, пока хотя бы одна из сторон — сверху или слева — свободна. Поэтому остановка происходит только в клетке, где сверху и слева находятся стены.

В каждой рабочей клетке робот выбирает единственное направление: вверх, если сверху свободно, и влево — иначе. Движение всегда направлено к верхней или левой границе, поэтому циклического движения нет.

Представим число 2025 в двоичной системе счисления.$$2025_{10}=11111101001_2$$

В состоянии q_0 головка из ближайшей справа пустой ячейки перемещается влево и переходит в состояние q_1.

При обработке цифры 1 команда заменяет «>1» на «2>», поэтому одна цифра 1 даёт сумму 2.$$1 \to 2,\quad S_1=2$$

При обработке цифры 2 команда заменяет «>2» на «21>», поэтому одна цифра 2 даёт сумму 3.$$2 \to 21,\quad S_2=2+1=3$$

В начале строка состоит из 96 цифр 9. Пока в ней нет цепочки 22222, программа заменяет первые найденные четыре цифры 9 на одну цифру 2.

После появления цепочек из пяти цифр 2 срабатывает первая ветвь ЕСЛИ: первая найденная цепочка 22222 заменяется на 99.

Каждая команда меняет местами соседнюю пару цифр, стоящих в неправильном порядке: 21, 31 или 32.$$21\to12,\quad 31\to13,\quad 32\to23$$

При каждой такой замене число инверсий в строке уменьшается. Цикл завершается только тогда, когда ни одной пары 21, 31 или 32 не осталось, то есть строка упорядочена по возрастанию.

В исходной строке 81 единица. Пока остаётся цепочка 1111, программа заменяет четыре единицы на три восьмёрки.

После 19 таких замен останется 5 единиц и появится 57 восьмёрок. Ещё одна замена преобразует четыре из пяти единиц в три восьмёрки:$$1^{81} \rightarrow 8^{60}1$$

Число 1023 в двоичной системе записывается десятью единицами: $1111111111_2$.

После выполнения команд машины на ленте получается двоичная запись следующей степени двойки: $10000000000_2$.$$10000000000_2 = 2^{10}$$

Каждая команда замены изменяет только порядок двух соседних цифр, поэтому длина строки и количества цифр 4, 7 и 9 сохраняются.

Цикл выполняется до тех пор, пока в строке есть хотя бы одна из пар $47$, $49$ или $97$. При каждом проходе первое слева вхождение каждой найденной пары заменяется на $74$, $94$ или $79$ соответственно.

Символ «>» перемещается вправо по строке. При обработке цифры 1 команда заменяет цепочку $>1$ на $22>$, поэтому каждая исходная цифра 1 даёт две цифры 2 и увеличивает сумму на 4.$$15 \cdot (2 + 2) = 60$$

При обработке цифры 2 цепочка $>2$ заменяется на $2>$, поэтому цифра 2 сохраняется и даёт вклад 2.$$20 \cdot 2 = 40$$

В начале в строке нет цепочки 999, поэтому программа заменяет первое вхождение 333 на 9. Из 92 цифр 3 образуются 30 цифр 9 и 2 цифры 3.$$92 = 30 \cdot 3 + 2$$

Пока в строке есть 999, программа заменяет первое такое вхождение на 3. Десять таких замен уничтожают 30 цифр 9 и добавляют 10 цифр 3 к двум оставшимся, поэтому получается 12 цифр 3.$$30 \to 0,\quad 2+10=12$$

На первом этапе программа заменяет вхождения 1111 на 888. Из 81 единицы можно выполнить 20 таких замен, поскольку 81 = 4 · 20 + 1.$$1^{81} \rightarrow 888^{20}1$$

После этого цепочки 1111 нет, но имеется цепочка из 60 восьмёрок. Каждая замена 88888 на 888 уменьшает её длину на 2.

Пусть текущая строка имеет вид $5 2^m$. Если $m \geq 2$, замена $522$ на $27$ даёт строку $27 2^{m-2}$.$$5 2^m \to 27 2^{m-2}$$

Затем первое вхождение $72$ заменяется на $2$, поэтому получается строка из $m-1$ цифр «2».$$27 2^{m-2} \to 2^{m-1}$$

Пока в строке нет пяти цифр 2 подряд, выполняется замена первого фрагмента $9999$ на $2$. Для достаточно длинной последовательности из девяток пять таких замен дают $22222$.$$9999 \to 2$$

Когда появляется фрагмент $22222$, он заменяется на $99$. Поэтому после полного цикла количество девяток уменьшается на 18: четыре заменённых блока содержат 20 девяток, а результат добавляет 2 девятки.$$n \to n - 20 + 2 = n - 18$$

Изначально строка содержит 84 цифры 8. Пока в ней нет цепочки $1111$, программа заменяет первое слева вхождение $8888$ на $11$.

Когда в строке появляется цепочка $1111$, условие первой ветви становится истинным, и первое вхождение $1111$ заменяется на одну цифру $8$. Далее снова выполняется поиск $1111$, а при его отсутствии — замена $8888$ на $11$.

Для каждого значения $n$ моделируем работу цикла: сначала заменяем найденную цепочку $73$, затем $322$, затем $2222$. После каждой итерации проверяем условие продолжения цикла.

Для значений $n$, меньших 12, сумма цифр итоговой строки не равна 15.