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

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

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

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

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

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

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

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

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

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

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

На ленте в соседних ячейках записана последовательность из 900 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности и находится в состоянии q0.

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

После выполнения программы на ленте осталось ровно 50 нулей.

Вопрос

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