Задание 12. Информатика. ЕГЭ 2026. Крылов. Вариант 8

Исполнитель MT на первом проходе (справа налево в состоянии \(q_1\)) заменит нули единицами, а единицы нулями. На втором проходе (слева направо в состоянии \(q_2\)) он проделаем ту же самую операцию с единицами (которые изначально были нулями) и остановится на первом нуле, заменив его единицей. Получается, что количество нулей \(Z\) в конечной строке будет определяться количеством левых нулей \(L0\) в исходной строке (до самой левой единицы) и количеством единиц \(R1\) после той же самой левой единицы: $$ \lambda \underbrace{00 \ldots 00}_{L0} 1 \underbrace {00 \ldots 00}_{R0} \underbrace{11 \ldots 11}_{R1} \lambda .$$ Общее количество нулей \(Z = L0 + R1 = L0 + 350 - R0 - L0 - 1 = 349 - R0 = 100\) при условии, что \(L0 + R0 = \min.\) Получаем, что \(R0 = 349 - 100 = 249.\) Минимум \(L0 + R0\) достигается при \(L0 = 0.\) Таким образом минимальное количество нулей в исходной строке — \(249.\)

Проверяем программно:

Python

com = {'l': {'q0': 'l,L,q1', 'q1': 'l,R,q2', 'q2': 'l,S,q2'},
       '1': {'q1': '0,L,q1', 'q2': '0,R,q2'},
       '0': {'q1': '1,L,q1', 'q2': '1,S,q2'}}
step = {'L': -1, 'R': 1, 'S': 0}

s = ['l'] + ['1'] + ['0'] * 249 + ['1'] * 100 + ['l']

print('Нулей в исходной строке', s.count('0'))

p = len(s) - 1
state = 'q0'
ch, act, st = com[s[p]][state].split(',')
s[p] = ch
state = st
p += step[act]

while act != 'S':
    ch, act, st = com[s[p]][state].split(',')
    s[p] = ch
    state = st
    p += step[act]

print('Нулей в конечной строке', s.count('0'))

Ответ: \(249\)