Карточки
Тесты
Главная
Курсы
Куратор
Подписка
12. Выполнение алгоритмов для исполнителей: все задания
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (19) ИЛИ нашлось (399) ИЛИ нашлось (999)
ЕСЛИ нашлось (19)
ТО заменить (19, 9)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (399)
ТО заменить (399, 91)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (999)
ТО заменить (999, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с цифры «$1$», а затем содержащая $n$ цифр «$9$» ($3 < n < 10000$). Определите наименьшее значение $n$, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $33$.
Аналитически такие задачи почти не решаются: замены накладываются друг на друга, длина строки то растёт, то падает, и простой зависимости результата от $n$ нет. Достаточно взглянуть на первые значения: при $n = 4$ получается $39$, при $n = 5$ — $91$, при $n = 7$ — просто $3$, при $n = 14$ — $99139$. Поэтому задание решается перебором с точным моделированием программы.
Моделировать надо буквально, шаг за шагом. Тело цикла содержит три независимых условных оператора, которые выполняются последовательно, а не как выбор одного из трёх. То есть за один проход цикла может сработать сразу несколько замен: сначала проверяется и при необходимости выполняется замена $19 \to 9$, затем на уже изменённой строке — замена $399 \to 91$, и только потом $999 \to 3$. Каждая команда заменяет одно, самое левое вхождение — в Python это в точности s.replace(v, w, 1).
Перебираем $n$ начиная с $4$ и для каждого считаем сумму цифр результата. Первое совпадение с $33$ даёт ответ.
def run(s):
while '19' in s or '399' in s or '999' in s:
if '19' in s:
s = s.replace('19', '9', 1) # только первое вхождение
if '399' in s:
s = s.replace('399', '91', 1)
if '999' in s:
s = s.replace('999', '3', 1)
return s
for n in range(4, 10000):
s = run('1' + '9' * n)
if sum(map(int, s)) == 33:
print(n, s) # 46 9911391
break
Проверка. При $n = 46$ программа оставляет строку $9911391$, сумма её цифр равна $9+9+1+1+3+9+1 = 33$. Соседние значения не подходят: при $n = 44$ остаётся $991133$ с суммой $26$, при $n = 45$ — $9911339$ с суммой $35$, при $n = 47$ — всего лишь $31$ с суммой $4$.
20
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A = {a_0, a_1, \ldots, a_{n-1}}$), включая специальный пустой символ $a_0$.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q = {q_0, q_1, \ldots, q_{n-1}}$. В начальный момент времени головка находится в начальном состоянии $q_0$.
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, и/или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
| $a_0$ | $a_1$ | … | $a_{n-1}$ | |
|---|---|---|---|---|
| $q_0$ | команда | команда | … | команда |
| $q_1$ | команда | команда | … | команда |
| … | … | … | … | … |
| $q_{n-1}$ | команда | команда | … | команда |
Программа
| $\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».
Возможное начальное состояние исполнителя:
| … | $\lambda$ | $\lambda$ | Z | Z | Z | Z | $\lambda$ | $\lambda$ | … |
|---|
Головка в состоянии $q_0$ стоит на восьмой ячейке.
Конечное состояние исполнителя после завершения выполнения программы:
| … | $\lambda$ | $\lambda$ | X | X | X | X | $\lambda$ | $\lambda$ | … |
|---|
Головка в состоянии $q_1$ стоит на второй ячейке.
На ленте в соседних ячейках записана последовательность из $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$ нуля. Определите максимально возможное число нулей в исходной последовательности.
Разберём, что делает программа. Головка стоит справа от последовательности на пустом символе, состояние $q_0$. Единственная заполненная клетка для $q_0$ — столбец «$\lambda$»: головка ничего не меняет, сдвигается влево и переходит в $q_1$. Теперь она стоит на самом правом символе последовательности.
Дальше вся работа идёт в состоянии $q_1$, и вариантов три. Если под головкой ноль, он заменяется на единицу, и головка сдвигается влево. Если под головкой единица, она заменяется на ноль и исполнитель останавливается. Если под головкой пустой символ, исполнитель тоже останавливается.
Значит программа идёт от правого края влево, переворачивая нули в единицы, пока не встретит первую единицу — превращает её в ноль и останавливается. Обозначим через $k$ количество нулей в хвосте справа, то есть до этой первой единицы.
Посчитаем баланс нулей. Из хвоста ушло $k$ нулей, зато встреченная единица стала нулём — прибавился один. Если исходно нулей было $Z$, то после работы их стало $Z — k + 1$. По условию это $343$, откуда $Z = 342 + k$.
Чтобы получить максимум нулей, надо взять как можно большее $k$. Но в последовательности должна быть хотя бы одна единица — иначе исполнитель дойдёт до пустого символа, все нули превратятся в единицы, и на ленте останется ноль нулей, что условию не удовлетворяет. Значит нулей не больше $999$, то есть $Z = 342 + k \le 999$, откуда $k \le 657$.
Возьмём $k = 657$. Тогда $Z = 342 + 657 = 999$: единственная единица стоит на $343$-й позиции, слева от неё $342$ нуля, справа $657$ нулей. После работы программы правые $657$ нулей станут единицами, а единица на $343$-й позиции станет нулём. Нулей останется $342 + 1 = 343$, что и требуется.
Проверим моделированием на языке Python.
def run(seq):
tape = list(seq)
pos = len(seq) # ячейка справа от последовательности
st = 'q0'
while True:
c = tape[pos] if 0 <= pos < len(tape) else 'L' # 'L' — символ лямбда
if st == 'q0':
if c == 'L':
pos -= 1
st = 'q1'
else:
break
else:
if c == 'L':
break # остановка
if c == '1':
tape[pos] = '0'
break # остановка
tape[pos] = '1' # был ноль
pos -= 1
return ''.join(tape)
seq = '0'*342 + '1' + '0'*657
print(seq.count('0'), run(seq).count('0')) # 999 343
Программа подтверждает: в исходной последовательности $999$ нулей, после выполнения остаётся ровно $343$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $81$ идущей подряд цифры $1$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (88888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ заменить (88888, 888)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Обратите внимание на устройство тела цикла: здесь не три независимых оператора, а один с ветвью ИНАЧЕ. За один проход выполняется ровно одна замена. Пока в строке есть цепочка $1111$, работает только первая ветка; вторая включается лишь тогда, когда четвёрок единиц не осталось.
Первая фаза. Строка из $81$ единицы. Каждый шаг превращает $1111$ в $888$: единиц становится на четыре меньше, восьмёрок на три больше. Поскольку $81 = 4 \cdot 20 + 1$, замена сработает $20$ раз, после чего останется одна единица, а слева от неё накопится $60$ восьмёрок. Получается строка из $60$ восьмёрок и одной единицы в конце.
Вторая фаза. Четвёрок единиц больше нет, поэтому включается вторая ветка: $88888 \to 888$, то есть восьмёрок каждый раз становится на две меньше. Из $60$ восьмёрок так можно дойти до $4$: замена работает, пока восьмёрок хотя бы пять. Убавляем по две: $60, 58, 56, \ldots, 6, 4$. На $4$ восьмёрках цепочка $88888$ уже не находится, а $1111$ отсутствует с самого начала второй фазы, поэтому цикл завершается.
Итого в строке остаются $4$ восьмёрки и одна единица: $88881$. Всего цикл отработал $20 + 28 = 48$ раз.
def run(s):
while '1111' in s or '88888' in s:
if '1111' in s:
s = s.replace('1111', '888', 1) # только первое вхождение
else:
s = s.replace('88888', '888', 1)
return s
print(run('1' * 81)) # 88881
Проверка на малых значениях подтверждает логику: строка из $8$ единиц даёт $8888$, из $13$ единиц — $8881$, из $9$ единиц — $88881$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
ЕСЛИ нашлось (25)
ТО заменить (25, 5)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (355)
ТО заменить (355, 52)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦНа вход приведённой выше программе поступает строка, начинающаяся с цифры «$2$», а затем содержащая $n$ цифр «$5$» ($n > 3$). Определите наименьшее значение $n$, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $17$.
Аналитически такие задачи почти не решаются: замены накладываются друг на друга, длина строки то растёт, то падает, и простой зависимости результата от $n$ нет. Достаточно взглянуть на первые значения: при $n = 4$ получается $35$, при $n = 5$ — $52$, при $n = 7$ — просто $3$, при $n = 14$ — $55235$. Поэтому задание решается перебором с точным моделированием программы.
Моделировать надо буквально, шаг за шагом. Тело цикла содержит три независимых условных оператора, которые выполняются последовательно, а не как выбор одного из трёх. То есть за один проход цикла может сработать сразу несколько замен: сначала проверяется и при необходимости выполняется замена $25 \to 5$, затем на уже изменённой строке — замена $355 \to 52$, и только потом $555 \to 3$. Каждая команда заменяет одно, самое левое вхождение — в Python это в точности s.replace(v, w, 1).
Перебираем $n$ начиная с $4$ и для каждого считаем сумму цифр результата. Первое совпадение с $17$ даёт ответ.
def run(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', '52', 1)
if '555' in s:
s = s.replace('555', '3', 1)
return s
n = 4
while True:
s = run('2' + '5' * n)
if sum(map(int, s)) == 17:
print(n, s) # 29 52235
break
n += 1
Проверка. При $n = 29$ программа оставляет строку $52235$, сумма её цифр равна $5+2+2+3+5 = 17$. Соседние значения не подходят: при $n = 27$ остаётся просто $3$ с суммой $3$, при $n = 28$ — $5223$ с суммой $12$, при $n = 30$ — $552$ с суммой $12$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $132$ идущих подряд цифр $9$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (22222) ИЛИ нашлось (9999)
ЕСЛИ нашлось (22222)
ТО заменить (22222, 99)
ИНАЧЕ заменить (9999, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦОбратите внимание на устройство тела цикла: здесь один оператор с ветвью ИНАЧЕ, а не два независимых. За один проход выполняется ровно одна замена, причём приоритет у первой ветки: пока в строке есть $22222$, работает только она.
Начинаем со $132$ девяток. Пятёрок двоек пока нет, поэтому раз за разом срабатывает вторая ветка: $9999 \to 2$. Каждая такая замена съедает четыре девятки и добавляет одну двойку слева от остатка. Двойки накапливаются в начале строки.
Как только двоек станет пять, включится первая ветка и превратит $22222$ в $99$ — то есть пять двоек снова свернутся в две девятки, которые допишутся к оставшемуся хвосту. Потом снова копятся двойки, и так далее.
Проследим за концовкой. К $38$-му шагу строка имеет вид $229999999999999999$ — две двойки и $16$ девяток. Дальше подряд идут три замены $9999 \to 2$: получаем $222999999999999$, затем $222299999999$ и затем $222229999$. Теперь двоек ровно пять, срабатывает первая ветка: $22222 \to 99$, и остаётся $999999$. Здесь ещё находится $9999$, последняя замена даёт $299$. В этой строке нет ни $22222$, ни $9999$, цикл завершается. Всего программа отработала $43$ шага.
def run(s):
while '22222' in s or '9999' in s:
if '22222' in s:
s = s.replace('22222', '99', 1) # только первое вхождение
else:
s = s.replace('9999', '2', 1)
return s
print(run('9' * 132)) # 299
Проверка на малых значениях подтверждает логику: из $4$ девяток получается $2$, из $8$ — $22$, из $9$ — $229$, из $13$ — $2229$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $100$ идущих подряд цифр $9$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (33333) ИЛИ нашлось (999)
ЕСЛИ нашлось (33333)
ТО заменить (33333, 99)
ИНАЧЕ заменить (999, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦОбратите внимание на устройство тела цикла: здесь один оператор с ветвью ИНАЧЕ, а не два независимых. За один проход выполняется ровно одна замена, причём приоритет у первой ветки: пока в строке есть $33333$, работает только она.
Начинаем со $100$ девяток. Пятёрок троек пока нет, поэтому раз за разом срабатывает вторая ветка: $999 \to 3$. Каждая такая замена съедает три девятки и добавляет одну тройку слева от остатка, так что тройки накапливаются в начале строки. Как только их станет пять, включится первая ветка и превратит $33333$ в $99$ — пять троек свернутся в две девятки, которые допишутся к оставшемуся хвосту. Потом снова копятся тройки, и так далее.
Проследим за концовкой. К $40$-му шагу строка имеет вид $33339999999999$ — четыре тройки и $10$ девяток. Следующая замена $999 \to 3$ даёт $333339999999$: троек стало пять, и срабатывает первая ветка, превращая их в две девятки — получается $999999999$, девять девяток. Дальше три замены подряд по второй ветке: $3999999$, затем $33999$, затем $333$. В строке $333$ нет ни $33333$, ни $999$, поэтому цикл завершается. Всего программа отработала $45$ шагов.
def run(s):
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)
return s
print(run('9' * 100)) # 333
Проверка на малых значениях подтверждает логику: из $3$ девяток получается $3$, из $6$ — $33$, из $9$ — $333$, из $15$ — $99$.
20
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов $A = {a_0, a_1, \ldots, a_{n-1}}$), включая специальный пустой символ $a_0$.
Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний $Q = {q_0, q_1, \ldots, q_{n-1}}$. В начальный момент времени головка находится в начальном состоянии $q_0$.
На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может изменить символ в текущей ячейке и переместиться в соседнюю ячейку слева или справа от неё. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии.
Программа работы исполнителя МТ задаётся в табличном виде.
| $a_0$ | $a_1$ | … | $a_{n-1}$ | |
|---|---|---|---|---|
| $q_0$ | команда | команда | … | команда |
| $q_1$ | команда | команда | … | команда |
| … | … | … | … | … |
| $q_{n-1}$ | команда | команда | … | команда |
Программа
| $\lambda$ | Z | |
|---|---|---|
| $q_0$ | $\lambda$, L, $q_0$ | X, L, $q_1$ |
| $q_1$ | $\lambda$, L, $q_1$ | X, L, $q_2$ |
| $q_2$ | $\lambda$, S, $q_2$ | X, L, $q_2$ |
заменяет на ленте все символы «Z» на «X» и останавливает исполнителя в первой ячейке слева от последовательности символов «X».
На ленте в соседних ячейках записано двоичное представление числа $2027$ без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «$\lambda$». В начальный момент времени головка расположена в ближайшей справа к последовательности ячейке.
Программа работы исполнителя:
| $\lambda$ | $0$ | $1$ | |
|---|---|---|---|
| $q_0$ | $\lambda$, L, $q_1$ | ||
| $q_1$ | $1$, L, $q_2$ | $0$, L, $q_1$ | $1$, L, $q_1$ |
| $q_2$ | $\lambda$, S, $q_2$ |
Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.
Разберём, что делает программа. Головка стоит справа от числа на пустом символе, состояние $q_0$. Единственная заполненная клетка для $q_0$ — столбец «$\lambda$»: символ не меняется, головка сдвигается влево и переходит в $q_1$. Теперь она стоит на младшем разряде числа.
В состоянии $q_1$ обе цифровые команды устроены одинаково: символ записывается тот же самый, головка сдвигается влево, состояние остаётся $q_1$. То есть машина просто пробегает всё число справа налево, ничего не меняя.
Когда головка выходит за левый край числа и видит пустой символ, срабатывает команда $1$, L, $q_2$: в эту ячейку записывается единица, головка сдвигается влево и переходит в $q_2$. Там она видит пустой символ и останавливается.
Итог: программа приписывает единицу слева от двоичной записи числа. Никакие цифры самого числа не меняются.
Переведём $2027$ в двоичную систему. $2027 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 + 1$, то есть $2027_{10} = 11111101011_2$. В записи $11$ разрядов.
Приписываем слева единицу: получается $111111101011_2$. Новая единица встала в разряд $2^{11} = 2048$, все остальные разряды сохранились, поэтому результат равен $2048 + 2027 = 4075$.
s = bin(2027)[2:] # 11111101011
r = '1' + s # приписываем единицу слева
print(r, int(r, 2)) # 111111101011 4075Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (39) ИЛИ нашлось (999) ИЛИ нашлось (7777)
ЕСЛИ нашлось (39)
ТО заменить (39, 3)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (999)
ТО заменить (999, 7)
ИНАЧЕ заменить (7777, 9)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦНа вход приведённой выше программе поступает строка, начинающаяся с цифры «$3$», а затем содержащая $n$ цифр «$9$» ($3 < n < 10000$). Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.
Обратите внимание на структуру тела цикла: здесь два оператора, причём второй с ветвью ИНАЧЕ. За один проход сначала при наличии $39$ выполняется замена $39 \to 3$, а затем независимо от этого срабатывает второй оператор: либо $999 \to 7$, либо, если тройки девяток нет, $7777 \to 9$.
Аналитически предсказать результат тяжело, поэтому моделируем программу и перебираем $n$. Достаточно посмотреть на первые значения, чтобы увидеть закономерность: результат зависит только от остатка $n$ при делении на $12$.
При $n = 4$ получается $37$ (сумма $10$), при $n = 5$ — $379$ (сумма $19$), при $n = 9$ — $37799$ (сумма $35$), при $n = 12$ — $377799$ (сумма $42$), а при $n = 13$, $14$, $15$ остаётся просто $3$ с суммой $3$. Дальше картина повторяется: $n = 16$ даёт то же, что $n = 4$, $n = 24$ — то же, что $n = 12$, и так далее.
Максимум внутри периода достигается при $n$, кратном $12$: результат $377799$, сумма цифр $3+7+7+7+9+9 = 42$. Поскольку период равен $12$, а диапазон $3 < n < 10000$ содержит множество кратных двенадцати (например, $n = 9996$), это значение действительно достижимо и является наибольшим.
def run(s):
while '39' in s or '999' in s or '7777' in s:
if '39' in s:
s = s.replace('39', '3', 1) # только первое вхождение
if '999' in s:
s = s.replace('999', '7', 1)
else:
s = s.replace('7777', '9', 1)
return s
print(max(sum(map(int, run('3' + '9'*n))) for n in range(4, 10000))) # 42
Проверка: при $n = 9996$ программа тоже оставляет строку $377799$ с суммой цифр $42$.
20
Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.
На вход приведённой ниже программе поступает строка, начинающаяся с символа «$>$», а затем содержащая $11$ цифр $1$, $12$ цифр $2$ и $30$ цифр $3$, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
Так, например, если результат работы программы представлял бы собой строку, состоящую из $50$ цифр $4$, то верным ответом было бы число $200$.
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
ЕСЛИ нашлось (>1)
ТО заменить (>1, 22>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>2)
ТО заменить (>2, 2>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>3)
ТО заменить (>3, 1>)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКлюч к задаче — понять роль символа «$>$». Во всех трёх заменах он стоит слева от цифры, а в результате оказывается справа от неё. Значит «$>$» работает как каретка, которая ползёт по строке слева направо и обрабатывает очередную цифру, а всё уже обработанное остаётся позади и больше не меняется.
Что происходит с каждой цифрой при проходе каретки:
- цифра $1$ превращается в $22$;
- цифра $2$ остаётся цифрой $2$;
- цифра $3$ превращается в $1$.
Цикл завершается, когда каретка дойдёт до конца строки — тогда справа от «$>$» ничего нет и ни одно из условий не выполняется.
Отсюда видно, что порядок цифр в исходной строке вообще не важен: каждая цифра обрабатывается независимо, и суммарный вклад определяется только количествами. Считаем сумму по типам цифр.
Каждая из $11$ единиц даёт $22$, то есть вклад $2 + 2 = 4$: всего $11 \cdot 4 = 44$.
Каждая из $12$ двоек даёт $2$: всего $12 \cdot 2 = 24$.
Каждая из $30$ троек даёт $1$: всего $30 \cdot 1 = 30$.
Итоговая сумма равна $44 + 24 + 30 = 98$.
import random
def run(s):
while '>1' in s or '>2' in s or '>3' in s:
if '>1' in s:
s = s.replace('>1', '22>', 1) # только первое вхождение
if '>2' in s:
s = s.replace('>2', '2>', 1)
if '>3' in s:
s = s.replace('>3', '1>', 1)
return s
d = list('1'*11 + '2'*12 + '3'*30)
random.shuffle(d) # порядок произвольный
r = run('>' + ''.join(d))
print(sum(int(c) for c in r if c.isdigit())) # 98При разных перемешиваниях исходной строки программа всегда даёт $98$, что подтверждает независимость результата от порядка цифр.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (72) ИЛИ нашлось (522) ИЛИ нашлось (2222)
ЕСЛИ нашлось (72)
ТО заменить (72, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (522)
ТО заменить (522, 27)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (2222)
ТО заменить (2222, 5)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦНа вход приведённой выше программе поступает строка, начинающаяся с цифры «$5$», а затем содержащая $n$ цифр «$2$» ($3 < n < 10000$). Определите наименьшее значение $n$, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна $66$.
Аналитически такие задачи почти не решаются: замены накладываются друг на друга, длина строки то растёт, то падает, и простой зависимости результата от $n$ нет. Достаточно взглянуть на первые значения: при $n = 4$ получается $222$ с суммой $6$, при $n = 5$ — просто $5$, при $n = 6$ — $275$ с суммой $14$, при $n = 19$ — $222752$ с суммой $20$. Поэтому задание решается перебором с точным моделированием программы.
Моделировать надо буквально, шаг за шагом. Тело цикла содержит три независимых условных оператора, которые выполняются последовательно, а не как выбор одного из трёх. То есть за один проход цикла может сработать сразу несколько замен: сначала проверяется и при необходимости выполняется замена $72 \to 2$, затем на уже изменённой строке — замена $522 \to 27$, и только потом $2222 \to 5$. Каждая команда заменяет одно, самое левое вхождение — в Python это в точности s.replace(v, w, 1).
Перебираем $n$ начиная с $4$ и для каждого считаем сумму цифр результата. Первое совпадение с $66$ даёт ответ. Заметьте, что искомое $n$ оказывается довольно большим: суммы растут медленно и очень неровно, до $n = 400$ значение $66$ ни разу не встречается.
def run(s):
while '72' in s or '522' in s or '2222' in s:
if '72' in s:
s = s.replace('72', '2', 1) # только первое вхождение
if '522' in s:
s = s.replace('522', '27', 1)
if '2222' in s:
s = s.replace('2222', '5', 1)
return s
for n in range(4, 10000):
s = run('5' + '2' * n)
if sum(map(int, s)) == 66:
print(n, s) # 484 5775275275275
break
Проверка. При $n = 484$ программа оставляет строку $5775275275275$, сумма её цифр равна $5+7+7+5+2+7+5+2+7+5+2+7+5 = 66$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $82$ идущих подряд цифр $1$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось (11111)
ТО заменить (11111, 88)
ИНАЧЕ
ЕСЛИ нашлось (888)
ТО заменить (888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦОбратите внимание на устройство тела цикла: здесь вложенная конструкция, а не два независимых оператора. За один проход выполняется ровно одна замена, причём приоритет у первой ветки: пока в строке есть $11111$, вторая ветка не работает вовсе.
Первая фаза. Строка из $82$ единиц. Каждый шаг превращает $11111$ в $88$: единиц становится на пять меньше, восьмёрок на две больше. Поскольку $82 = 5 \cdot 16 + 2$, замена сработает $16$ раз, после чего останутся две единицы, а слева накопится $32$ восьмёрки. Получается строка из $32$ восьмёрок и двух единиц в конце.
Вторая фаза. Пятёрок единиц больше нет, поэтому включается вторая ветка: $888 \to 8$, то есть восьмёрок каждый раз становится на две меньше. Из $32$ восьмёрок так можно дойти до $2$: замена работает, пока восьмёрок хотя бы три. Убавляем по две: $32, 30, 28, \ldots, 4, 2$. На двух восьмёрках цепочка $888$ уже не находится, и цикл завершается.
Хвост из двух единиц всё это время остаётся нетронутым: пять единиц подряд там никогда не наберётся. Итого в строке остаются $2$ восьмёрки и $2$ единицы: $8811$. Всего цикл отработал $16 + 15 = 31$ шаг.
def run(s):
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)
return s
print(run('1' * 82)) # 8811
Проверка на малых значениях подтверждает логику: строка из $5$ единиц даёт $88$, из $6$ — $881$, из $10$ — $88$, из $11$ — $881$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (42) ИЛИ нашлось (322) ИЛИ нашлось (2222)
ЕСЛИ нашлось (42)
ТО заменить (42, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (322)
ТО заменить (322, 24)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (2222)
ТО заменить (2222, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦНа вход приведённой выше программе поступает строка, начинающаяся с цифры «$4$», а затем содержащая $n$ цифр «$2$» ($3 < n < 2000$). Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.
Здесь три независимых оператора ЕСЛИ, а не вложенная конструкция. Значит, за один проход тела цикла выполняется до трёх замен подряд, строго в записанном порядке: сначала $42 \to 2$, потом $322 \to 24$, потом $2222 \to 3$, причём каждая работает уже с той строкой, которую оставила предыдущая.
Как замены влияют на сумму цифр: $42 \to 2$ уменьшает её на $4$, $322 \to 24$ — на $1$, $2222 \to 3$ — на $5$. Начальная сумма равна $4 + 2n$, и она только убывает, поэтому «выгодны» те $n$, при которых цикл завершается быстро и оставляет много четвёрок и троек.
Посмотрим на первый проход. Строка $4\underbrace{22\ldots2}{n}$: команда $42 \to 2$ даёт $n$ двоек, цепочки $322$ нет, а $2222 \to 3$ превращает начало в тройку, и получается $3\underbrace{22\ldots2}{n-4}$. Дальше цепочка $322$ начинает «производить» четвёрки ($322 \to 24$), цепочка $2222$ — тройки, а $42 \to 2$ эти четвёрки уничтожает. Три правила гоняют строку туда-обратно, и результат оказывается крайне неустойчивым по $n$: например, при $n = 49$ остаётся $3$ (сумма $3$), а при $n = 50$ — строка $2443243$ (сумма $22$). Никакой простой периодичности здесь нет, поэтому единственный надёжный путь — перебрать все допустимые $n$ и взять максимум.
def run(s):
while '42' in s or '322' in s or '2222' in s:
if '42' in s:
s = s.replace('42', '2', 1) # только первое вхождение
if '322' in s:
s = s.replace('322', '24', 1)
if '2222' in s:
s = s.replace('2222', '3', 1)
return s
best = max((sum(map(int, run('4' + '2' * n))), n) for n in range(4, 2000))
print(best) # (113, 1603)
Обратите внимание на две типичные ошибки: замена должна быть только первого вхождения (третий аргумент $1$ у replace), а три условия внутри цикла проверяются последовательно и независимо — если написать их через elif, ответ получится другим.
Максимум достигается при $n = 1603$: программа делает $321$ проход цикла и оставляет строку из $34$ цифр $$2444444333324443244443244324432432,$$ сумма цифр которой равна $113$ (начальная сумма была $4 + 2 \cdot 1603 = 3210$). Ближайшие конкуренты заметно меньше: $111$ при $n = 1602$ и $108$ при $n = 1598$.
20
Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $125$ идущих подряд цифр $3$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (999) ИЛИ нашлось (333)
ЕСЛИ нашлось (999)
ТО заменить (999, 3)
ИНАЧЕ заменить (333, 9)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦЗдесь одна конструкция ЕСЛИ–ИНАЧЕ, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $999$: пока в строке есть три девятки подряд, тройки не трогаются вовсе.
Проследим за строкой из одних троек. Пока девяток мало, работает ветка ИНАЧЕ: $333 \to 9$, причём заменяется самое левое вхождение, поэтому девятки копятся в начале строки. Три таких шага дают $999$ и на $9$ троек меньше. Как только девятки набралось три, срабатывает первая ветка: $999 \to 3$, и строка снова становится состоящей из одних троек.
Итого за четыре шага цикл возвращается к исходному виду, но троек стало на $8$ меньше: $9$ израсходовано, $1$ вернулась из $999 \to 3$. Так строка из $m$ троек превращается в строку из $m — 8$ троек, пока троек хватает на все четыре шага.
Начинаем со $125$ троек и вычитаем по $8$. Поскольку $125 = 8 \cdot 15 + 5$, после $15$ таких циклов остаётся ровно $5$ троек.
Разбираем остаток вручную. Строка $33333$: девяток нет, поэтому $333 \to 9$, получается $933$. Теперь ни $999$, ни $333$ в строке нет, условие цикла ложно, программа останавливается. Всего цикл сделал $15 \cdot 4 + 1 = 61$ шаг.
Ключевой момент — именно остаток от деления на $8$. Полезно помнить таблицу для остатков: $m \equiv 1 \to 3$, $2 \to 33$, $3 \to 9$, $4 \to 93$, $5 \to 933$, $6 \to 99$, $7 \to 993$, $0 \to 9933$.
def run(s):
while '999' in s or '333' in s:
if '999' in s:
s = s.replace('999', '3', 1) # только первое вхождение
else:
s = s.replace('333', '9', 1)
return s
print(run('3' * 125)) # 933Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке $\underbrace{100\ldots00}_{80}$, т.е. к строке, состоящей из единицы, за которой следуют $80$ нулей подряд. В ответе запишите только количество нулей в получившейся строке.
НАЧАЛО
ПОКА нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 0001)
ИНАЧЕ заменить (1, 00)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦЕдиница в строке всё время ровно одна: обе замены её сохраняют ($10 \to 0001$) либо уничтожают ($1 \to 00$), а появиться новой неоткуда. Поэтому достаточно следить за тем, сколько нулей стоит справа от единицы.
Основная ветка. Пока справа от единицы есть хотя бы один нуль, цепочка $10$ находится, и работает замена $10 \to 0001$. Что она делает: убирает один нуль справа от единицы и дописывает три нуля слева от неё. Единица как бы сдвигается вправо через строку, оставляя за собой по три нуля вместо одного.
Баланс нулей за такой шаг: $-1$ справа и $+3$ слева, то есть общее количество нулей растёт на $2$.
Сколько таких шагов. Справа от единицы изначально $80$ нулей, и каждый шаг съедает ровно один, поэтому замена $10 \to 0001$ сработает $80$ раз. К этому моменту нулей станет $80 + 2 \cdot 80 = 240$, а единица окажется последним символом строки.
Завершающий шаг. Теперь цепочки $10$ нет, но единица есть, поэтому срабатывает ветка ИНАЧЕ: $1 \to 00$, что добавляет ещё $2$ нуля. Единиц в строке не остаётся, условие цикла становится ложным, и программа завершается. Всего цикл отработал $81$ шаг.
Итого нулей: $240 + 2 = 242$ (и это вся длина строки, поскольку единицы в ней больше нет).
Общая формула для $k$ нулей на входе: $3k + 2$. Проверка на малых значениях: при $k = 1$ получается $5$, при $k = 2$ — $8$, при $k = 3$ — $11$; при $k = 80$ имеем $3 \cdot 80 + 2 = 242$.
def run(s):
while '1' in s:
if '10' in s:
s = s.replace('10', '0001', 1) # только первое вхождение
else:
s = s.replace('1', '00', 1)
return s
print(run('1' + '0' * 80).count('0')) # 242Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $82$ идущих подряд цифр $1$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (1111) ИЛИ нашлось (8888)
ЕСЛИ нашлось (1111)
ТО заменить (1111, 888)
ИНАЧЕ
ЕСЛИ нашлось (8888)
ТО заменить (8888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКонструкция вложенная, поэтому за один проход цикла выполняется ровно одна замена, и у первой ветки абсолютный приоритет: пока в строке есть $1111$, вторая ветка не работает.
Первая фаза. Строка из $82$ единиц. Каждый шаг превращает $1111$ в $888$: единиц становится на четыре меньше, восьмёрок на три больше, причём восьмёрки копятся слева, а единицы остаются справа. Так как $82 = 4 \cdot 20 + 2$, замена сработает $20$ раз, после чего останется хвост из двух единиц, а слева накопится $3 \cdot 20 = 60$ восьмёрок. Строка принимает вид из $60$ восьмёрок и двух единиц.
Вторая фаза. Четырёх единиц подряд больше нет, включается вторая ветка: $8888 \to 8$, то есть восьмёрок каждый раз становится на три меньше. Замена работает, пока восьмёрок не меньше четырёх. Убавляем по три: $60, 57, 54, \ldots, 6, 3$. Поскольку $60$ делится на $3$, процесс упирается ровно в $3$ восьмёрки, на которых цепочка $8888$ уже не находится, и цикл завершается. Это $\frac{60 — 3}{3} = 19$ шагов.
Хвост из двух единиц всё это время не трогается: четыре единицы подряд там никогда не наберутся. Итого остаются $3$ восьмёрки и $2$ единицы: $88811$. Всего цикл отработал $20 + 19 = 39$ шагов.
def run(s):
while '1111' in s or '8888' in s:
if '1111' in s:
s = s.replace('1111', '888', 1) # только первое вхождение
else:
s = s.replace('8888', '8', 1)
return s
print(run('1' * 82)) # 88811
Проверка на малых значениях подтверждает логику: строка из $4$ единиц даёт $888$, из $5$ — $8881$, из $6$ — $88811$, из $8$ — $888$.
20
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $80$ идущих подряд цифр $1$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
ЕСЛИ нашлось (11111)
ТО заменить (11111, 88)
ИНАЧЕ
ЕСЛИ нашлось (888)
ТО заменить (888, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКонструкция вложенная, поэтому за один проход цикла выполняется ровно одна замена, и приоритет у первой ветки: пока в строке есть $11111$, вторая ветка не работает вовсе.
Первая фаза. Строка из $80$ единиц. Каждый шаг превращает $11111$ в $88$: единиц становится на пять меньше, восьмёрок на две больше, причём восьмёрки копятся слева. Число $80$ делится на $5$ нацело: $80 = 5 \cdot 16$, поэтому замена сработает $16$ раз и единицы закончатся полностью — никакого хвоста не остаётся. В строке будет $2 \cdot 16 = 32$ восьмёрки.
Вторая фаза. Теперь работает вторая ветка: $888 \to 8$, то есть восьмёрок каждый раз становится на две меньше. Замена возможна, пока восьмёрок хотя бы три. Убавляем по две от чётного числа $32$: $32, 30, 28, \ldots, 4, 2$. На двух восьмёрках цепочка $888$ уже не находится, и цикл завершается. Это $\frac{32 — 2}{2} = 15$ шагов.
Итого в строке остаются $2$ восьмёрки: $88$. Всего цикл отработал $16 + 15 = 31$ шаг.
Обратите внимание: ответ определяется остатком от деления на $5$ (сколько единиц останется в хвосте) и чётностью числа восьмёрок. Здесь $80$ кратно $5$, поэтому хвоста нет, а $32$ чётно, поэтому дело доходит ровно до двух восьмёрок.
def run(s):
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)
return s
print(run('1' * 80)) # 88
Проверка: строки из 5, 10, 15, 20 единиц тоже дают 88Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.
А) заменить ($v$, $w$). Эта команда заменяет в строке первое слева вхождение цепочки $v$ на цепочку $w$. Например, выполнение команды заменить ($111$, $27$) преобразует строку $05111150$ в строку $0527150$. Если в строке нет вхождений цепочки $v$, то выполнение команды заменить ($v$, $w$) не меняет эту строку.
Б) нашлось ($v$). Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
На вход приведённой ниже программе поступает строка, начинающаяся с символа «$>$», а затем содержащая $10$ цифр $1$, $20$ цифр $2$ и $30$ цифр $3$, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
Так, например, если результат работы программы представлял бы собой строку, состоящую из $50$ цифр $4$, то верным ответом было бы число $200$.
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
ЕСЛИ нашлось (>1)
ТО заменить (>1, 22>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>2)
ТО заменить (>2, 2>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>3)
ТО заменить (>3, 1>)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКлючевая идея: символ «$>$» в строке ровно один, и все три замены устроены одинаково — они забирают цифру, стоящую справа от маркера, дописывают что-то слева от него и передвигают сам маркер на одну цифру вправо. Символ «$>$» работает как курсор, который проезжает по строке слева направо ровно один раз.
Что важно: всё, что маркер уже произвёл, остаётся слева от него и больше никогда не проверяется — шаблоны $>1$, $>2$, $>3$ требуют маркер перед цифрой. Значит, обработанные цифры не участвуют в дальнейших заменах, и повторных проходов не будет. Цикл закончится, когда маркер дойдёт до конца строки, — цифр справа от него не останется, все три условия станут ложными.
То, что операторов ЕСЛИ три и они независимы, здесь ничего не меняет: за один проход маркер просто успевает съесть до трёх цифр подряд. На итог это не влияет, важен только вклад каждой исходной цифры.
Теперь считаем вклад по каждой цифре, независимо от порядка их следования: цифра $1$ превращается в $22$ и даёт $4$; цифра $2$ превращается в $2$ и даёт $2$; цифра $3$ превращается в $1$ и даёт $1$.
Отсюда сумма цифр итоговой строки: $$10 \cdot 4 + 20 \cdot 2 + 30 \cdot 1 = 40 + 40 + 30 = 110.$$
Сам маркер «$>$» остаётся в конце строки, но он не цифра и в сумму не входит.
import random
def run(s):
while '>1' in s or '>2' in s or '>3' in s:
if '>1' in s: s = s.replace('>1', '22>', 1)
if '>2' in s: s = s.replace('>2', '2>', 1)
if '>3' in s: s = s.replace('>3', '1>', 1)
return s
d = list('1' * 10 + '2' * 20 + '3' * 30)
random.shuffle(d) # порядок цифр произвольный
r = run('>' + ''.join(d))
print(sum(int(c) for c in r if c.isdigit())) # 110 при любом порядкеИсполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из $104$ идущих подряд цифр $9$? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (22222) ИЛИ нашлось (9999)
ЕСЛИ нашлось (22222)
ТО заменить (22222, 99)
ИНАЧЕ заменить (9999, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКонструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $22222$: как только пять двоек набралось, они тут же схлопываются, и до девяток очередь не доходит.
Проследим за строкой из одних девяток. Пока двоек меньше пяти, работает ветка ИНАЧЕ: $9999 \to 2$, причём заменяется самое левое вхождение, поэтому двойки копятся в начале строки, а девятки остаются справа сплошным блоком. Пять таких шагов дают $22222$ и уменьшают число девяток на $20$. Сразу после этого срабатывает первая ветка: $22222 \to 99$, двойки исчезают полностью, а девяток становится на $2$ больше.
Итого за шесть шагов строка снова состоит из одних девяток, но их стало на $20 — 2 = 18$ меньше. Такой цикл повторяется, пока девяток хватает на пять замен, то есть пока их не меньше $20$.
Считаем: $104 \to 86 \to 68 \to 50 \to 32 \to 14$. Это пять полных циклов ($30$ шагов), и остаются $14$ девяток.
Разбираем остаток вручную. Из $14$ девяток замена $9999 \to 2$ проходит три раза (съедает $12$ девяток) и даёт строку $22299$: три двойки слева и две девятки справа. Дальше ни $22222$ (двоек всего три), ни $9999$ (девяток всего две) в строке нет — условие цикла ложно, программа останавливается. Всего цикл отработал $30 + 3 = 33$ шага.
Обратите внимание: если бы остаток оказался равен $20$, строка свернулась бы до $99$ — полезно проверять именно остаток, а не обрывать деление наугад.
def run(s):
while '22222' in s or '9999' in s:
if '22222' in s:
s = s.replace('22222', '99', 1) # только первое вхождение
else:
s = s.replace('9999', '2', 1)
return s
print(run('9' * 104)) # 22299Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.
Б) нашлось ($v$). Эта команда проверяет, встречается ли цепочка $v$ в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
На вход приведённой ниже программы поступает строка, начинающаяся с символа «$>$», а затем содержащая $23$ цифры $1$, $11$ цифр $2$ и $15$ цифр $3$, расположенных в произвольном порядке. Определите сумму числовых значений цифр строки, получившейся в результате выполнения программы.
Так, например, если результат работы программы представлял бы собой строку, состоящую из $50$ цифр $4$, то верным ответом было бы число $200$.
НАЧАЛО
ПОКА нашлось (>1) ИЛИ нашлось (>2) ИЛИ нашлось (>3)
ЕСЛИ нашлось (>1)
ТО заменить (>1, 2>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>2)
ТО заменить (>2, 21>)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (>3)
ТО заменить (>3, 11>)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦСимвол «$>$» в строке ровно один, и все три замены устроены одинаково: маркер съедает стоящую справа от него цифру, дописывает результат слева и сдвигается на одну позицию вправо. То есть «$>$» работает как курсор, который проезжает строку слева направо ровно один раз.
Всё, что маркер уже произвёл, остаётся слева от него и больше не проверяется: шаблоны $>1$, $>2$, $>3$ требуют, чтобы маркер стоял непосредственно перед цифрой. Поэтому обработанные цифры в дальнейших заменах не участвуют, и вклад каждой исходной цифры можно посчитать отдельно. Цикл завершится, когда справа от маркера не останется цифр.
То, что операторов ЕСЛИ три и они независимы, на результат не влияет: за один проход маркер просто успевает обработать до трёх цифр подряд, но каждая цифра всё равно обрабатывается ровно один раз.
Вклад каждой цифры в сумму: цифра $1$ превращается в $2$ и даёт $2$; цифра $2$ превращается в $21$ и даёт $2 + 1 = 3$; цифра $3$ превращается в $11$ и даёт $1 + 1 = 2$.
Отсюда итоговая сумма: $$23 \cdot 2 + 11 \cdot 3 + 15 \cdot 2 = 46 + 33 + 30 = 109.$$
Порядок цифр во входной строке никакой роли не играет. Маркер «$>$» остаётся в конце строки, но он не цифра и в сумму не входит.
import random
def run(s):
while '>1' in s or '>2' in s or '>3' in s:
if '>1' in s: s = s.replace('>1', '2>', 1)
if '>2' in s: s = s.replace('>2', '21>', 1)
if '>3' in s: s = s.replace('>3', '11>', 1)
return s
d = list('1' * 23 + '2' * 11 + '3' * 15)
random.shuffle(d) # порядок цифр произвольный
r = run('>' + ''.join(d))
print(sum(int(c) for c in r if c.isdigit())) # 109 при любом порядкеИсполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки символов.
На вход приведённой ниже программы поступает строка из $150$ цифр, содержащая по $50$ цифр $1$, $2$ и $3$, расположенных в произвольном порядке.
Определите, какие цифры будут находиться на $10$-м, $80$-м и $140$-м местах строки, получившейся в результате выполнения программы. Цифры в строке нумеруются последовательно слева направо, самая левая имеет номер $1$, следующая — номер $2$ и т.д.
В ответе запишите три полученные цифры подряд без пробелов и разделителей в порядке возрастания номеров их мест в получившейся строке. Так, например, если бы на $10$-м месте стояла цифра $9$, на $80$-м — $4$, а на $140$-м — $8$, то был бы ответ $948$.
НАЧАЛО
ПОКА нашлось (21) ИЛИ нашлось (31) ИЛИ нашлось (32)
ЕСЛИ нашлось (21)
ТО заменить (21, 12)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (31)
ТО заменить (31, 13)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (32)
ТО заменить (32, 23)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦПрисмотримся к трём заменам: $21 \to 12$, $31 \to 13$, $32 \to 23$. Это в точности все пары соседних цифр, стоящих в неправильном порядке (большая слева, меньшая справа). Каждая замена меняет такую пару местами, не трогая остальные символы. Перед нами обычная сортировка обменами — по сути пузырьковая.
Из этого следуют два важных вывода. Во-первых, длина строки не меняется: в ней всегда остаются те же $150$ цифр, по $50$ штук каждого вида, меняется только их порядок. Во-вторых, условие цикла ложно ровно тогда, когда в строке не осталось ни одной «неправильной» пары соседей, то есть когда строка полностью упорядочена по неубыванию. Такое состояние достижимо всегда, и остановиться раньше программа не может.
Значит, каким бы ни был исходный порядок цифр, на выходе получится отсортированная строка: $$\underbrace{11\ldots1}{50}\underbrace{22\ldots2}{50}\underbrace{33\ldots3}_{50}.$$
Осталось расставить границы блоков. Места с $1$ по $50$ занимают единицы, места с $51$ по $100$ — двойки, места с $101$ по $150$ — тройки.
Место $10$ попадает в первый блок, значит, там стоит $1$. Место $80$ попадает во второй блок ($51 \le 80 \le 100$), значит, там стоит $2$. Место $140$ попадает в третий блок ($101 \le 140 \le 150$), значит, там стоит $3$.
Записываем цифры подряд в порядке возрастания номеров мест: $123$.
import random
def run(s):
while '21' in s or '31' in s or '32' in s:
if '21' in s: s = s.replace('21', '12', 1)
if '31' in s: s = s.replace('31', '13', 1)
if '32' in s: s = s.replace('32', '23', 1)
return s
d = list('1' * 50 + '2' * 50 + '3' * 50)
random.shuffle(d) # порядок цифр произвольный
r = run(''.join(d))
print(r[9], r[79], r[139]) # 1 2 3 при любом порядке