12. Выполнение алгоритмов для исполнителей: исполнитель

Аналитически такие задачи почти не решаются: замены накладываются друг на друга, длина строки то растёт, то падает, и простой зависимости результата от $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$.

Обратите внимание на устройство тела цикла: здесь не три независимых оператора, а один с ветвью ИНАЧЕ. За один проход выполняется ровно одна замена. Пока в строке есть цепочка $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$.

Аналитически такие задачи почти не решаются: замены накладываются друг на друга, длина строки то растёт, то падает, и простой зависимости результата от $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$.

Обратите внимание на устройство тела цикла: здесь один оператор с ветвью ИНАЧЕ, а не два независимых. За один проход выполняется ровно одна замена, причём приоритет у первой ветки: пока в строке есть $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$.

Обратите внимание на устройство тела цикла: здесь один оператор с ветвью ИНАЧЕ, а не два независимых. За один проход выполняется ровно одна замена, причём приоритет у первой ветки: пока в строке есть $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$.

Обратите внимание на структуру тела цикла: здесь два оператора, причём второй с ветвью ИНАЧЕ. За один проход сначала при наличии $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$.

Ключ к задаче — понять роль символа «$>$». Во всех трёх заменах он стоит слева от цифры, а в результате оказывается справа от неё. Значит «$>$» работает как каретка, которая ползёт по строке слева направо и обрабатывает очередную цифру, а всё уже обработанное остаётся позади и больше не меняется.

Что происходит с каждой цифрой при проходе каретки:

• цифра $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$, что подтверждает независимость результата от порядка цифр.

Аналитически такие задачи почти не решаются: замены накладываются друг на друга, длина строки то растёт, то падает, и простой зависимости результата от $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$.

Обратите внимание на устройство тела цикла: здесь вложенная конструкция, а не два независимых оператора. За один проход выполняется ровно одна замена, причём приоритет у первой ветки: пока в строке есть $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$.

Здесь три независимых оператора ЕСЛИ, а не вложенная конструкция. Значит, за один проход тела цикла выполняется до трёх замен подряд, строго в записанном порядке: сначала $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$.

Здесь одна конструкция ЕСЛИ–ИНАЧЕ, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $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

Единица в строке всё время ровно одна: обе замены её сохраняют ($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

Конструкция вложенная, поэтому за один проход цикла выполняется ровно одна замена, и у первой ветки абсолютный приоритет: пока в строке есть $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$.

Конструкция вложенная, поэтому за один проход цикла выполняется ровно одна замена, и приоритет у первой ветки: пока в строке есть $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

Ключевая идея: символ «$>$» в строке ровно один, и все три замены устроены одинаково — они забирают цифру, стоящую справа от маркера, дописывают что-то слева от него и передвигают сам маркер на одну цифру вправо. Символ «$>$» работает как курсор, который проезжает по строке слева направо ровно один раз.

Что важно: всё, что маркер уже произвёл, остаётся слева от него и больше никогда не проверяется — шаблоны $>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 при любом порядке

Конструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $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

Символ «$>$» в строке ровно один, и все три замены устроены одинаково: маркер съедает стоящую справа от него цифру, дописывает результат слева и сдвигается на одну позицию вправо. То есть «$>$» работает как курсор, который проезжает строку слева направо ровно один раз.

Всё, что маркер уже произвёл, остаётся слева от него и больше не проверяется: шаблоны $>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 при любом порядке

Присмотримся к трём заменам: $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 при любом порядке

Три оператора ЕСЛИ здесь независимы, а не вложены, поэтому за один проход тела цикла выполняется до трёх замен строго в записанном порядке: сначала $48 \to 8$, затем $288 \to 84$, затем $8888 \to 2$, причём каждая работает уже с результатом предыдущей.

Как замены влияют на сумму цифр: $48 \to 8$ уменьшает её на $4$, $288 \to 84$ — на $6$, $8888 \to 2$ — сразу на $30$. Начальная сумма равна $4 + 8n$ и только убывает, поэтому нужное значение $64$ достигается лишь при удачном стечении обстоятельств в конце работы.

Посмотрим на первый проход. Строка $4\underbrace{88\ldots8}{n}$: команда $48 \to 8$ даёт $n$ восьмёрок, цепочки $288$ нет, а $8888 \to 2$ превращает начало в двойку, и получается $2\underbrace{88\ldots8}{n-4}$. Дальше $288 \to 84$ начинает «производить» четвёрки, $48 \to 8$ их съедает, а $8888 \to 2$ снова порождает двойки — три правила гоняют строку туда-обратно.

Поведение оказывается крайне неустойчивым по $n$, никакой простой формулы нет. Достаточно взглянуть на маленькие значения: $n = 8$ даёт $888$ (сумма $24$), $n = 9$ — $2$ (сумма $2$), $n = 10$ — $842$ (сумма $14$). Поэтому единственный надёжный путь — перебрать все допустимые $n$ и найти первое, дающее сумму $64$.

def run(s):
    while '48' in s or '288' in s or '8888' in s:
        if '48' in s:
            s = s.replace('48', '8', 1)      # только первое вхождение
        if '288' in s:
            s = s.replace('288', '84', 1)
        if '8888' in s:
            s = s.replace('8888', '2', 1)
    return s

for n in range(4, 10000):
    if sum(map(int, run('4' + '8' * n))) == 64:
        print(n)      # 646
        break

Две типичные ошибки: заменять нужно только первое вхождение (третий аргумент $1$ у replace), и три условия должны проверяться последовательно и независимо — если написать их через elif, ответ изменится.

Перебор даёт первое подходящее значение $n = 646$: программа оставляет строку $8842842842842$, сумма цифр которой $8 + 8 + 4 + 2 + 8 + 4 + 2 + 8 + 4 + 2 + 8 + 4 + 2 = 64$. Всего в диапазоне $3 < n < 10,000$ таких $n$ набирается $82$ штуки, следующие после найденного — $663$ и $790$, так что важно брать именно наименьшее.

Символ «$>$» в строке ровно один, и все три замены устроены одинаково: маркер съедает стоящую справа от него цифру, дописывает результат слева и сдвигается на одну позицию вправо. То есть «$>$» работает как курсор, который проезжает строку слева направо ровно один раз.

Всё, что маркер уже произвёл, остаётся слева от него и больше не проверяется: шаблоны $>1$, $>2$, $>3$ требуют, чтобы маркер стоял непосредственно перед цифрой. Поэтому обработанные цифры в дальнейших заменах не участвуют, и вклад каждой исходной цифры можно посчитать отдельно. Цикл завершится, когда справа от маркера не останется цифр.

То, что операторов ЕСЛИ три и они независимы, на результат не влияет: за один проход маркер просто успевает обработать до трёх цифр подряд, но каждая цифра всё равно обрабатывается ровно один раз.

Вклад каждой цифры в сумму: цифра $1$ превращается в $22$ и даёт $2 + 2 = 4$; цифра $2$ превращается в $2$ и даёт $2$; цифра $3$ превращается в $1$ и даёт $1$.

Отсюда итоговая сумма: $$26 \cdot 4 + 10 \cdot 2 + 14 \cdot 1 = 104 + 20 + 14 = 138.$$

Порядок цифр во входной строке никакой роли не играет. Маркер «$>$» остаётся в конце строки, но он не цифра и в сумму не входит.

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' * 26 + '2' * 10 + '3' * 14)
random.shuffle(d)                      # порядок цифр произвольный
r = run('>' + ''.join(d))
print(sum(int(c) for c in r if c.isdigit()))   # 138 при любом порядке