Задание 12 из ЕГЭ по информатике: задача 2

Изменения ЕГЭ-2026

Исполнитель МТ представляет собой читающую и записывающую головку, которая может перемещаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (A = {a0, a1, …, an–1}), включая специальный пустой символ λ.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний (Q = {q0, q1, …, qn–1}. В начальный момент времени головка находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

• Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
• Или заменить символ в текущей ячейке без перемещения;
• После выполнения действия перейти в новое состояние или остаться в прежнем.

Программа работы исполнителя задаётся в табличном виде. В первой строке перечислены все возможные символы ленты, в первой колонке – возможные состояния головки. На пересечении строки и столбца указана команда, которую выполняет МТ, когда головка обозревает данный символ, находясь в данном состоянии. Пустая клетка означает невозможную комбинацию.

Каждая команда имеет три элемента, разделённых запятой:

1. Символ, записываемый в текущую ячейку;
2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
3. Новое состояние головки после выполнения команды.

Например, команда 0, L, q3 означает: в текущую ячейку записать символ «0», сдвинуться в соседнюю ячейку слева и перейти в состояние q3.

Выполните задание:

В начальный момент времени на ленте подряд записана последовательность из 600 символов, включающая только 0 и 1. Остальные ячейки заполнены λ. Головка расположена на левой границе последовательности (не на пустом символе) и находится в состоянии q1.

Программа работы исполнителя

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

Вопрос:определите максимально возможное количество нулей в исходной последовательности