Задание 12 ЕГЭ по информатике 2027 Генератор вариантов с ответами для учителя

Исполнитель МТ — это читающая и записывающая головка, которая движется вдоль бесконечной ленты, разделённой на ячейки. В каждой ячейке записан один символ алфавита исполнителя; пустой символ обозначается «λ». Головка в каждый момент находится в одном из состояний q₀, q₁, …; в начальный момент — в состоянии q₀. За один такт головка обозревает текущую ячейку, может записать в неё символ и сдвинуться на соседнюю ячейку влево или вправо, после чего переходит в новое состояние (или остаётся в прежнем).
Программа задаётся таблицей: в первой строке — символы, в первом столбце — состояния; на пересечении — команда из трёх элементов через запятую: записываемый символ, «L» (сдвиг влево), «R» (сдвиг вправо) или «S» (остановка после записи) и новое состояние. Пустая клетка — такой пары «символ — состояние» не бывает. Например, программа из одного состояния q₀ с командами «0 → 1, L, q₀», «1 → 0, L, q₀», «λ → λ, S, q₀», запущенная на последней цифре двоичного числа, заменяет каждую цифру противоположной и останавливается в первой ячейке слева от числа.
Выполните задание.
На ленте в соседних ячейках записана последовательность из 800 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.
Программа работы исполнителя — на рисунке.
После выполнения программы на ленте осталось ровно 694 нуля. Определите максимально возможное число нулей в исходной последовательности.