12. Выполнение алгоритмов для исполнителей: На вход приведённой ниже программе поступает строка…
Исполнитель Редактор получает на вход строку символов и преобразовывает её. Редактор может выполнять две команды, в обеих командах $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$, что подтверждает независимость результата от порядка цифр.