Тренажер на задание 12 ЕГЭ по информатике с ответами (алгоритмы МТ, редактор)

Тренажер на задание 12 ЕГЭ по информатике.

Заданий №12 ЕГЭ по информатике из разных источников

ЕГЭ 2026. Статград. 16.12.2025
Выполните задание.

На ленте в соседних ячейках записана последовательность из $999$ символов, которая может включать только пятёрки, семёрки и девятки, расположенные в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$5$	$7$	$9$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$1, \, L, \, q_1$	$0, \, L, \, q_1$

Известно, что после выполнения программы получилась строка, в которой все соседние символы различны. Определите минимально возможное значение суммы цифр в исходной строке.

Решение:

Так как в конечной строке цифры чередуются, значит там присутствуют минимум $\left\lfloor 999 / 2 \right\rfloor = 499$ нулей. Значит в исходной строке должно присутствовать такое же количество девяток. Остальные $999 - 499 = 500$ непустых символов должны быть пятерками, если мы хотим получить минимум суммы цифр исходной строки. Значит, минимально возможное значение суммы в исходной строке будет $$5 \cdot 500 + 9 \cdot 499 = 6991.$$

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

Python


com = {('q0', 'l'): 'l,L,q1', ('q1', 'l'): 'l,S,q1', ('q1', '5'): '1,L,q1',
       ('q1', '7'): '1,L,q1', ('q1', '9'): '0,L,q1', }
step = {'L': -1, 'S': 0}

strip = ['l'] + ['5', '9'] * 499 + ['5', 'l']

state, act, p = 'q0', 'L', len(strip) - 1

while act != 'S':
    strip[p], act, state = com[(state, strip[p])].split(',')
    p += step[act]
#print(strip)
if all(a != b for a, b in zip(strip, strip[1:])):
    print(500 * 5 + 499 * 9)

Ответ: 6991

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

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

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

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_0$	$a_1$	$\ldots$	$a_n$
$q_0$	команда	команда	$\ldots$	команда
$q_1$	команда	команда	$\ldots$	команда
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$
$q_{n-1}$	команда	команда	$\ldots$	команда

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце – возможные состояния головки. На пересечении $i$-й строки и $j$-го столбца находится команда, которую выполняет МТ, когда головка обозревает $j$-й символ, находясь в $i$-м состоянии. Если пара «символ – состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент – записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент – один из четырёх символов «$L$», «$R$», «$N$», «$S$». Символы «$L$» и «$R$» означают сдвиг в левую или правую ячейки соответственно, «$N$» – отсутствие сдвига, «$S$» – завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент – новое состояние головки после выполнения команды.

Например, команда $0, \, L, q_3$ выполняется следующим образом: в текущую ячейку записывается символ «$0$», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_3.$

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов «$Z$», все остальные ячейки ленты заполнены пустым символом «$\lambda$». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «$Z$».

Программа

	$\lambda$	$Z$
$q_0$	$\lambda , \, L, \, q_0$	$X, \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$X, \, L, \, q_1$

заменяет на ленте все символы «$Z$» на «$X$» и останавливает исполнителя в первой ячейке слева от последовательности символов «$X$»

Возможное начальное состояние исполнителя:

$\ldots$	$\lambda$	$\lambda$	$Z$	$Z$	$Z$	$Z$	$\lambda$	$\lambda$	$\ldots$
								$\blacktriangle q_0$

Конечное состояние исполнителя после завершения выполнения программы:

$\ldots$	$\lambda$	$\lambda$	$X$	$X$	$X$	$X$	$\lambda$	$\lambda$	$\ldots$
		$\blacktriangle q_0$

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

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$0 , \, R, \, q_2$	$0, \, R, \, q_1$	$1, \, R, \, q_1$
$q_2$	$0 , \, R, \, q_3$
$q_3$	$\lambda , \, S, \, q_3$

Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.

Решение:

Python


table = {('q0', 'l'): 'l,R,q1', ('q1', 'l'): '0,R,q2', ('q1', '0'): '0,R,q1',
         ('q1', '1'): '1,R,q1', ('q2', 'l'): '0,R,q3', ('q3', 'l'): 'l,S,q3',}
step = {'R': 1, 'L': -1, 'S': 0}
state = 'q0'
act = 'R'
strip = ['l'] + list(bin(2028)[2:]) + ['l']*3
p = 0

while act != 'S':
    strip[p], act, state = table[(state, strip[p])].split(',')
    p += step[act]
print(int(''.join(strip[1:-1]), 2))

Ответ: 8112

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

Программа работы исполнителя МТ задаётся в табличном виде.

	$a_0$	$a_1$	$\ldots$	$a_n$
$q_0$	команда	команда	$\ldots$	команда
$q_1$	команда	команда	$\ldots$	команда
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$
$q_{n-1}$	команда	команда	$\ldots$	команда

Например, команда $0, \, L, q_3$ выполняется следующим образом: в текущую ячейку записывается символ «$0$», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние $q_3.$

Приведём пример выполнения программы, заданной таблично.

Программа

	$\lambda$	$Z$
$q_0$	$\lambda , \, L, \, q_0$	$X, \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$X, \, L, \, q_1$

Возможное начальное состояние исполнителя:

$\ldots$	$\lambda$	$\lambda$	$Z$	$Z$	$Z$	$Z$	$\lambda$	$\lambda$	$\ldots$
								$\blacktriangle q_0$

Конечное состояние исполнителя после завершения выполнения программы:

$\ldots$	$\lambda$	$\lambda$	$X$	$X$	$X$	$X$	$\lambda$	$\lambda$	$\ldots$
		$\blacktriangle q_0$

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

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

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, S, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $343$ нуля. Определите максимально возможное число нулей в исходной последовательности.

Решение:

Если все $1000$ непустых символов в начальной строке будут равны $0,$ то после выполнения программы в конечной строке не останется вообще нулей. Значит, хотя бы один символ $1$ должен присутствовать в строке. Действительно, если входная строка будет иметь вид $$\lambda \underbrace{0 \ldots 0}_{342} 1 \underbrace{0 \ldots 0}_{657} \lambda$$ на выходе получим ровно $343$ нуля. Для проверки напишем программу

Python


#s = ['l'] + ['0'] * 1000 + ['l'] # Для такой строки в конце выпонения программы нулей совсем не останется
s = ['l'] + ['0'] * 342 + ['1'] + ['0'] * 657 + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = len(s) - 1
state='q0'
table = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,L,q1'},
         '1': {'q1': '0,S,q1'}}
step = {'L': 1, 'R': -1, 'S': 0}
s[p], m, state = table[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = table[s[p]][state].split(',')
print(f"Количество нулей в конечной строке: {s.count('0')}")

Ответ: 999

ЕГЭ 2026. Крылов. Вариант 20
На ленте в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте оказалась двоичная запись числа $88.$ Определите десятичное значение наименьшего числа на ленте, которое могло быть записано на ленте до начала выполнения программы.

Решение:

Python


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

for n in range(1, 1000):
    s = ['l'] + list(f'{n:b}') + ['l']

    p = len(s) - 1
    state = 'q0'
    act = 'L'

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

    if int(''.join(s[1:-1]), 2) == 88:
        print(n)
        break

Ответ: 167

ЕГЭ 2026. Крылов. Вариант 19
На ленте в соседних ячейках записано двоичное представление целого положительного числа без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте оказалась двоичная запись числа $240.$ Определите десятичное значение наименьшего числа на ленте, которое могло быть записано на ленте до начала выполнения программы.

Решение:

Python


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

for n in range(1, 1000):
    s = ['l'] + list(f'{n:b}') + ['l']

    p = len(s) - 1
    state = 'q0'
    act = 'L'

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

    if int(''.join(s[1:-1]), 2) == 240:
        print(n)
        break

Ответ: 271

ЕГЭ 2026. Крылов. Вариант 18
На ленте в соседних ячейках записано двоичное представление числа $14$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите десятичное значение числа на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + list(f'{14:b}') + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

print(int(''.join(s[1:-1]), 2))

Ответ: 10

ЕГЭ 2026. Крылов. Вариант 17
На ленте в соседних ячейках записано двоичное представление числа $240$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$

Определите десятичное значение числа на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + list(f'{240:b}') + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

print(int(''.join(s[1:-1]), 2))

Ответ: 15

ЕГЭ 2026. Крылов. Вариант 16
На ленте в соседних ячейках записано двоичное представление числа $511$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите десятичное значение числа на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + list(f'{511:b}') + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

print(int(''.join(s[1:-1]), 2))

Ответ: 341

ЕГЭ 2026. Крылов. Вариант 15
На ленте в соседних ячейках записано двоичное представление числа $1022$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите десятичное значение числа на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + list(f'{1022:b}') + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

print(int(''.join(s[1:-1]), 2))

Ответ: 682

ЕГЭ 2026. Крылов. Вариант 14
На ленте в соседних ячейках записана последовательность из $125$ нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите число нулей на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + ['0'] * 125 + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

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

Ответ: 125

ЕГЭ 2026. Крылов. Вариант 13
На ленте в соседних ячейках записана последовательность из $100$ нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите число нулей на ленте после выполнения программы.

Решение:

Python


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

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

p = len(s) - 1
state = 'q0'
act = 'L'

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

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

Ответ: 100

ЕГЭ 2026. Крылов. Вариант 12
На ленте в соседних ячейках записана последовательность из $200$ единиц. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите число нулей на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + ['1'] * 200 + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

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

Ответ: 100

ЕГЭ 2026. Крылов. Вариант 11
На ленте в соседних ячейках записана последовательность из $103$ единиц. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$1, \, L, \, q_2$	$0, \, L, \, q_3$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, L, \, q_3$	$1, \, L, \, q_2$
$q_3$	$\lambda , \, S, \, q_3$	$1, \, L, \, q_2$	$0, \, L, \, q_3$

Определите число нулей на ленте после выполнения программы.

Решение:

Python


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

s = ['l'] + ['1'] * 103 + ['l']

p = len(s) - 1
state = 'q0'
act = 'L'

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

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

Ответ: 51

ЕГЭ 2026. Крылов. Вариант 10
На ленте в соседних ячейках записана последовательность из $400$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, R, \, q_2$	$0, \, R, \, q_2$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_2$	$1, \, R, \, q_2$	$1, \, R, \, q_2$

После выполнения программы на ленте осталось ровно $100$ нулей. Определите максимально возможное число нулей в исходной последовательности.

Решение:

Исполнитель проходит сначала ленту справа налево (в состоянии $q_1$) заменяя нули единицами, пока не встретит первую единицу. Эту единицу он заменяет на $0,$ переключается в состояние $q_2$ и движется вправо до конца ленты, заменяя все символы на $1.$ Все $400$ символов не могут быть нулями, потому что в конце в строке не останется ни одного нуля. Значит, хотя бы одна единица на ленте присутствует. Действительно, строка $$\lambda \underbrace{00 \ldots 00}_{99} 1 \underbrace{00 \ldots 00}_{300} \lambda$$ решает нашу задачу. Проверим это программно:

Python


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

#s = ['l'] + ['0'] * 400 + ['l']
s = ['l'] + ['0'] * 99 + ['1'] + ['0'] * 300 + ['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'))

Ответ: 399

ЕГЭ 2026. Крылов. Вариант 9
На ленте в соседних ячейках записана последовательность из $255$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, R, \, q_2$	$0, \, R, \, q_2$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_2$	$1, \, R, \, q_2$	$1, \, R, \, q_2$

После выполнения программы на ленте осталось ровно $50$ нулей. Определите максимально возможное число нулей в исходной последовательности.

Решение:

Исполнитель проходит сначала ленту справа налево (в состоянии $q_1$) заменяя нули единицами, пока не встретит первую единицу. Эту единицу он заменяет на $0,$ переключается в состояние $q_2$ и движется вправо до конца ленты, заменяя все символы на $1.$ Все $255$ символов не могут быть нулями, потому что в конце в строке не останется ни одного нуля. Значит, хотя бы одна единица на ленте присутствует. Действительно, строка $$\lambda \underbrace{00 \ldots 00}_{49} 1 \underbrace{00 \ldots 00}_{205} \lambda$$ решает нашу задачу. Проверим это программно:

Python


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

#s = ['l'] + ['0'] * 250 + ['l']
s = ['l'] + ['0'] * 49 + ['1'] + ['0'] * 205 + ['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'))

Ответ: 254

ЕГЭ 2026. Крылов. Вариант 8
На ленте в соседних ячейках записана последовательность из $350$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, R, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, R, \, q_2$	$0, \, S, \, q_2$

После выполнения программы на ленте осталось ровно $100$ нулей. Определите минимально возможное число нулей в исходной последовательности.

Решение аналитически и программно:

Исполнитель 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

ЕГЭ 2026. Крылов. Вариант 7
На ленте в соседних ячейках записана последовательность из $255$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, R, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, R, \, q_2$	$0, \, S, \, q_2$

После выполнения программы на ленте осталось ровно $125$ нулей. Определите минимально возможное число нулей в исходной последовательности.

Решение аналитически и программно:

Исполнитель 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 + 255 - R0 - L0 - 1 = 254 - R0 = 125$ при условии, что $L0 + R0 = \min.$ Получаем, что $R0 = 254 - 125 = 129.$ Минимум $L0 + R0$ достигается при $L0 = 0.$ Таким образом минимальное количество нулей в исходной строке — $129.$

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

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'] * 129 + ['1'] * 125 + ['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'))

Ответ: 129

ЕГЭ 2026. Крылов. Вариант 6
На ленте в соседних ячейках записана последовательность из $350$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $100$ нулей. Определите число нулей в исходной последовательности.

Решение:

Исполнитель заменяет нули на единицы, а единицы на нули. Значит, в исходной последовательности было $100$ единиц и $350-100 = 250$ нулей. Проверяем программно:

Python


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

s = ['l'] + ['1'] * 100 + ['0'] * 250 + ['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'))

Ответ: 250

ЕГЭ 2026. Крылов. Вариант 5
На ленте в соседних ячейках записана последовательность из $255$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $125$ нулей. Определите число нулей в исходной последовательности.

Решение:

Исполнитель заменяет нули на единицы, а единицы на нули. Значит, в исходной последовательности было $125$ единиц и $255-125 = 130$ нулей. Проверяем программно:

Python


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

s = ['l'] + ['1'] * 125 + ['0'] * 130 + ['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'))

Ответ: 130

ЕГЭ 2026. Крылов. Вариант 4
На ленте в соседних ячейках записана последовательность из $333$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, S, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $137$ нулей. Определите минимально возможное число нулей в исходной последовательности.

Решение:

Исполнитель завершает свою работу на первой встретившейся ему единице, превращая её в ноль. Кроме этого появившегося нуля на ленте должно остаться ещё $136$ нуля. Значит, минимальное количество нулей, которое изначально может быть на ленте равно $136.$ Напишем программу для проверки:

Python


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

s = ['l'] + ['1'] * 196 + ['0'] * 136 + ['1'] + ['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'))

Ответ: 136

ЕГЭ 2026. Крылов. Вариант 3
На ленте в соседних ячейках записана последовательность из $520$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, S, \, q_1$	$1, \, L, \, q_1$

Решение:

Исполнитель завершает свою работу на первой встретившейся ему единице, превращая её в ноль. Кроме этого появившегося нуля на ленте должно остаться ещё $124$ нуля. Значит, минимальное количество нулей, которое изначально может быть на ленте равно $124.$ Напишем программу для проверки:

Python


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

s = ['l'] + ['1'] * 395 + ['0'] * 124 + ['1'] + ['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'))

Ответ: 124

ЕГЭ 2026. Крылов. Вариант 2
На ленте в соседних ячейках записана последовательность из $333$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, S, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $120$ нулей. Определите максимально возможное число нулей в исходной последовательности.

Решение:

Если все $333$ символа в исходной строке будут нулями, то после завершения работы исполнителя на ленте не останется ни одного нуля. Поэтому, хотя бы одна единица должна присутствовать на ленте. Действительно, если исходная строка будет вида $$\lambda \underbrace{00 \ldots 0}_{119} 1 \underbrace{00 \ldots 0}_{213} \lambda , $$ то после выполнения программы на ленте останется $120$ нулей. Для проверки напишем программу:

Python


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

#s = ['l'] + ['0'] * 333 + ['l']
s = ['l'] + ['0'] * 119 + ['1'] + ['0'] * 213 + ['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'))

Ответ: 332

ЕГЭ 2026. Крылов. Вариант 1
На ленте в соседних ячейках записана последовательность из $520$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, S, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $125$ нулей. Определите максимально возможное число нулей в исходной последовательности.

Решение:

Если все $520$ символов в исходной строке будут нулями, то после завершения работы исполнителя на ленте не останется ни одного нуля. Поэтому, хотя бы одна единица должна присутствовать на ленте. Действительно, если исходная строка будет вида $$\lambda \underbrace{00 \ldots 0}_{124} 1 \underbrace{00 \ldots 0}_{395} \lambda , $$ то после выполнения программы на ленте останется $125$ нулей. Для проверки напишем программу:

Python


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

# s = ['l'] + ['0'] * 520 + ['l']
s = ['l'] + ['0'] * 124 + ['1'] + ['0'] * (520 - 125) + ['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'))

Ответ: 519

ЕГЭ 2026. Статград. 23.10.2025
На ленте в соседних ячейках записана последовательность из $1000$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$1$	$0$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, S, \, q_1$	$1, \, L, \, q_1$

После выполнения программы на ленте осталось ровно $605$ нуля. Определите минимально возможное число нулей в исходной последовательности.

Решение:

Алгоритм остановится на первой единице, превратив её в ноль. И после этого в строке должно быть ещё $604$ нуля. Значит, минимально возможное число нулей в исходной строке равно $604.$

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

Python


s = ['l'] + ['1'] * 395 + ['0']*604 + ['1'] + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = len(s) - 1
state='q0'
table = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,L,q1'},
         '1': {'q1': '0,S,q1'}}
step = {'L': 1, 'R': -1, 'S': 0}
s[p], m, state = table[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = table[s[p]][state].split(',')
print(f"Количество нулей в конечной строке: {s.count('0')}")

Ответ: 604

Поляков-8304
(Р. Косов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_q$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_1$	$2, \, L, \, q_2$	$1, \, S, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. В результате на ленте оказалась последовательность с суммой цифр, превышающей $1200.$ Определите максимально возможное число единиц в исходной последовательности.

Решение:

Если все ненулевые символы исходной строки единицы, то она не изменится в результате работы программы, а сумма её цифр будет равна $1000.$ Значит, вместо некоторых единиц нужно ставить нули, которые после работы исполнителя превратятся в двойки. Всего нужно поставить больше $200$ нулей в самый конец строки перед завершающей единицей. Минимальное количество двоек — $201,$ значит максимальное количество единиц равно $1000 - 201 = 799.$

Тестируем программно

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '0,L,q1', 'q2': '2,L,q2'},
      '1': {'q1': '1,L,q2', 'q2': '1,S,q2'},
      }
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 798 + '0' * 201 + '1' + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Сумма цифр в конечной последовательности: {sum(int(x) for x in s if x != "l")}')

Ответ: 799

Поляков-8303
(Р. Косов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_q$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_1$	$2, \, L, \, q_2$	$1, \, S, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. В результате на ленте оказалась последовательность с суммой цифр, превышающей $1200.$ Определите минимально возможное число нулей в исходной последовательности.

Решение:

Если непустые символы исходной строки одни единицы, то на выходе получим такую же строку, а сумма цифр будет равна $1000.$ Необходимо в конец строки перед самой крайней правой единицей поместить больше, чем $200$ нулей, которые на выходе дадут двойки, а конечная сумма будет больше $1200.$

Тестируем программно

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '0,L,q1', 'q2': '2,L,q2'},
      '1': {'q1': '1,L,q2', 'q2': '1,S,q2'},
      }
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 798 + '0' * 201 + '1' + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Сумма цифр в конечной последовательности: {sum(int(x) for x in s if x != "l")}')

Ответ: 201

Поляков-8302
(Р. Косов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1500$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_q$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_1$	$2, \, L, \, q_2$	$1, \, S, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Определите максимально возможную сумму цифр, которую можно получить на ленте после выполнения алгоритма.

Решение:

Если все непустые символы строки нули, то сумма цифр конечной строки будет нулевая. Поставим самым крайним правым символом единицу. Тогда на выходе получим строку, сумма цифр которой $2999.$ Это — максимальная сумма, которую можно получить в результате работы программы.

Программный тест

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '0,L,q1', 'q2': '2,L,q2'},
      '1': {'q1': '1,L,q2', 'q2': '2,S,q2'},
      }
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '0' * 1499 +  '1' + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Сумма цифр в конечной последовательности: {sum(int(x) for x in s if x != "l")}')

Ответ: 2999

Поляков-8301
(Р. Косов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_q$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_1$	$2, \, L, \, q_2$	$1, \, S, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. В результате на ленте оказалась последовательность с суммой цифр, превышающей $1500.$ Определите максимально возможное число нулей в исходной последовательности.

Решение:

Если все непустые символы исходной строки нули, то в конечной строке они же останутся. Значит, в строке присутствует хотя бы одна единица. Действительно, строка $$\lambda \underbrace{0 \ldots 0}_{750} 1 \underbrace{0 \ldots 0}_{249} \lambda$$ даст на выходе строку, сумма цифр которой больше $1500$ (её сумма будет $1501)$.

Программный тест

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '0,L,q1', 'q2': '2,L,q2'},
      '1': {'q1': '1,L,q2', 'q2': '1,S,q2'},
      }
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
#s = list('l' + '0' * 1000  + 'l') # для такой строки в конце будут только нули
s = list('l' + '0' * 750 +  '1' + '0' * 249  + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Сумма цифр в конечной последовательности: {sum(int(x) for x in s if x != "l")}')

Ответ: 999

Поляков-8300
(Р. Косов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_q$	$0, \, L, \, q_1$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_1$	$2, \, L, \, q_2$	$1, \, S, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. В результате на ленте оказалась последовательность с суммой цифр, превышающей $1500.$ Определите минимально возможное число единиц в исходной последовательности.

Решение:

Пусть в исходной последовательности нет совсем единиц. Тогда конечная строка будет содержать среди непустых символов только нули. Значит, хотя бы одна единица присутствует в строке. В частности строка $$\lambda \underbrace{0 \ldots 0}_{750} 1 \underbrace{0 \ldots 0}_{249} \lambda$$ даст на выходе строку, сумма цифр которой больше $1500$ (её сумма будет $1501)$.

Тестируем программно

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '0,L,q1', 'q2': '2,L,q2'},
      '1': {'q1': '1,L,q2', 'q2': '1,S,q2'},
      }
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
#s = list('l' + '0' * 1000  + 'l') # для такой строки в конце будут только нули
s = list('l' + '0' * 750 +  '1' + '0' * 249  + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Сумма цифр в конечной последовательности: {sum(int(x) for x in s if x != "l")}')

Ответ: 1

Поляков-8299
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая $155$ нулей, $237$ единиц, $128$ двоек и $480$ троек, расположенных в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$	$2$	$3$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, L, \, q_2$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$
$q_2$	$\lambda , \, R, \, q_1$		$2, \, L, \, q_2$	$1, \, L, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Определите количество цифр $2$ в последовательности, полученной после выполнения программы.

Решение:

Python

mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,L,q2', 'q2': 'l,S,q2'},
      '0': {'q1': '1,R,q1'},
      '1': {'q1': '2,R,q1', 'q2': '2,L,q2'},
      '2': {'q1': '1,R,q1', 'q2': '1,L,q2'},
      '3': {'q1': '2,R,q1'}}
step = {'R': 1, 'L': -1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '0' * 155 +  '1' * 237 + '2' * 128 + '3' * 480 +  'l')
p = 0
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество двоек в конечной последовательности: {s.count("2")}')

Ответ: 283

Поляков-8298
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, L, \, q_1$	$2, \, L, \, q_1$	$0, \, L, \, q_1$	$1, \, L, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. После выполнения программы получилась строка с количеством символов $1$ вдвое больше символов $2,$ при этом сумма значений в ней равна $448.$ Сколько единиц было в исходной строке?

Решение:

Если количество двоек в конечной строке равно $d,$ то количество единиц тогда будет $2d.$ Значит $2 \cdot d + 1 \cdot 2d = 448,$ отсюда $d = 112,$ $2d = 224.$ Двойки в конечной строке получаются из нулей в исходной, т.е в исходной строке нулей было $112.$ Единицы в конечной строке появляются их двоек исходной, т.е. в исходной строке двоек было $224.$ Значит, единиц в исходной строке было $1000 - 112 - 224 = 664.$

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

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '2,L,q1'},
      '1': {'q1': '0,L,q1'},
      '2': {'q1': '1,L,q1'}}
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '2' * 224 +  '0' * 112 + '1' * 664 + 'l')
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество единиц в конечной последовательности: {s.count("1")}')
print(f'Количество двоек в конечной последовательности: {s.count("2")}')

Ответ: 664

Поляков-8297
(Д. Муфаззалов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_0$	$1, \, S, \, q_1$	$0, \, L, \, q_1$
$q_1$	$1 , \, S, \, q_1$	$1, \, S, \, q_0$	$0 , \, L, \, q_1$

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

Решение:

Если все $1000$ непустых символов в строке единицы, то после выполнения программы останется только одна единица (мало!). Значит, хотя бы один ноль присутствует в строке. Действительно, строка $$\lambda \underbrace{1 \ldots 1}_{342} 0 \underbrace{1 \ldots 1}_{657} \lambda$$ даст на выходе $343$ единицы.

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

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q0': '1,S,q1', 'q1': '1,S,q0'},
      '1': {'q0': '0,L,q1', 'q1': '0,L,q1'}}
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 342 +  '0' + '1' * 657 + 'l')
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество единиц в конечной последовательности: {s.count("1")}')

Ответ: 999

Поляков-8296
(Д. Муфаззалов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_0$	$1, \, S, \, q_1$	$0, \, L, \, q_1$
$q_1$	$1 , \, S, \, q_1$	$1, \, S, \, q_0$	$0 , \, L, \, q_1$

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

Решение:

Исполнитель завершит работу на первом встретившемся ему нуле, заменив его на единицу. В строке должно остаться при этом ещё $343$ нуля. Значит, максимальное количество нулей, которое может быть в исходной строке равно $344.$

Тестируем

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q0': '1,S,q1', 'q1': '1,S,q0'},
      '1': {'q0': '0,L,q1', 'q1': '0,L,q1'}}
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 656 +  '0' * 344 + 'l')
print(f'Количество нулей в исходной последовательности: {s.count("0")}')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 344

Поляков-8295
(Д. Муфаззалов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $5000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Если в строке все $5000$ символов нули, то после исполнения алгоритма в конечной строке нулей не останется совсем. Значит, как минимум одна единица всё же присутствует. Действительно, строка $$\lambda \underbrace{0 \ldots 0}_{242} 1 \underbrace{0 \ldots 0}_{4757} \lambda$$ даст на выходе $243$ нуля. В этой строке находятся $4999$ нулей. С другой стороны, в исходной строке должно находится минимум $242$ нуля. Тогда на первой же единице исполнитель закончит свою работу, добавив в строку ещё один нуль. Вот пример строки с минимальным количество нулей. $$\lambda \underbrace{0 \ldots 0}_{242} \underbrace{1 \ldots 1}_{4758} \lambda$$ Т.о. $x \in [242; \, 4999].$ Всего различных значений $x$ найти нетрудно: $4999 - 242 + 1 = 4758.$

Тест

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,L,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
#s = list('l' + '0' * 242 + '1' + '0' * 4757 + 'l') # Максимальное количество нулей в исходной последовательности
s = list('l' + '0' * 242 + '1' * 4758 + 'l') # Минимальное количество нулей в исходной последовательности
print(f'Количество нулей в исходной последовательности: {s.count("0")}')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 4758

Поляков-8294
(Д. Муфаззалов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $100000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Исполнитель на первой же попавшейся ему единице закончит свою работу, заменив её на ноль. Кроме того, в строке должно остаться ещё $342$ нуля. Значит, оставшиеся $100~000 - 343 = 99657$ символов, которые стояли в конце строки после единицы, должны быть также нулями и они заменятся на $1.$ Всего, максимальное количество символов, которые могут быть заменены в исходной строке, равно $99658.$

Тест

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,L,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
orig = 'l' + '0' * 342 + '1' + '0' * 99657 + 'l'
s = list(orig)
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')

print(f'Количество заменённых символов: {sum(x != y for x, y in zip(s, orig))}')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 99658

Поляков-8293
(Д. Муфаззалов) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Исполнитель завершает работу на первой встретившейся ему единице, меняя её на ноль. Кроме того, в последовательности еще $342$ позиции должны быть заняты нулями, чтобы удовлетворить условию задачи. Значит, минимальное число нулей в стартовой строке равно $342.$

Тестируем

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,L,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': -1, 'L': 1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 657 + '0' * 342 + '1' + 'l')
print(f'Количество нулей в исходной последовательности: {s.count("0")}')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 342

Поляков-8292
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $800$ единиц и $900$ нулей, расположенных в произвольном порядке, и одной двойки в конце. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$	$1, \, R, \, q_1$	$0, \, R, \, q_1$	$1, \, S, \, q_0$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_0$	$0, \, R, \, q_0$	$0, \, S, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Определите количество единиц в строке, полученной в результате работы программы.

Решение:

Python


from random import shuffle

mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '0': {'q0': '1,R,q1', 'q1': '1,R,q0'},
      '1': {'q0': '0,R,q1', 'q1': '0,R,q0'},
      '2': {'q0': '1,S,q0', 'q1': '0,S,q1'}}
step = {'R': 1, 'L': -1, 'S': 0, 'N': 0}
state = 'q0'
tmp = list('1' * 800 + '0' * 900)
shuffle(tmp)
s = ['l'] + tmp + ['2', 'l']
p = 0
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(s.count("1"))

Ответ: 900

Поляков-8291
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $750$ единиц и $650$ нулей, расположенных в произвольном порядке, и одной двойки в конце. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_0$	$1, \, R, \, q_1$	$0, \, R, \, q_1$	$1, \, S, \, q_0$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_0$	$0, \, R, \, q_0$	$0, \, S, \, q_1$

Решение:

Python


mt = {'l': {'q0': 'l,R,q0', 'q1': 'l,S,q1'},
      '0': {'q0': '1,R,q1', 'q1': '1,R,q0'},
      '1': {'q0': '0,R,q1', 'q1': '0,R,q0'},
      '2': {'q0': '1,S,q0', 'q1': '0,S,q1'}}
step = {'R': 1, 'L': -1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 750 + '0' * 650 + '2' + 'l')
p = 0
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(s.count("1"))

Ответ: 651

Поляков-8290
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ единиц и одного нуля в конце. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_0$	$1, \, S, \, q_0$	$0, \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_0$	$0, \, N, \, q_1$

Решение:

Python


mt = {'l': {'q0': 'l,R,q0', 'q1': 'l,S,q1'},
      '0': {'q0': '1,S,q0', 'q1': '1,R,q0'},
      '1': {'q0': '0,R,q1', 'q1': '0,N,q1'}}
step = {'R': 1, 'L': -1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '1' * 1000 + '0' + 'l')
p = 0
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(s.count("1"))

Ответ: 501

Поляков-8289
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $800$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$0, \, L, \, q_1$	$1, \, S, \, q_1$

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

Решение:

Исполнитель заканчивает выполнение алгоритма на первой попавшейся единице. При этом он вообще не меняет значение символов в строке. Значит, максимальное, оно же единственно возможное, количество нулей в исходной последовательности $800 - 420 = 380.$

Тестируем программно

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '0,L,q1'},
      '1': {'q1': '1,S,q1'}}
step = {'L': 1, 'S': 0}
state = 'q0'
s = list('l' + '0' * 380 + '1' * 420 + 'l')
p = len(s) - 1
print(f'Количество нулей в исходной последовательности: {s.count("0")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество единиц в конечной последовательности: {s.count("1")}')

Ответ: 380

Поляков-8288
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $600$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, S, \, q_1$	$0 , \, R, \, q_1$

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

Решение:

Определим максимально возможное количество единиц в исходной строке. Так как исполнитель завершит работу на первом попавшемся ему нуле, превратив его в единицу, то максимально возможное количество нулей в исходной строке будет $251.$ Значит, минимально возможное количество единиц в исходной строке $600 - 251 = 349.$

Тестируем программно

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,S,q1'},
      '1': {'q1': '0,R,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' + '0' * 251 + '1' * 349 + 'l')
p = 0
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 349

Поляков-8287
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $500$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Так как программа остановится на первой встретившейся ей единицы, превратив её в ноль, то максимально возможное количество единиц в исходной строке равно $151.$

Тестируем в программе

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,R,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' + '1' * 151 + '0' * 349 + 'l')
p = 0
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество единиц в конечной последовательности: {s.count("1")}')

Ответ: 151

Поляков-8286
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $500$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Если в исходной последовательности все непустые символы нули, то в конечной строке будет $500$ единиц (много!). Значит, хотя бы одна единица присутствует в начальной строке. Действительно, строка $$\lambda \underbrace{0 \ldots 0}_{300} 1 \underbrace{0 \ldots 0}_{699} \lambda$$ на выходе будет содержать $300$ единиц.

Программный тест

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,R,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' + '0' * 300 + '1' + '0' * 199 + 'l')
p = 0
print(f'Количество нулей в исходной последовательности: {s.count("0")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество единиц в конечной последовательности: {s.count("1")}')

Ответ: 499

Поляков-8285
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Исполнитель завершит свою работу на первой встретившейся единице, превратив её в ноль. Значит в строке должны присутствовать еще $199$ нолей. Значит, максимальное количество единиц в строке $1000 - 199 = 801.$

Программный тест

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,R,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' + '1' + '0' * 199 + '1' * 800 + 'l')
p = 0
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 801

Поляков-8284
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Если в исходной последовательности все $1000$ элементов нули, то после исполнения алгоритма их не останется в конечной последовательности ни одного. Значит, в последовательности присутствует хотя бы одна единица. Действительно строка $$\lambda \underbrace{0 \ldots 0}_{900} 1 \underbrace{0 \ldots 0}_{99} \lambda$$ после завершения работы алгоритма будет содержать $100$ нулей.

Программное тестирование

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,R,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' +  '0' * 900 + '1' + '0' * 99 + 'l')
p = 0
print(f'Количество нулей в исходной последовательности: {s.count("0")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 999

Поляков-8283
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Понятно, что если вначале было максимальное количество единиц, то в процессе исполнения алгоритма их количество могло только уменьшаться. С другой стороны, из таблицы видно, что на первой же единице алгоритм свою работу завершит, превратив её в ноль. Значит в исходной последовательности было максимум $14$ единиц.

Тест

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,L,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'L': 1, 'S': 0}
state = 'q0'
s = list('l' +  '0' * 986 + '1' * 14 + 'l')
p = len(s) - 1
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество единиц в конечной последовательности: {s.count("1")}')

Ответ: 14

Поляков-8282
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Определим минимально возможное число нулей в исходной строке. Исполнитель остановится на первой попавшейся единице, заменив её на ноль. Значит, чтобы в строке осталось $284$ ноля, необходимо, чтобы в ней присутствовало ещё $283$ ноля. Значит, максимальное количество единиц в исходной строке равно $1000 - 283 = 717.$

Тест в программе

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,L,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'L': 1, 'S': 0}
state = 'q0'
s = list('l' + '1' * 716 + '0' * 283 + '1' + 'l')
p = len(s) - 1
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 717

Поляков-8281
(К. Багдасарян) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0 , \, S, \, q_1$

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

Решение:

Если в последовательности нет совсем единиц, то в конечной последовательности не будет ни одного нуля. Значит, хотя бы одна единица присутствует в последовательности. Рассмотрим такую строку: $$\lambda \underbrace{00 \ldots 0}_{99} 1 \underbrace{00 \ldots 0}_{900} \lambda$$ Исполнитель закончит работу на символе $1,$ заменив его предварительно на $0.$ Все нули, стоящие справа от этой единицы заменятся символами $1.$

Тест

Python


mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
      '0': {'q1': '1,L,q1'},
      '1': {'q1': '0,S,q1'}}
step = {'L': 1, 'S': 0}
state = 'q0'
s = list('l' + '0' * 99 + '1' + '0' * 900 + 'l')
p = len(s) - 1
print(f'Количество единиц в исходной последовательности: {s.count("1")}')
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(f'Количество нулей в конечной последовательности: {s.count("0")}')

Ответ: 1

Поляков-8280
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, состоящей из $764$ двоек, $122$ троек и $114$ символов $X$, расположенных в указанном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$2$	$3$	$X$
$q_0$	$\lambda , \, R, \, q_0$
$q_1$	$\lambda , \, S, \, q_1$	$3 , \, R, \, q_1$	$X , \, R, \, q_1$	$2, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Какую десятичную цифру необходимо указать вместо символа $X,$ чтобы сумма цифр последовательности после выполнения программы равнялась $3496?$

Решение:

В конечной последовательности будет $114$ двоек, $764$ тройки и $122$ символа $X.$ Получаем, что $$2 \cdot 114 + 3 \cdot 764 + 122 X = 3496 \, \Rightarrow \, X = \frac{3496 - 2 \cdot 114 - 3 \cdot 764}{122} = 8$$

Программно

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
      '2': {'q1': '3,R,q1'},
      '3': {'q1': 'X,R,q1'},
      'X': {'q1': '2,R,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' + '2' * 764 + '3' * 122 + 'X' * 114 + 'l')
p = 0
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
nums = ''.join(c for c in s if c != 'l')
for n in range(10):
    if sum(int(z) for z in nums.replace('X', str(n))) == 3496:
        print(n)
        break

Ответ: 8

Поляков-8279
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $593$ символов, состоящей из двоек, троек и семёрок, расположенных в произвольном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$2$	$3$	$7$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$7 , \, L, \, q_2$	$7 , \, L, \, q_2$	$7, \, L, \, q_2$
$q_2$	$\lambda , \, S, \, q_2$	$3 , \, L, \, q_3$	$3 , \, L, \, q_3$	$3, \, L, \, q_3$
$q_3$	$\lambda , \, S, \, q_3$	$2 , \, L, \, q_1$	$2, \, L, \, q_1$	$2, \, L, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Определите количество цифр $7$ в последовательности, полученной после выполнения программы.

Решение:

На первом шаге исполнитель разместит в ячейке число $7$ вне зависимости от того, какая там цифра до этого была там записана, на втором шаге будет записана в следующую ячейку цифра $3,$ на третьем — цифра $2$ и т.д. Т.е., количество семёрок, которое появится в конечной строке, будет равно $\left\lceil \cfrac{593}{3} \right\rceil = 198.$

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

Python


from random import choice

mt = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2', 'q3': 'l,S,q3'},
      '2': {'q1': '7,L,q2', 'q2': '3,L,q3', 'q3': '2,L,q1'},
      '3': {'q1': '7,L,q2', 'q2': '3,L,q3', 'q3': '2,L,q1'},
      '7': {'q1': '7,L,q2', 'q2': '3,L,q3', 'q3': '2,L,q1'}}
step = {'L': 1, 'S': 0}
state = 'q0'
nums = '237237237'
s = ['l']
for _ in range(593):
    s.append(choice(nums))
s.append('l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(s.count("7"))

Ответ: 198

Поляков-8278
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, состоящей из $106$ нулей, $334$ единиц и $560$ двоек, расположенных в указанном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$		$2 , \, L, \, q_1$	$0 , \, R, \, q_2$	$1, \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_2$		$0, \, R, \, q_2$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Определите количество нулей в последовательности, полученной после выполнения программы.

Решение:

Python


mt = {'l': {'q0': 'l,L,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '2,L,q1'},
      '1': {'q1': '0,R,q2', 'q2': '0,R,q2'},
      '2': {'q1': '1,L,q1'}}
step = {'L': 1, 'R': -1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '0' * 106 + '1' * 334 + '2' * 560 + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(s.count('0'))

Ответ: 667

Поляков-8277
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, состоящей из $575$ нулей, $303$ единиц и $122$ двоек, расположенных в указанном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке справа от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$			$2 , \, N, \, q_2$	$0 , \, L, \, q_1$
$q_2$	$\lambda , \, S, \, q_2$	$1 , \, L, \, q_2$	$1, \, L, \, q_1$	$2, \, L, \, q_2$

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

Решение:

Python


mt = {'l': {'q0': 'l,L,q1', 'q2': 'l,S,q2'},
      '0': {'q2': '1,L,q2'},
      '1': {'q1': '2,N,q2', 'q2': '1,L,q1'},
      '2': {'q1': '0,L,q1', 'q2': '2,L,q2'}}
step = {'L': 1, 'R': -1, 'S': 0, 'N': 0}
state = 'q0'
s = list('l' + '0' * 575 + '1' * 303 + '2' * 122 + 'l')
p = len(s) - 1
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(sum(int(x) for x in s if x != 'l'))

Ответ: 1030

Поляков-8276
(И. Карпачёв) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, состоящей из $232$ двоек, $115$ нулей и $562$ единиц, расположенных в указанном порядке. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$		$2 , \, R, \, q_1$	$0 , \, S, \, q_1$	$1 , \, R, \, q_1$

Решение:

Python


mt = {'l': {'q0': 'l,R,q1'},
      '0': {'q1': '2,R,q1'},
      '1': {'q1': '0,S,q1'},
      '2': {'q1': '1,R,q1'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('l' + '2' * 323 + '0' * 115 + '1' * 562 + 'l')
p = 0
s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(sum(int(x) for x in s if x != 'l'))

Ответ: 1114

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

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_0$	$0 , \, R, \, q_0$	$0 , \, R, \, q_1$	$0 , \, R, \, q_2$
$q_1$	$1 , \, S, \, q_0$	$1 , \, L, \, q_0$	$1 , \, R, \, q_1$	$1 , \, R, \, q_2$
$q_2$	$\lambda , \, N, \, q_1$	$2 , \, L, \, q_0$	$2 , \, L, \, q_1$	$2 , \, R, \, q_2$

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

Решение:

Так как исходная строка заранее известна, то решить задачу можно программно, просто исполнив алгоритм:

Python


mt = {'l': {'q0': 'l,R,q0', 'q1': '1,S,q0', 'q2': 'l,N,q1'},
      '0': {'q0': '0,R,q0', 'q1': '1,L,q0', 'q2': '2,L,q0'},
      '1': {'q0': '0,R,q1', 'q1': '1,R,q1', 'q2': '2,L,q1'},
      '2': {'q0': '0,R,q2', 'q1': '1,R,q2', 'q2': '2,R,q2'}}
step = {'L': -1, 'R': 1, 'S': 0, 'N': 0}
state = 'q0'

orig = 'l' * 10 + '2' * 120 + '0' * 333 + '1' * 750 + 'l' * 10
s = list(orig)
p = 0

s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(sum(x != y for x, y in zip(s, orig)))

Ответ: 5

Поляков-8274
(В. Шубинкин) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающих только нули и единицы. Известно, что в этой последовательности $985$ единиц. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_0$	$1 , \, L, \, q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, R, \, q_2$	$1, \, L, \, q_0$	$\lambda, \, L, \, q_1$
$q_2$	$1 , \, S, \, q_0$	$1, \, S, \, q_0$	$1, \, S, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. Все полученные после выполнения программы непрерывные последовательности из нолей и единиц рассматриваются как двоичные числа. Определите, какое наибольшее число могло получиться. В ответе запишите это число в десятичной системе счисления.

Решение:

Исполнитель может закончить работу только в состоянии $q_2.$ А попасть в него он может только находясь в состоянии $q_1$ при считывании пустого символа. Это возможно только после прохождения справа налево всех непустых символов. Кроме того самый левый непустой символ не может быть нулём, иначе программа уйдёт в бесконечный цикл. Наконец, чтобы получить максимальное число, все $15$ нулей должны идти подряд. В итоге получим строку из $16$ подряд идущих единиц, а $1111111111111111_2 = 65535_{10}.$

Тест на программе

Python


mt = {'l': {'q0': 'l,L,q0', 'q1': 'l,R,q2', 'q2': '1,S,q0'},
      '0': {'q0': '1,L,q0', 'q1': '1,L,q0', 'q2': '1,S,q0'},
      '1': {'q0': 'l,L,q1', 'q1': 'l,L,q1', 'q2': '1,S,q1'}}
step = {'L': 1, 'R': -1, 'S': 0, 'N': 0}
state = 'q0'
s = ['l'] * 10 + ['1'] + ['0'] * 15 + ['1'] * 984 + ['l'] * 10
p = len(s) - 1

s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p -= step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(int(''.join(x for x in s if x != 'l'), 2))

Ответ: 65535

Поляков-8273
(В. Шубинкин) На ленте исполнителя МТ в соседних ячейках записана последовательность из $500$ пар символов $0$ и $1:$ $0101 \ldots 01.$ Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в самой левой ячейке последовательности (в ячейке с самым левым символом $0).$

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

	$\lambda$	$0$	$1$
$q_0$	$1 , \, R, \, q_1$	$0 , \, R, \, q_1$	$0 , \, R, \, q_1$
$q_1$	$2 , \, R, \, q_2$	$1, \, R, \, q_2$	$1, \, R, \, q_2$
$q_2$	$3 , \, S, \, q_0$	$3, \, R, \, q_0$	$3, \, R, \, q_0$

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

Решение:

Так как начальная строка известна, задание можно решить программно

Python


mt = {'l': {'q0': '1,R,q1', 'q1': '2,R,q2', 'q2': '3,S,q0'},
      '0': {'q0': '0,R,q1', 'q1': '1,R,q2', 'q2': '3,R,q0'},
      '1': {'q0': '0,R,q1', 'q1': '1,R,q2', 'q2': '3,R,q0'}}
step = {'R': 1, 'S': 0}
state = 'q0'
s = list('01' * 500) + ['l'] * 10
p = 0

s[p], m, state = mt[s[p]][state].split(',')
while m != 'S':
    p += step[m]
    s[p], m, state = mt[s[p]][state].split(',')
print(sum(int(x) for x in s if x != 'l'))

Ответ: 1337

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_0$	$0 , \, N, \, q_1$	$1 , \, N, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, S, \, q_1$	$\lambda, \, L, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $N$ — нет перемещения, $S$ – стоп. После выполнения программы на ленте осталось $42$ единицы и $131$ ноль. Определите максимально возможное число единиц в исходной последовательности.

Решение:

Сначала головка будет двигаться справа налево по пустым символам, пока не дойдёт до $0$ или $1$ и переключит состояние в $q_1.$ Из второй строки таблицы видно, что исполнитель закончит работу, если встретит символ $0$ или пустой символ. В случае $0$ он поменяет это символ на $1.$ Так как на ленте ещё останутся ненулевые символы, значит исполнитель закончит работу именно на нулевом символе. Ясно, что слева от него останутся $131$ нуль и $41$ единица, а он сам тоже превратится в единицу. Значит, до этого нулевого символа находились только единицы, которые превратились в пустые символы. Всего их было $1000 - 131 - 42 = 827.$ А в начальной строке общее количество единиц поэтому было $827 + 41 = 868.$

Тест в программе

Python


mt = {'l': {'q0': 'l,L,q0', 'q1': 'l,S,q1'},
      '0': {'q0': '0,N,q1', 'q1': '1,S,q1'},
      '1': {'q0': '1,N,q1', 'q1': 'l,L,q1'}}
step = {'L': 1, 'S': 0, 'N': 0}
state = 'q0'

s = ['l']* 5 + ['1'] * 41 + ['0'] * 132 + ['1'] * 827 + ['l'] 
print(f'В начальной строке единиц - {s.count("1")}')
p = len(s) - 1

act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
    p -= step[act[1]]
    act = mt[s[p]][state].split(',')
    s[p], state = act[0], act[2]

print(f'В конечной строке нулей - {s.count("0")}, единиц - {s.count("1")}')

Ответ: 868

Поляков-8271
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_2$	$0, \, R, \, q_2$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, S, \, q_2$	$1, \, R, \, q_1$

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

Решение:

Найдем максимальное количество нулей, которое может быть размещено в строке. Пусть на нулевой позиции стоит пустой символ. При переходе к первой позиции исполнитель переходит в состояние $q_1.$ Замечаем, что если в строке встретятся два подряд идущих нуля, то исполнитель закончит работу либо на первом нуле (если уже находится в состоянии $q_1),$ либо на втором нуле. Чтобы добавить как можно больше нулей, мы должны их размешать в парах $01,$ причём каждая такая пара перейдет в пару из двух единиц $11.$ Ясно, что таких пар не может быть больше, чем $250.$ Точнее, их будет ровно $249.$ Они дадут $498$ единиц. Далее размещаем на $499$ и $500$ позиции нули. Исполнитель, на $499$ шаге, находясь в состоянии $q_1$ заменит $0$ на $1$ и остановится на $500$-м шаге. Оставшиеся $500$ позиций мы должны заполнить нулями, за исключением одной позиции. Номер позиции, где может стоять $1$ любой из диапазона $[501:1000].$ Т.о., максимум нулей, которое мы можем разместить в исходной строке, равно $750.$ Значит, минимум единиц, которое может встретиться в строке, будет $1000 - 750 = 250.$

Программный тест:

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '1,R,q2', 'q2': '0,S,q2'},
      '1': {'q1': '0,R,q2', 'q2': '1,R,q1'}}
s = ['l']  + list('01' * 249) + ['0'] * 501 + ['1'] + ['l']
p = 0
step = {'L': -1, 'R': 1, 'S': 0}
print(f'Количество единиц в начальной строке: {s.count("1")}')
state = 'q0'
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
    p += step[act[1]]
    act = mt[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f'Количество нулей в конечной строке: {s.count("0")}')

Ответ: 250

Поляков-8270
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_2$	$0, \, R, \, q_2$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, S, \, q_2$	$1, \, R, \, q_1$

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

Решение:

Пусть строка после пустого символа состоит из $1000$ единиц. Каждую единицу, стоящую на нечётной позиции, исполнитель заменит на $0.$ В конечной строке будет тогда $500$ нулей и $500$ единиц. То что нам нужно.

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

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '1,R,q2', 'q2': '0,S,q2'},
      '1': {'q1': '0,R,q2', 'q2': '1,R,q1'}}
s = ['l']  + ['1'] * 1000 + ['l']
p = 0
step = {'L': -1, 'R': 1, 'S': 0}
print(f'Количество единиц в начальной строке: {s.count("1")}')
state = 'q0'
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
    p += step[act[1]]
    act = mt[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f'Количество нулей в конечной строке: {s.count("0")}')

Ответ: 1000

Поляков-8269
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_2$	$0, \, R, \, q_2$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, S, \, q_2$	$1, \, R, \, q_1$

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

Решение:

Переформулируем вопрос задачи: определите максимально возможное количество нулей в исходной последовательности. Пусть на нулевой позиции находится пустой символ $\lambda ,$ а на последующих $1000$ позициях находятся нули и единицы. Во-первых заметим, что если в последовательности встретились два подряд идущих нуля, то исполнитель закончит свою работу обязательно либо на первом из этих нулей (если он уже находится в состоянии $q_2,)$ либо на втором нуле. Так как мы хотим разместить как можно больше нулей в исходной строке, то часть из них должна превратиться в единицы и после работы алгоритма должно остаться $200$ нулей. Исполнитель при переходе с нулевой (пустой) позиции в первую получает состояние $q_1.$ Значит на первой позиции не может находится единица (иначе количество нулей увеличится, а нам нужно наоборот уменьшение нулей, раз мы хотим разместить как можно больше этих самых нулей). Значит, начало исходной строки должно представлять собой последовательность пар чисел $01.$ После работы алгоритма такие пары переходят в две единицы: $11.$ Мы можем разместить не больше $400$ таких пар, раз нам нужно получить в конце $200$ нулей. На самом деле таких пар будет ровно $399.$ Они дадут в итоге $798$ единиц. В запасе осталось $202$ позиции. Помещаем на $799$ и $800$ позиции нули. Исполнитель на $799$ шаге заменит $0$ на $1$ и перейдёт в состояние $q_2.$ На $800$ шаге он остановится. Так как должно остаться ровно $200$ нулей, то на одной позиции из диапазона $[801:1000]$ размещаем одну единицу. Т.о., нам удалось разместить максимум $600$ нулей так, чтобы в конечной строчке осталось $200$ нулей. Значит, минимум единиц в строке будет $1000 - 600 = 400.$

Тест в программе

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '1,R,q2', 'q2': '0,S,q2'},
      '1': {'q1': '0,R,q2', 'q2': '1,R,q1'}}
s = ['l']  + list('01' * 399) + ['0'] * 201 + ['1'] + ['l']
p = 0
step = {'L': -1, 'R': 1, 'S': 0}
print(f'Количество единиц в начальной строке: {s.count("1")}')
state = 'q0'
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
    p += step[act[1]]
    act = mt[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f'Количество нулей в конечной строке: {s.count("0")}')

Ответ: 400

Поляков-8268
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_2$	$0, \, R, \, q_2$
$q_2$	$\lambda , \, S, \, q_2$	$0, \, S, \, q_2$	$1, \, R, \, q_1$

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

Решение:

Пусть пустой символ $\lambda$ стоит на нулевой позиции, а далее на $1000$ следующих позициях стоят нули и единицы. Исполнитель завершает работу если он находится в состоянии $q_1$ или $q_2$ и смотрит на пустой символ, либо в состоянии $q_2$ и на ленте в данный момент находится символ $0.$ Если строка состоит из всех единиц, то в конце получится $500$ нулей: каждая единица, находящаяся на нечётной позиции превратится в ноль. Рассмотрим следующую строку: $$\lambda \underbrace{11\ldots 1}_{397} 0 \underbrace{11\ldots 1}_{602}$$ Из первых $397$ единиц получится $199$ нулей (столько единиц стоит на нечётных позициях). На $398$-м шаге исполнитель остановится, так как встретит символ $0$ и будет находиться в состоянии $q_2.$ Всего получим $200$ нулей. Таким образом, максимальное количество единиц в такой последовательности — $999.$

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

Python


mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '1,R,q2', 'q2': '0,S,q2'},
      '1': {'q1': '0,R,q2', 'q2': '1,R,q1'}}
#s = ['l'] + ['1'] * 1000 + ['l'] Если в строке 1000 единиц, то в конце получим 500 нулей
s = ['l']  + ['1'] * 397 + ['0'] + ['1'] * 602 + ['l']
p = 0
step = {'L': -1, 'R': 1, 'S': 0}
print(f'Количество единиц в начальной строке: {s.count("1")}')
state = 'q0'
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
    p += step[act[1]]
    act = mt[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f'Количество нулей в конечной строке: {s.count("0")}')

Ответ: 999

Поляков-8267
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $S$ – стоп. Известно, что каждый из символов $0,$ $1$ и $2$ есть в исходной строке. Суммы значений в начальной и конечной строках кратны $5,$ при этом больше $0.$ Определите максимальную возможную разницу между суммой цифр исходной строки и суммой цифр конечной строки.

Решение:

Пусть в исходной строке было $n$ нулей, $e$ единиц и $d$ двоек. Из условия задачи имеем: $1 \leqslant n \leqslant 998,$ $1 \leqslant e \leqslant 998,$ $1 \leqslant d \leqslant 998.$ Кроме того, $n + e + d = 1000.$ Сумма значений начальной строки $$S_0 = e + 2d = 1000 - n + d$$ Сумма значений конечной строки $$S_1 = n + 2e = 2000 - n - 2d$$ Эти суммы должны быть кратны $5$ и быть ненулевыми. Максимальную разницу $S_0 - S_1$ найдём перебором

Python


ms = -float('inf')
for n in range(998, 1, -1):
    for d in range(1, 1000 - n):
        s0 = 1000 - n + d
        s1 = 2000 - n - 2 * d
        if s0 % 5 == 0 and s1 % 5 == 0 and s0 * s1:
            ms = max(s0 - s1, ms)
print(ms)

Ответ: 1970

Поляков-8266
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $S$ – стоп. Известно, что каждый из символов $0,$ $1$ и $2$ есть в исходной строке. Суммы значений в начальной и конечной строках кратны $5,$ при этом больше $0.$ Определите минимальную возможную сумму исходной строки при выполнении этого условия.

Решение:

Пусть в исходной строке было $n$ нулей, $e$ единиц и $d$ двоек. Из условия задачи имеем: $1 \leqslant n \leqslant 998,$ $1 \leqslant e \leqslant 998,$ $1 \leqslant d \leqslant 998.$ Кроме того, $n + e + d = 1000.$ Сумма значений начальной строки $$S_0 = e + 2d = 1000 - n + d$$ Сумма значений конечной строки $$S_1 = n + 2e = 2000 - n - 2d$$ Эти суммы должны быть кратны $5$ и быть ненулевыми. Минимум $S_0$ найдём перебором

Python


ms = float('inf')
for n in range(998, 1, -1):
    for d in range(1, 1000 - n):
        s0 = 1000 - n + d
        s1 = 2000 - n - 2 * d
        if s0 % 5 == 0 and s1 % 5 == 0 and s0 * s1:
            ms = min(s0, ms)
print(ms)

Ответ: 15

Поляков-8265
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $S$ – стоп. Известно, что каждый из символов $0,$ $1$ и $2$ есть в исходной строке. Суммы значений в начальной и конечной строках кратны $5,$ при этом больше $0.$ Определите максимальную возможную сумму исходной строки при выполнении этого условия.

Решение:

Python


ms = -float('inf')
for n in range(998, 1, -1):
    for d in range(1, 1000 - n):
        s0 = 1000 - n + d
        s1 = 2000 - n - 2 * d
        if s0 % 5 == 0 and s1 % 5 == 0 and s0 * s1:
            ms = max(s0, ms)
print(ms)

Ответ: 1985

Поляков-8264
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $S$ – стоп. Известно, что каждый из символов $0,$ $1$ и $2$ есть в исходной строке. Суммы значений в начальной и конечной строках кратны $5,$ при этом больше $0.$ При каком максимальном количестве символов $0$ в исходной строке это возможно?

Решение:

Пусть в исходной строке было $n$ нулей, $e$ единиц и $d$ двоек. Из условия задачи имеем: $1 \leqslant n \leqslant 998,$ $1 \leqslant e \leqslant 998,$ $1 \leqslant d \leqslant 998.$ Кроме того, $n + e + d = 1000.$ Сумма значений начальной строки $$S_0 = e + 2d = 1000 - n + d$$ Сумма значений конечной строки $$S_1 = n + 2e = 2000 - n - 2d$$ Эти суммы должны быть кратны $5$ и быть ненулевыми. Можно подобрать максимум $n$ перебором

Python


for n in range(998, 1, -1):
    f = False
    for d in range(1, 1000 - n):
        s0 = 1000 - n + d
        s1 = 2000 - n - 2 * d
        if s0 % 5 == 0 and s1 % 5 == 0 and s0 * s1:
            print(n)
            f = True
            break
    if f:
        break

Ответ: 990

Поляков-8263
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $S$ – стоп. Известно, что количество символов $0$ и $1$ в исходной строке было одинаково, а сумма значений в исходной строке больше суммы значений в конечной строке на $200.$ Какое количество цифр $2$ было в исходной строке?

Решение:

Пусть в исходной строке было $n$ нулей. Столько же было и единиц. Пусть также двоек сначала было $d.$ Каждые ноль и единица дают увеличение суммы конечной строки на $1,$ а каждая двойка уменьшает сумму значений конечной строки на $2.$ Получаем систему: $$ \begin{cases} 2n + d = 1000, \\ n + 2d - 3n = 200 \end{cases} $$ Значит $d = 400.$ Проверяем

Python


from random import shuffle
ned = ['0'] * 300 + ['1'] * 300 + ['2'] * 400
shuffle(ned)
s = ['l'] + ned + ['l']
print(f"Количество единиц в начальной строке: {s.count('1')}")
s0 = sum(int(x) for x in s if x != 'l')
print(f"Сумма значений конечной строки: {s0}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '2,R,q1'},
         '2': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
s1 = sum(int(x) for x in s if x != 'l')
print(f"Сумма значений конечной строки: {s1}")
print(f"Сумма значений начальной строки больше суммы значений конечной строки на {s0-s1}")

Ответ: 400

Поляков-8262
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

Команды движения каретки: $L$ – влево, $R$ – вправо, $S$ – стоп. После выполнения программы получилась строка с одинаковым количеством символов $1$ и $2$, при этом сумма значений в ней равна $432.$ Сколько было единиц в исходной строке?

Решение:

Исполнитель завершает работу только на пустом символе. Пусть количество символов $1$ и $2$ в конечной строке $N$ каждый. Тогда $1 \cdot N + 2 \cdot N = 432.$ Отсюда $N = 144.$ Символ $1$ получается из исходного нуля, а символ $2$ из исходной единицы. Значит, начальная строка должна содержать по $144$ нуля и единицы, а оставшиеся символы были двойками. Проверяем

Python


s = ['l'] + ['0'] * 144 + ['1'] * 144 + ['2'] * (1000 - 288) + ['l']
print(f"Количество единиц в начальной строке: {s.count('1')}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '2,R,q1'},
         '2': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Сумма значений конечной строки: {sum(int(x) for x in s if x != 'l')}")

Ответ: 144

Поляков-8261
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

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

Решение:

Исполнитель завершает свою работу только на пустом символе. Каждая единица преобразуется в двойку, а каждая двойка — в ноль. Значит, максимальное количество единиц в исходной строке равно $480 : 2 = 240,$ а остальные символы —двойки. Проверяем

Python


s = ['l'] + ['1'] * 240 + ['2'] * (1000 - 240) + ['l']
print(f"Количество единиц в начальной строке: {s.count('1')}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '2,R,q1'},
         '2': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Сумма значений конечной строки: {sum(int(x) for x in s if x != 'l')}")

Ответ: 240

Поляков-8260
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули, единицы и двойки. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$	$2$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$2, \, R, \, q_1$	$0, \, R, \, q_1$

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

Решение:

Программа останавливается только на пустом символе, заменяя при этом нули на единицы. Чтобы сумма значений строки была ровно $455,$ необходимо, чтобы в конечной строке появилось ровно $455$ единиц, а оставшиеся символы, кроме пустых, были нулями. Т.е. исходная строка должна иметь максимум $455$ нулей, причём оставшиеся непустые символы должны быть двойками. Проверяем программно

Python


s = ['l'] + ['0'] * 455 + ['2'] * (1000 - 455) + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '2,R,q1'},
         '2': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Сумма значений конечной строки: {sum(int(x) for x in s if x != 'l')}")

Ответ: 455

Поляков-8259
(Е. Джобс) На ленте исполнителя МТ в соседних ячейках записана последовательность из $1000$ символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0, \, R, \, q_1$

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

Решение:

Программа останавливается только на пустом символе. При этом все единицы становятся нулями, а нули — единицами. Получаем, что в конечной строке находятся ровно $422$ единицы, которые получились из $422$ нулей исходной строки. Проверяем программно:

Python


s = ['l'] + ['0'] * 422 + ['1'] * (1000 - 422) + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Количество единиц в конечной строке: {s.count('1')}")

Ответ: 422

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0, \, R, \, q_1$

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

Решение:

Программа останавливается только на пустом символе, и единицы заменяет нулями, а нули — единицами. Значит, чтобы в конечной строке появилось $319$ нулей, необходимо, чтобы в исходной было столько же единиц. Проверим с помощью программы

Python


s = ['l'] + ['1'] * 319 + ['0'] * (1000 - 319) + ['l']
print(f"Количество единиц в начальной строке: {s.count('1')}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Количество нулей в конечной строке: {s.count('0')}")

Ответ: 319

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, R, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, R, \, q_1$	$0, \, R, \, q_1$

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

Решение:

Программа останавливается только на пустом символе, заменяя нули на единицы и единицы на нули. Значит, чтобы в конечной строке появилось $515$ нулей, необходимо, чтобы в начальной было столько же единиц, а значит, нулей в исходной строке должно быть $1000 - 515 = 485.$ Для проверки напишем программу

Python


s = ['l'] + ['1'] * 515 + ['0'] * 485 + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = 0
state='q0'
table = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,R,q1'},
         '1': {'q1': '0,R,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Количество нулей в конечной строке: {s.count('0')}")

Ответ: 485

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

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

	$\lambda$	$0$	$1$
$q_0$	$\lambda , \, L, \, q_1$
$q_1$	$\lambda , \, S, \, q_1$	$1, \, L, \, q_1$	$0, \, S, \, q_1$

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

Решение:

Если в исходной строке нулей совсем нет, то на выходе получится строка из $1000$ нулей. Значит хотя бы один нуль в исходной строке присутствует. Действительно, если на вход программы подать строку $$\lambda \lambda \underbrace{11\ldots 11}_{241} 0 \underbrace{11\ldots 11}_{758} \lambda \lambda$$ на выходе получится строка, содержащая ровно $758$ нулей. Для проверки напишем программу

Python


#s = ['l'] + ['1'] * 1000 + ['l'] # Для такой строки в конце выпонения программы будет 1000 нулей
s = ['l'] + ['1'] * 241 + ['0'] + ['1'] * 758 + ['l']
print(f"Количество нулей в начальной строке: {s.count('0')}")
p = len(s) - 1
state='q0'
table = {'l': {'q0': 'l,L,q1', 'q1': 'l,S,q1'},
         '0': {'q1': '1,S,q1'},
         '1': {'q1': '0,L,q1'}}
act = table[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
step = {'L': 1, 'R': -1, 'S': 0}
while act[1] != 'S':
    p -= step[act[1]]
    act = table[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f"Количество нулей в конечной строке: {s.count('0')}")

Ответ: 1

Основная волна. Пересдача. 03.07.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды

заменить (111, 27)
преобразует строку $05111150$ в строку $0527150$.
Если в строке нет вхождений цепочки $v$, то выполнение команды заменить ($v, \, w$) не меняет эту строку.

Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл

    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции

    ЕСЛИ условие
        ТО команда1
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).
В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (42) ИЛИ нашлось (822) ИЛИ нашлось (222)
    ЕСЛИ нашлось (42)
      ТО заменить (42, 2)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (822)
      ТО заменить (822, 24)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (222)
      ТО заменить (222, 8)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «4», а затем содержащая $n$ цифр «2» $(3 < n < 10~000).$ Определите наибольшее возможное значение суммы цифр в строке, которая может быть получена в результате выполнения программы.

Решение:

Python


def conv(s):
    while '42' in s or '822' in s or '222' in s:
        if '42' in s:
            s = s.replace('42', '2', 1)
        if '822' in s:
            s = s.replace('822', '24', 1)
        if '222' in s:
            s = s.replace('222', '8', 1)
    return s

print(max(sum(int(x) for x in conv('4' + '2' * n)) for n in range(4, 10000)))

Ответ: 40

Основная волна. Резерв. 23.06.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции

    ЕСЛИ условие
        ТО команда1
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).
В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (312) ИЛИ нашлось (222)
    ЕСЛИ нашлось (12)
      ТО заменить (12, 2)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (312)
      ТО заменить (312, 21)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (222)
      ТО заменить (222, 311)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая $n$ цифр «2» $(3 < n < 4~000).$ Определите наибольшее значение $n,$ при котором количество цифр «1» в строке, получившаяся в результате выполнения программы, равно трём.

Решение:

Python


def conv(s):
    while '12' in s or '312' in s or '222' in s:
        if '12' in s:
            s = s.replace('12', '2', 1)
        if '312' in s:
            s = s.replace('312', '21', 1)
        if '222' in s:
            s = s.replace('222', '311', 1)
    return s

for n in range(3999, 3, -1):
    if conv('1' + '2' * n).count('1') == 3:
        print(n)
        break

Ответ: 2964

Основная волна. Резерв. 19.06.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции

    ЕСЛИ условие
        ТО команда1
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).
В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (15) ИЛИ нашлось (599) ИЛИ нашлось (999)
    ЕСЛИ нашлось (15)
      ТО заменить (15, 9)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (599)
      ТО заменить (599, 5)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (999)
      ТО заменить (999, 19)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая $n$ цифр «9» $(3 < n < 10~000).$ Определите наименьшее значение $n,$ при котором сумма цифр в строке, получившаяся в результате выполнения программы, равна $30.$

Решение:

Python


def transf(s):
    while '15' in s or '599' in s or '999' in s:
        if '15' in s:
            s = s.replace('15', '9', 1)
        if '599' in s:
            s = s.replace('599', '5', 1)
        if '999' in s:
            s = s.replace('999', '19', 1)
    return s


for n in range(4, 10_000):
    s = transf('1' + '9' * n)
    if sum(int(x) for x in s) == 30:
        print(n)
        break

Ответ: 24

Основная волна. 11.06.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции

ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции

ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (2222)
    ЕСЛИ нашлось (12)
      ТО заменить (12, 2)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (322)
      ТО заменить (322, 21)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (2222)
      ТО заменить (2222, 3)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая $n$ цифр «2» $(3 < n < 4~000).$ Определите наибольшее значение цифр в строке, которая может быть результатом выполнения программы.

Решение:

Python


def transf(s):
    while '12' in s or '322' in s or '2222' in s:
        if '12' in s:
            s = s.replace('12', '2', 1)
        if '322' in s:
            s = s.replace('322', '21', 1)
        if '2222' in s:
            s = s.replace('2222', '3', 1)
    return s

mx = 0
for n in range(4, 4000):
    s = transf('1' + '2' * n)
    mx = max(mx, sum(int(x) for x in s))
print(mx)

Ответ: 89

Основная волна. 10.06.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции

    ЕСЛИ условие
        ТО команда1
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).
В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (31) ИЛИ нашлось (11111) ИЛИ нашлось (144)
    ЕСЛИ нашлось (31)
      ТО заменить (31, 4)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (11111)
      ТО заменить (11111, 33)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (144)
      ТО заменить (144, 133)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «3», а затем содержащая $n$ цифр «1» $(5 < n < 1~000).$ Определите значение $n,$ при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $160.$

Решение:

Python


def transf(s):
    while '31' in s or '11111' in s or '144' in s:
        if '31' in s:
            s = s.replace('31', '4', 1)
        if '11111' in s:
            s = s.replace('11111', '33', 1)
        if '144' in s:
            s = s.replace('144', '133', 1)
    return s

for n in range(6, 1000):
    if sum(int(x) for x in transf('3' + '1' * n)) == 160:
        print(n)

Ответ: 135

Апробация. 14.05.2025-1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции

ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции

Дана программа для Редактора:

НАЧАЛО
ПОКА нашлось (45) ИЛИ нашлось (655) ИЛИ нашлось (555)
    ЕСЛИ нашлось (45)
      ТО заменить (45, 5)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (655)
      ТО заменить (655, 54)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (555)
      ТО заменить (555, 6)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «4», а затем содержащая $n$ цифр «5» $(3 < n < 10~000).$ Определите наименьшее значение $n,$ при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $25.$

Решение:

Python


def transform(s):
    while '45' in s or '655' in s or '555' in s:
        if '45' in s:
            s = s.replace('45', '5', 1)
        if '655' in s:
            s = s.replace('655', '54', 1)
        if '555' in s:
            s = s.replace('555', '6', 1)
    return s

for n in range(4, 10_001):
    s = transform('4' + '5' * n)
    if sum(int(x) for x in s) == 25:
        print(n)
        break

Ответ: 14

ЕГКР. 19.04.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора:

   НАЧАЛО
   ПОКА нашлось (42) ИЛИ нашлось (8222) ИЛИ нашлось (2222)
      ЕСЛИ нашлось (42)
         ТО заменить (42, 2)
      КОНЕЦ ЕСЛИ
      ЕСЛИ нашлось (8222)
         ТО заменить (8222, 24)
      КОНЕЦ ЕСЛИ
      ЕСЛИ нашлось (2222)
         ТО заменить (2222, 8)
      КОНЕЦ ЕСЛИ
   КОНЕЦ ПОКА
   КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$4$», а затем содержащая $n$ цифр «$2$» ($3 < n < 10~000$). Определите наименьшее значение $n,$ при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $110.$

Решение:

Python


def ed(s):
    while '42' in s or '8222' in s or '2222' in s:
        if '42' in s:
            s = s.replace('42', '2', 1)
        if '8222' in s:
            s = s.replace('8222', '24', 1)
        if '2222' in s:
            s = s.replace('2222', '8', 1)
    return s

for n in range(4, 10_000):
    if sum(int(x) for x in ed('4' + '2' * n)) == 110:
        print(n)
        break

Ответ: 1591

Досрочный экзамен. 08.04.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции

    ЕСЛИ условие
        ТО команда1
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).
В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Дана программа для Редактора

   НАЧАЛО
        ПОКА нашлось (31) ИЛИ нашлось (211) ИЛИ нашлось (1111)
            ЕСЛИ нашлось (31)
                ТО заменить (31, 1)
            КОНЕЦ ЕСЛИ
            ЕСЛИ нашлось (211)
                ТО заменить (211, 13)
            КОНЕЦ ЕСЛИ
            ЕСЛИ нашлось (1111)
                ТО заменить (1111, 2)
            КОНЕЦ ЕСЛИ
        КОНЕЦ ПОКА
    КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$3$», а затем содержащая $n$ цифр «$1$» $(3 < n < 10~000).$ Определите наименьшее значение $n,$ при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $15.$

Решение:

Python


def conv(s):
    while '31' in s or '211' in s or '1111' in s:
        if '31' in s:
            s = s.replace('31', '1', 1)
        if '211' in s:
            s = s.replace('211', '13', 1)
        if '1111' in s:
            s = s.replace('1111', '2', 1)
    return s

for n in range(4, 10_000):
    if sum(int(x) for x in conv('3' + '1' * n)) == 15:
        print(n)
        break

Ответ: 50

Апробация. 05.03.2025-2
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции

ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $81$ идущих подряд цифр $1?$ В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (111) ИЛИ нашлось (88888)
    ЕСЛИ нашлось (111)
        ТО заменить (111, 88)
        ИНАЧЕ заменить (88888, 8)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:

Python


s = '1' * 81

while '111' in s or '88888' in s:
    if '111' in s:
        s = s.replace('111', '88', 1)
    else:
        s = s.replace('88888', '8', 1)

print(s)

Ответ: 88

Апробация. 05.03.2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции

ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $99$ идущих подряд цифр $9?$ В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (33333) ИЛИ нашлось (999)
    ЕСЛИ нашлось (33333)
        ТО заменить (33333, 99)
        ИНАЧЕ заменить (999, 3)
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:

Python


s = '9' * 99

while '33333' in s or '999' in s:
    if '33333' in s:
        s = s.replace('33333', '99', 1)
    else:
        s = s.replace('999', '3', 1)

print(s)

Ответ: 3399

Шастин. 7.6.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение программы заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки $v$, то выполнение команды заменить (u, v) не меняет эту строку.

Б) нашлось (v)
Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не меняется.

Дана программа для Редактора

НАЧАЛО
  ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (222)
    ЕСЛИ нашлось (12)
      ТО заменить (12,  2)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (322)
      ТО заменить (322,  21)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (222)
      ТО заменить (222,  3)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$1$», а затем содержащая $n$ цифр «$2$» $(3 < n < 10~000).$ Определите значение $n,$ при котором сумма числовых значений цифр в строке, являющейся результатом работы программы, максимальна.

Решение:

Python


def trans(s):
    while '12' in s or '322' in s or '222' in s:
        if '12' in s:
            s = s.replace('12', '2', 1)
        if '322' in s:
            s = s.replace('322', '21', 1)
        if '222' in s:
            s = s.replace('222', '3', 1)
    return s

max_sum = 0
ans = 0
for n in range(4, 10_001):
    s = trans('1' + '2' * n)
    m = sum(int(x) for x in s)
    if m > max_sum:
        max_sum = m
        ans = n
print(ans)

Ответ: 50

Шастин. 5.6.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора

НАЧАЛО
  ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось(555)
    ЕСЛИ нашлось (25)
      ТО заменить (25,  5)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (355)
      ТО заменить (355,  522)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (555)
      ТО заменить (555,  3)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$2$», а затем содержащая $n$ цифр «$5$» $(3 < n < 1000).$ Определите наибольшую возможную сумму цифр в строке, содержащей ровно $10$ цифр «$2$», среди всех строк, которые могут получиться в результате выполнения программы.

Решение:

Python


def trans(s):
    while '25' in s or '355' in s or '555' in s:
        if '25' in s:
            s = s.replace('25', '5', 1)
        if '355' in s:
            s = s.replace('355', '522', 1)
        if '555' in s:
            s = s.replace('555', '3', 1)
    return s

max_sum = 0

for n in range(4, 1001):
    s = trans('2' + '5' * n)
    if s.count('2') == 10:
        max_sum = max(max_sum, sum(int(x) for x in s))
print(max_sum)

Ответ: 57

Шастин. 3.6.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора

НАЧАЛО
  ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось(>0)
    ЕСЛИ нашлось (>1)
      ТО заменить (>1,  22>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>2)
      ТО заменить (>2,  2>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>0)
      ТО заменить (>0,  1>)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая $25$ цифр «0», $n$ цифр «$1$» $(3 < n < 1000)$ и $25$ цифр «2», расположенных в произвольном порядке. Определите наименьшее $n,$ при котором сумма числовых значений строки, получившейся в результате выполнения программы, является четырёхзначным числом, кратным $15.$

Решение:

Python


def transf(s):
    while '>1' in s or '>2' in s or '>0' in s:
        if '>1' in s:
            s = s.replace('>1', '22>', 1)
        if '>2' in s:
            s = s.replace('>2', '2>', 1)
        if '>0' in s:
            s = s.replace('>0', '1>', 1)
    return s

for n in range(4, 1000):
    expr = transf('>' + '0' * 25 + '1' * n + '2' * 25).replace('>', '')
    num = sum(int(x) for x in expr)
    if 999 < num < 10_000 and num % 15 == 0:
        print(n)
        break

Ответ: 240

Шастин. 1.6.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $234$ идущих подряд цифр $3?$ В ответе запишите значение произведения цифр в полученной строке

НАЧАЛО
  ПОКА нашлось (33333) ИЛИ нашлось (1111)
    ЕСЛИ нашлось (33333)
      ТО заменить (33333,  111)
      ИНАЧЕ заменить (111,  3)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

Решение:

Python


s = '3' * 234

while '33333' in s or '1111' in s:
    if '33333' in s:
        s = s.replace('33333', '111', 1)
    else:
        s = s.replace('111', '33', 1)
print(3 ** s.count('3'))

Ответ: 243

Статград. Профиль. 12.05.2025-1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора:

ПОКА НЕ нашлось (00)
  заменить (01, 210)
  заменить (02, 3201)
  заменить (03, 1302)
КОНЕЦ ПОКА

Известно, что исходная строка начиналась с нуля и заканчивалась нулём, а между ними были только цифры «$1$», «$2$» и «$3$». После выполнения данной программы получилась строка, содержащая $114$ единиц, $215$ двоек и $111$ троек. Сколько цифр «$2$» было в исходной строке?

Решение:

При проскакивании $0$ через $1$ получаем такое преобразование: $01 \to 210,$ т.е. одна $1$ даёт в итоговую строку одну $2$ и одну $1.$ Теперь рассмотрим проскакивание нуля через $2{:}$ $02 \to 3201 = 02 \to 32210.$ Т.е. одна двойка выдаёт в итоговую строку по одной $1$ и $3$ и две $2.$ Наконец, проскакивание $0$ через $3$ приводит к преобразованию $03 \to 1332210.$ Т.е. одна $3$ даёт в итоговой строке две $1,$ две $2$ и две $3.$ Пусть в начальной строке было $e$ единиц, $d$ двоек и $t$ троек. Тогда получаем систему уравнений: $$ \begin{cases} e + d + 2t & = & 114 \\ e + 2d + 2t & = & 215 \\ d + 2t & = & 111 \end{cases} $$ Вычитая второе уравнение из первого сразу получаем, что $d = 101.$ Можно найти и остальные числа: $t = 5,$ $e = 3.$ Для проверки напишем небольшую программу:

Python


s = '0' + '111' + '2' * 101 + '3' * 5 + '0'

while '00' not in s:
    s = s.replace('01', '210', 1)
    s = s.replace('02', '3201', 1)
    s = s.replace('03', '1302', 1)

print(s.count('1'), s.count('2'), s.count('3'))

Ответ: 101

Статград. База. 12.05.2025-1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора:

НАЧАЛО
  ПОКА нашлось (>5) ИЛИ нашлось (>7) ИЛИ нашлось (>2)
    ЕСЛИ нашлось (>5)
      ТО заменить (>5, 77>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>7)
      ТО заменить (>7, 222>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>2)
      ТО заменить (>2, 55>)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая $28$ цифр «$2$», $n$ цифр «$7$» $(0 < n < 10000)$ и $11$ цифр «$5$», расположенных в произвольном порядке. Определите наименьшее значение $n,$ при котором сумма числовых значений цифр строки, получившихся в результате выполнения программы, больше $1000$ и кратна $20.$

Решение:

Каждая цифра $5$ даёт в итоговой строке две цифры $7,$ в сумме $11 \cdot 2 \cdot 7 = 154.$ Каждая цифра $2$ даёт две пятерки и в сумме $28 \cdot 2 \cdot 5 = 280.$ Наконец каждая семёрка выдаст в строку три двойки, а в сумме $6n.$ Значит, сумма цифр в итоговой строке будет $$280 + 154 + 6n = 434 + 6n = 440 + (n-1) \cdot 6.$$ Так как $440$ делится на $20,$ то и число $6(n-1)$ тоже должно делиться на $20,$ или, что то же самое, $3(n-1)$ должно делиться на $10.$ Но $3$ — это простое число, поэтому на $10$ должно делиться $(n-1).$ Учитывая, что сумма всех чисел должна быть больше $1000,$ получаем, что $n-1 = 100$ (если $n-1 = 90,$ то $6(n-1) = 540,$ а $440 + 540 < 1000$). Поэтому $n = 101.$

Программное решение

Python


def trasnf(s):
    while '>5' in s or '>7' in s or '>2' in s:
        if '>5' in s:
            s = s.replace('>5', '77>', 1)
        if '>7' in s:
            s = s.replace('>7', '222>', 1)
        if '>2' in s:
            s = s.replace('>2', '55>', 1)
    return s

for n in range(1, 10_000):
    s = trasnf('>' + '2' * 28 + '7' * n + '5' * 11)
    d = sum(int(x) for x in s[:-1])
    if d > 1000 and d % 20 == 0:
        print(n)
        break

Ответ: 101

Демо-2025
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции

    ЕСЛИ условие
        ТО команда1
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно).
В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $81$ идущей подряд цифры $1$? В ответе запишите полученную строку.

  НАЧАЛО
  ПОКА нашлось (11111) ИЛИ нашлось (888)
    ЕСЛИ нашлось (11111)
      ТО заменить (11111, 88)
      ИНАЧЕ заменить (888,8)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
  КОНЕЦ

Решение:

Python


s = '1' * 81

while '11111' in s or '888' in s:
    if '11111' in s:
        s = s.replace('11111', '88', 1)
    else:
        s = s.replace('888', '8', 1)

print(s)

Ответ: 881

Шастин. 7.05.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Определите сумму цифр в строке, получившейся в результате применения приведённой ниже программы к входной строке, состоящей из единицы, за которой следуют $110$ восьмёрок.

НАЧАЛО
ПОКА нашлось (1)
   ЕСЛИ нашлось (18)
      ТО заменить (18,  8881)
      ИНАЧЕ заменить (1,  888)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:

Python


s = '1' + '8' * 110

while '1' in s:
    if '18' in s:
        s = s.replace('18', '8881', 1)
    else:
        s = s.replace('1', '888', 1)
print(sum(int(x) for x in s))

Ответ: 2664

Шастин. 13.03.2025
(Д. Бахтиев) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для редактора:

ПОКА нашлось (4444) ИЛИ нашлось (222)
   ЕСЛИ нашлось (4444)
      ТО заменить (4444,  2)
      ИНАЧЕ заменить (222,  44)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

На вход программе подана строка из $222$ подряд идущих символов $4.$ Сколько замен произойдёт в ходе работы алгоритма?

Решение:

Python


s = '4' * 222
q = 0

while '4444' in s or '222' in s:
    if '4444' in s:
        s = s.replace('4444', '2', 1)
    else:
        s = s.replace('222', '44', 1)
    q += 1
print(q)

Ответ: 86

ЕГКР. 21.12.2024
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

заменить (111, 27)
преобразует строку $05111150$ в строку $0527150$.
Если в строке нет вхождений цепочки $v$, то выполнение команды заменить ($v, \, w$) не меняет эту строку.

Цикл

ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции

ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции

Дана программа для Редактора:

   НАЧАЛО
   ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (222)
      ЕСЛИ нашлось (12)
         ТО заменить (12, 2)
      КОНЕЦ ЕСЛИ
      ЕСЛИ нашлось (322)
         ТО заменить (322, 21)
      КОНЕЦ ЕСЛИ
      ЕСЛИ нашлось (222)
         ТО заменить (222, 3)
      КОНЕЦ ЕСЛИ
   КОНЕЦ ПОКА
   КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$1$», а затем содержащая $n$ цифр «$2$» ($3 < n < 10~000$). Определите наименьшее значение $n,$ при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $15.$

Решение:

Python


for n in range(4, 10_000):
    s = '1' + '2' * n
    while '12' in s or '322' in s or '222' in s:
        if '12' in s:
            s = s.replace('12', '2', 1)
        if '322' in s:
            s = s.replace('322', '21', 1)
        if '222' in s:
            s = s.replace('222', '3', 1)
    if sum(int(x) for x in s) == 15:
        print(n)
        break

Ответ: 37

Статград. 01.04.2025-1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Цикл

ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции

ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции

Определите сумму цифр в строке, получившейся в результате применения приведённой ниже программы к входной строке, состоящей из одной двойки, за которой следуют $140$ цифр $3$ подряд.

НАЧАЛО
    ПОКА нашлось (2)
        ЕСЛИ нашлось (23)
            ТО заменить (23, 3332)
            ИНАЧЕ заменить (2, 333)
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
КОНЕЦ

В ответе укажите только сумму цифр в получившейся строке.

Решение:

Python


s = '2' + '3' * 140
while '2' in s:
    if '23' in s:
        s = s.replace('23', '3332', 1)
    else:
        s = s.replace('2', '333', 1)
print(sum(int(x) for x in s))

Ответ: 1269

Статград. 28.01.2025-1
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
А) заменить $(v, \, w)$.
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды
заменить $(111, \, 27)$
преобразует строку $05111150$ в строку $0527150.$ Если в строке нет вхождений цепочки $v$, то выполнение команды заменить $(v, \, w)$ не меняет эту строку.
Б) нашлось $(v)$.
Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

  НАЧАЛО
     ПОКА нашлось (111) ИЛИ нашлось (22)
        заменить (111, 2)
        заменить (222, 1)
        заменить (221, 1)
        заменить (122, 1)
        заменить (22, 2)
     КОНЕЦ ПОКА
  КОНЕЦ

Определите, сколько различных строк, содержащих ровно $5$ единиц, может получиться в результате применения этой программы к строкам, состоящим только из единиц и двоек.

Решение:

Для экспериментов со строками напишем программу.

Python


s = '21121121'

while '111' in s or '22' in s:
    s = s.replace('111', '2', 1)
    s = s.replace('222', '1', 1)
    s = s.replace('221', '1', 1)
    s = s.replace('122', '1', 1)
    s = s.replace('22', '2', 1)

print(s)

Нетрудно заметить, что строка не будет меняться циклом, если ней нет трёх и более подряд стоящих $1$ и двух и более стоящих $2$. Всего имеем три типа таких строк:
$X1121121Y$
$X11212121Y
\(X121212121Y$
Здесь вместо $X$ и $Y$ обозначает либо символ $2$ либо отсутствие какого-либо символа (пустой символ). Строки первого типа — это строки, в которых есть две пары единиц $11$ и одна единица $1$. Всего существует три разных строк такого типа (одну единственную единицу мы можем поставить либо на первое место, либо на второе, либо на третье). С учётом того, что $X$ и $Y$ могут принимать два разных значения, получаем, что строк первого типа всего $3 \cdot 4 = 12.$ Аналогично определяем, что разных строк второго типа $4 \cdot 4 = 16,$ а третьего типа $4 \cdot 1 = 4.$ Всего получаем $12 + 4 + 16 = 32.$

Ответ: 32

Статград. 17.12.2024
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
А) заменить $(v, \, w)$.
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды
заменить $(111, \, 27)$
преобразует строку $05111150$ в строку $0527150.$ Если в строке нет вхождений цепочки $v$, то выполнение команды заменить $(v, \, w)$ не меняет эту строку.
Б) нашлось $(v)$.
Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

  НАЧАЛО
     ПОКА нашлось (111) ИЛИ нашлось (22)
        заменить (111, 2)
        заменить (222, 1)
        заменить (221, 1)
        заменить (122, 1)
        заменить (22, 2)
     КОНЕЦ ПОКА
  КОНЕЦ

Определите, сколько различных строк, содержащих ровно $9$ двоек, может получиться в результате применения этой программы к строкам, состоящим только из единиц и двоек.

Решение:

$3 \cdot 2^8 \cdot 3 = 2304$
Ответ: 2304

Статград. 24.10.2024
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
А) заменить $(v, \, w)$.
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды
заменить $(111, \, 27)$
преобразует строку $05111150$ в строку $0527150.$ Если в строке нет вхождений цепочки $v$, то выполнение команды заменить $(v, \, w)$ не меняет эту строку.
Б) нашлось $(v)$.
Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

  НАЧАЛО
     ПОКА нашлось (111)
        заменить (111, 2)
        заменить (222, 11)
        заменить (1, 2)
     КОНЕЦ ПОКА
  КОНЕЦ

Определите количество таких натуральных $N$ из интервала $[123 456 794; \, 678 901 234],$ для которых в результате применения данной программы к строке, состоящей из $N$ единиц, получится строка, состоящая только из двоек.

Решение:

Постараемся понять, для каких $N$ финальная строка стостоит из одних двоек. Для этого напишем программу

Python


for N in range(3, 100):
    s = '1' * N
    while '111' in s:
        s = s.replace('111', '2', 1)
        s = s.replace('222', '11', 1)
        s = s.replace('1', '2', 1)
    if s.count('1') == 0:
        print(N, s)

Опуская первые две строчки вывода программы, видим, что строка $22$ получается для чисел $9б \, 25б \, 41 \ldots$. Строка $222$ получается для $N = 10, \, 26, \, 42, \, \ldots$. А строка $2222$ получится в итоге для чиесл $16, \, 32, \, 48, \ldots$. Каждая из трех последовательностей $N$ является арифметической прогрессией с разностью прогессии $16$. Т.о., задача свелась к подсчёту кодичества чисел, имеющих в остатке от деления на $16$ числа $0, \, 9, \, 10$.

Так как $123456794 = 10 \,\, (\mod 16)$. И $(678901234 - 123456794) // 16 = 34715277$, то количество чисел на указанном в задаче интервале, которые имеют в остатке от деления на $16$ число $10$ равно $34715278$. Аналогичные подсчёты показывает, что количество чисел, имеющих в остатке $0$ при делении на $16$ такое же количество, а имеющих остаток $9$ всего $34715277$ чисел. Общее количество $N$, удовлетворяющих условию задачи будет $34715278 + 34715278 + 34715277$

Ответ: $104~145~833$

Шастин. 9.2.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для редактора:

НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>0)
   ЕСЛИ нашлось (>1)
      ТО заменить (>1,  22>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>2)
      ТО заменить (>2,  2>)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (>0)
      ТО заменить (>0,  1>)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «$Ю$», а затем содержащая $19$ цифр «$0$», $n$ цифр «$1$» ($6 < n < 100$) и $19$ цифр «$2$». Определите наименьшее значение $n$, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, оканчивается на две одинаковые цифры.

Решение:

Легко заметить, что результат выполнения программы не зависит от взаимного расположения цифр в строке.

Python


for n in range(7, 100):
    s = '>' + '0' * 19 + '1' * n + '2' * 19
    while any(ch in s for ch in ('>1', '>2', '>0')):
        if '>1' in s:
            s = s.replace('>1', '22>', 1)
        if '>2' in s:
            s = s.replace('>2', '2>', 1)
        if '>0' in s:
            s = s.replace('>0', '1>', 1)
    dsum = str(s.count('1') + 2 * s.count('2'))
    if dsum[-2] == dsum[-1]:
        print(n)
        break

Ответ: 19

Шастин. 19.01.2025
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для редактора:

НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
   ЕСЛИ нашлось (25)
      ТО заменить (25,  5)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (355)
      ТО заменить (355,  522)
   КОНЕЦ ЕСЛИ
   ЕСЛИ нашлось (555)
      ТО заменить (555,  3)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$2$», а затем содержащая $n$ цифр «$5$» ($3 < n < 10~000.$) Определите наименьшее значение $n$, при котором в строке, получившейся в результате выполнения программы, количество цифр «$2$» равно $10.$

Решение:

Python


def trans(s):
    while '25' in s or '355' in s or '555' in s:
        if '25' in s:
            s = s.replace('25', '5', 1)
        if '355' in s:
            s = s.replace('355', '522', 1)
        if '555' in s:
            s = s.replace('555', '3', 1)
    return s

for n in range(4, 10_000):
    if trans('2' + '5' * n).count('2') == 10:
        print(n)
        break

Ответ: 681

Шастин. 18.12.2024
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

А) заменить (v, w)
Эта команда заменяет в строке все вхождения цепочки $v$ на цепочку $w$. Например, выполнение программы заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки $v$, то выполнение команды заменить (u, v) не меняет эту строку.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $140$ подряд идущих цифр «8»? В ответе запишите полученную строку.

НАЧАЛО
ПОКА нашлось (888) ИЛИ нашлось (2222)
   ЕСЛИ нашлось (2222)
      ТО заменить (2222, 88)
      ИНАЧЕ заменить (888, 22)
   КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

Решение:

Python


s = '8' * 140

while '888' in s or '2222' in s:
    if '2222' in s:
        s = s.replace('2222', '88')
    else:
        s = s.replace('888', '22')
print(s)

Ответ: 228228

Шастин. 30.11.2024
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора:

НАЧАЛО
  ПОКА нашлось (>3) ИЛИ нашлось(>5) ИЛИ нашлось (>7)
    ЕСЛИ нашлось (>3)
      ТО заменить (>3, 55>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>5)
      ТО заменить (>5, 5>3)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>7)
      ТО заменить (>7, 3>5)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «>», а затем содержащая $10$ цифр «$3$», $10$ цифр «$5$» и $10$ цифр «$7$», расположенных в произвольном порядке.Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы. В ответе запишите только число.

Решение:

Проведём «численный эксперимент» для нескольких значений исходной строки, в которых цифры перемешаны.

Python


from random import shuffle

arr = ['3'] * 10 + ['5'] * 10 + ['7'] * 10
for i in range(10):
    
    shuffle(arr)
    s = '>' + ''.join(arr)

    while '>3' in s or '>5' in s or '>7' in s:
        if '>3' in s:
            s = s.replace('>3', '55>', 1)
        elif '>5' in s:
            s = s.replace('>5', '5>3', 1)
        else:
            s = s.replace('>7', '3>5', 1)


    s = s.replace('>', '')
    print(sum(int(x) for x in s))

Для каждой строки получаем на выходе программы $430.$ Это не строгое математическое доказательство, что всегда будет получаться такое число. Но возникает твёрдая уверенность, что такое $430$ будет получаться всегда. :)
Ответ: 430

Шастин. 6.11.2024
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

Дана программа для Редактора:

НАЧАЛО
  ПОКА нашлось (766) ИЛИ нашлось(677)
    ЕСЛИ нашлось (766)
      ТО заменить (766, 67)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (667)
      ТО заменить (667, 7)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «$7$», а затем содержащая $n$ цифр «$6$» ($3 < n < 10~000)$. Какое количество различных строк может получиться в результате выполнения программы? В ответе запишите только число.

Решение:

При $n = 10~000$ программа будет выполняться очень долго. Поэтому нужно посмотреть на количество получающихся различных строк для меньших чисел.

Python


ans = set()

for n in range(4, 1000):
    s = '7' + '6' * n

    while '766' in s or '667' in s:
        if '766' in s:
            s = s.replace('766', '67', 1)
        else:
            s = s.replace('667', '7', 1)
    ans.add(s)
print(len(ans))

Ответ: 4

Шастин. 18.10.2024
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$.

Дана программа для Редактора:

НАЧАЛО
  ПОКА нашлось (>3) ИЛИ нашлось(>2) ИЛИ нашлось(>0)
    ЕСЛИ нашлось (>3)
      ТО заменить (>3, 22>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>2)
      ТО заменить (>2, 2>)
    КОНЕЦ ЕСЛИ
    ЕСЛИ нашлось (>0)
      ТО заменить (>0, 3>)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с символа «$>$», а затем содержащая $17$ цифр «$0$», $n$ цифр «$3$» и $17$ цифр «$2$», расположенных в произвольном порядке.

Определите наименьшее возможно значение $n$, при котором сумма числовых значений цифр строки, получившейся в результате выполнения программы, является квадратом какого-либо натурального числа.

Решение:

Python


def sum_digs(s):
    return sum(int(x) for x in s if x != '>')

n = 1
while True:
    s = '>' + '0' * 17 + '2' * 17 + '3' * n 
    while '>3' in s or '>2' in s or '>0' in s:
        if '>3' in s:
            s = s.replace('>3', '22>', 1)
        if '>2' in s:
            s = s.replace('>2', '2>', 1)
        if '>0' in s:
            s = s.replace('>0', '3>', 1)
    x = sum_digs(s)
    if (int(x**0.5))**2 == x:
        print(n)
        break
    n += 1

Ответ: 9

Шастин. 4.10.2024
(Д. Бахтиев) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.

А) заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды заменить (111, 27) преобразует строку $05111150$ в строку $0527150$. Если в строке нет вхождений цепочки $v$, то выполнение команды заменить (v, w) не меняет эту строку.

Дана программа для Редактора:

НАЧАЛО
  ПОКА нашлось (411) ИЛИ нашлось(1111)
    ЕСЛИ нашлось (411)
      ТО заменить (411, 14)
    КОНЕЦ ЕСЛИ
      ЕСЛИ нашлось (1111)
      ТО заменить (1111, 1)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «$4$», а затем содержащая и $n$ цифр «$1$» ($ 3 < n < 10~000$).

Определите наибольшее возможно значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.

Решение:

Так как алгоритмы на строках выполняются довольно медленно, то для больших строк время выполнения таких программ может оказаться неприемлемо большим. «Подвох» в условии этого задания как раз и состоит в большим $n$ ($10~000$). Однако, можно ограничиться вначале небольшими $n$ ($20, \, 30, \, 100, \, 300$) и убедиться, что в результате работы такого алгоритма может появиться только одна из шести возможных строк. Значит, не имеет смысла гонять этот алгоритм для больших $n$. (Конечно, это не доказательство. Его нужно провести строго и показать, что существует только $6$ различных вариантов результата работы этого алгоритма. Но на экзамене на это нет времени, да и никто это доказательство там не потребует.)

Python


def editor(s):
    while '411' in s or '1111' in s:
        if '411' in s:
            s = s.replace('411', '14', 1)
        if '1111' in s:
            s = s.replace('1111', '1', 1)
    return s

tmp = set()

for n in range(4, 300):
    s = '4' + '1' * n   
    tmp.add(editor(s))

#print(len(tmp), tmp)
ans = [sum(int(x) for x in el) for el in tmp]
print(max(ans))

Ответ: 8

Шастин. 19.09.2024
(Л. Шастин) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $111$ идущей подряд цифр $3$? В ответе запишите сумму цифр в полученной строке.

НАЧАЛО
  ПОКА нашлось(ЗЗЗЗЗ) ИЛИ нашлось(1111)
    ЕСЛИ нашлось (33333)
      ТО заменить (33333, 11)
      ИНАЧЕ заменить (111, 33)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
КОНЕЦ

Решение:

Python


s = '3'*111
while '33333' in s or '1111' in s:
    s = s.replace('33333', '111', 1) if '33333' in s else s.replace('111', '33', 1)
print(sum(map(int, list(s))))

Ответ: 12

Поляков-7554
(ЕГЭ-2024) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.

1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Если цепочки $v$ в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор.

Дана программа для исполнителя Редактор:

  ПОКА нашлось(ЗЗЗЗЗ) ИЛИ нашлось(999)
    ЕСЛИ нашлось (33333)
      ТО заменить (33333, 99)
      ИНАЧЕ заменить (999, 3)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $81$ идущей подряд цифр $9$? В ответе запишите полученную строку.

Решение:

Python


s = '9' * 81

while '33333' in s or '999' in s:
    s = s.replace('33333', '99', 1) if '33333' in s else s.replace('999', '3', 1)

print(s)

Ответ: 3

Поляков-7553
(ЕГЭ-2024) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.

Дана программа для исполнителя Редактор:

  ПОКА нашлось (22222) ИЛИ нашлось (9999)
    ЕСЛИ нашлось (22222)
      ТО заменить (22222, 99)
      ИНАЧЕ заменить (9999, 2)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $136$ идущих подряд цифр $9$? В ответе запишите полученную строку.

Решение:

Python


s = '9' * 136

while '22222' in s or '9999' in s:
    s = s.replace('22222', '99', 1) if '22222' in s else s.replace('9999', '2', 1)

print(s)

Ответ: 2299

Поляков-7521
(ЕГЭ-2024) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.

Дана программа для исполнителя Редактор:

  ПОКА нашлось (111) ИЛИ нашлось (88888)
    ЕСЛИ нашлось (111)
      ТО заменить (111, 88)
      ИНАЧЕ заменить (88888, 8)
    КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $83$ идущих подряд цифр $8$?

Решение:

Python


s = '8' * 83

while '111' in s or '88888' in s:
    s = s.replace('111', '88', 1) if '111' in s else s.replace('88888', '8', 1)

print(s)

Ответ: 888

Поляков-7470
(ЕГЭ-2024) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.

Дана программа для исполнителя Редактор:

  ПОКА нашлось (33333) ИЛИ нашлось (777)
    ЕСЛИ нашлось (33333)
    ТО заменить (33333, 7)
    ИНАЧЕ заменить (777, 3)
  КОНЕЦ ПОКА

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $108$ идущих подряд цифр $7$?

Решение:

Python


s = '7' * 108

while '33333' in s or '777' in s:
    s = s.replace('33333', '7', 1) if '33333' in s else s.replace('777', '3', 1)

print(s)

Ответ: 3337

Поляков-7469
(ЕГЭ-2024) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.

Дана программа для исполнителя Редактор:

  ПОКА нашлось (33333) ИЛИ нашлось (999)
    ЕСЛИ нашлось (33333)
    ТО заменить (33333, 99)
    ИНАЧЕ заменить (999, 3)
  КОНЕЦ ПОКА

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $100$ идущих подряд цифр $9$?

Решение:

Python


s = '9' * 100

while '33333' in s or '999' in s:
    s = s.replace('33333', '99', 1) if '33333' in s else s.replace('999', '3', 1)

print(s)

Ответ: 333

: Обновлено: 23 декабря 2025

	\(\lambda\)	\(5\)	\(7\)	\(9\)	\(0\)	\(1\)
\(q_0\)	\(\lambda , \, L, \, q_1\)
\(q_1\)	\(\lambda , \, S, \, q_1\)	\(1, \, L, \, q_1\)	\(1, \, L, \, q_1\)	\(0, \, L, \, q_1\)

	\(a_0\)	\(a_1\)	\(\ldots\)	\(a_n\)
\(q_0\)	команда	команда	\(\ldots\)	команда
\(q_1\)	команда	команда	\(\ldots\)	команда
\(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)	\(\ldots\)
\(q_{n-1}\)	команда	команда	\(\ldots\)	команда

	\(\lambda\)	\(Z\)
\(q_0\)	\(\lambda , \, L, \, q_0\)	\(X, \, L, \, q_1\)
\(q_1\)	\(\lambda , \, S, \, q_1\)	\(X, \, L, \, q_1\)

\(\ldots\)	\(\lambda\)	\(\lambda\)	\(Z\)	\(Z\)	\(Z\)	\(Z\)	\(\lambda\)	\(\lambda\)	\(\ldots\)
								\(\blacktriangle q_0\)

\(\ldots\)	\(\lambda\)	\(\lambda\)	\(X\)	\(X\)	\(X\)	\(X\)	\(\lambda\)	\(\lambda\)	\(\ldots\)
		\(\blacktriangle q_0\)

	\(\lambda\)	\(2\)	\(3\)	\(X\)
\(q_0\)	\(\lambda , \, R, \, q_0\)
\(q_1\)	\(\lambda , \, S, \, q_1\)	\(3 , \, R, \, q_1\)	\(X , \, R, \, q_1\)	\(2, \, R, \, q_1\)