ЕГЭ-12. Выполнение алгоритмов для исполнителя (МТ)

*(Г. Гутман) На ленте исполнителя МТ в соседних ячейках записана последовательность из

1000 символов, состоящая из некоторого числа блоков вида (k*'1'+k*'0'), при этом последний блок может быть неполным. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности. Программа для исполнителя:

	λ	0	1
q0	λ, R, q1
q1	λ, S, q1	0, R, q1	1, R, q2
q2	λ, S, q2	0, R, q1	0, R, q2

Команды движения каретки: L – влево, R – вправо, N – отсутствие сдвига, S – стоп. После выполнения программы в полученной последовательности оказалось 10 символов 1. Определите максимально возможное значение параметра k в исходной последовательности.

(В. Шубинкин) На ленте исполнителя МТ в соседних ячейках записана последовательность символов 2…20…01…1: сначала 120 двоек, затем 333 ноля и 750 единиц. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка находится на неизвестном ненулевом расстоянии слева от последовательности. Программа для исполнителя:

	λ	0	1	2
q0	λ, R, q0	0, R, q0	0, R, q1	0, R, q2
q1	1, S, q0	1, L, q0	1, R, q1	1, R, q2
q2	λ, N, q1	2, L, q0	2, L, q1	2, R, q2

Команды движения каретки: L – влево, R – вправо, S – стоп. Определите количество ячеек, значения которых после выполнения программы не равны исходным.

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

	λ	0	1
q0	λ, L, q1
q1	λ, S, q1	1, S, q1	0, L, q1

Команды движения каретки: L – влево, R – вправо, S – стоп. После выполнения программы на ленте осталось ровно 758 нулей. Определите минимально возможное число нулей в исходной последовательности.