Исполнитель Панцирь получает на вход строку цифр и преобразовывает её. Панцирь может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.
1. заменить (\(v\), \(w\))
2. нашлось (\(v\))
Первая команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w.\) Если цепочки \(v\) в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка \(v\) в строке исполнителя Панцирь. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».
Дана программа для исполнителя Панцирь:
НАЧАЛО
ПОКА нашлось\((9)\) ИЛИ нашлось\((11)\) ИЛИ нашлось\((555)\)
ЕСЛИ нашлось\((9)\)
ТО заменить\((9, 11)\)
ИНАЧЕ ЕСЛИ нашлось\((11)\)
ТО заменить\((11, 1)\)
ИНАЧЕ ЕСЛИ нашлось\((555)\)
ТО заменить\((555, 9)\)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какое число получится в результате применения приведенной выше программы к строке \(\underbrace{99\dots99}_{423}\underbrace{11\dots11}_{762}\underbrace{55\dots55}_{980}?\)
Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: \(A_{(B)},\) где A - цифра, которая находится в строке, а B - количество этих цифр.
Изначально была строка \(9_{(423)} 1_{(762)} 5_{(980)}.\) Самое приоритетное действие в цикле ПОКА – это замена 9 на 11. На протяжении всей работы программы оно будет выполняться до тех пор, пока девяток не останется вообще. Для текущей же строки все девятки заменятся парами единиц, которых будет в 2 раза больше, чем изначальное количество девяток, т.е. 846.
\(9_{(423)} 1_{(762)} 5_{(980)} \rightarrow 1_{(1608)} 5_{(980)}\)
Второе по приоритету действие - это замена пары единиц на одну единицу. Это действие перестанет выполняться, когда количество единиц станет 1.
\(1_{(1608)} 5_{(980)} \rightarrow 1_{(1)} 5_{(980)}\)
Далее, необходимо прогонять получаемые строки по алгоритму до тех пор, пока мы не получим конструкцию из одной единицы и какого-то количества пятерок, большего или равного 3. Если мы получим идентичную конструкцию, но с другим количеством цифр, то это значит, что выполнение определенного набора действий будет зациклено до тех пор, пока условие наличия одной девятки, двух единиц или трех пятерок не будет нарушено.
\(1_{(1)} 5_{(980)} \rightarrow 1_{(1)} 9_{(1)} 5_{(977)} \rightarrow 1_{(3)} 5_{(977)} \rightarrow 1_{(2)} 5_{(977)} \rightarrow 1_{(1)} 5_{(977)}\)
Итак, из \(1_{(1)} 5_{(980)}\) мы получили \(1_{(1)} 5_{(977)},\) значит выполнять те же действия большое количество раз не нужно, мы можем сразу снижать количество пятерок.
За один шаг количество уменьшилось на 3, значит нужно вычесть из 980 ближайшее к этому числу значение, кратное 3, т.е. 975.
\(1_{(1)} 5_{(980)} \rightarrow 1_{(1)} 5_{(5)}\)
Теперь снова вручную прогоним полученную строку.
\(1_{(1)} 5_{(5)} \rightarrow 1_{(1)} 9_{(1)} 5_{(2)} \rightarrow 1_{(3)} 5_{(2)} \rightarrow 1_{(2)} 5_{(2)} \rightarrow 1_{(1)} 5_{(2)}\)
Ответ: 155