Задача . ЕГЭ-ПОБЕДА №12

Исполнитель МТ представляет собой читающую и записывающую головку, которая может перемещаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов \(A = \{a_0, a_1, \ldots, a_{n-1}\}\)), включая специальный пустой символ λ.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний (\(Q = \{q_0, q_1, \ldots, q_{m-1}\}\)). В начальный момент времени головка находится в начальном состоянии \(q_0\).

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

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

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

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

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

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

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

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

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

Определите наибольшее число, не превышающее 2026, которое может получиться на ленте в результате работы программы.

В ответе запишите получившееся на ленте число в десятичной системе счисления.