Исполнитель Панцирь получает на вход строку цифр и преобразовывает её. Панцирь может выполнять две команды, в обеих командах \(v\) и \(w\) обозначают цепочки символов.
1. заменить (\(v\), \(w\))
2. нашлось (\(v\))
Первая команда заменяет в строке первое слева вхождение цепочки \(v\) на цепочку \(w\). Если цепочки \(v\) в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка \(v\) в строке исполнителя Панцирь. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».
Дана программа для исполнителя Панцирь:
НАЧАЛО
ПОКА нашлось\((7)\) ИЛИ нашлось\((33)\) ИЛИ нашлось\((888)\)
ЕСЛИ нашлось\((7)\)
ТО заменить\((7, 33)\)
ИНАЧЕ ЕСЛИ нашлось\((33)\)
ТО заменить\((33, 3)\)
ИНАЧЕ ЕСЛИ нашлось\((888)\)
ТО заменить\((888, 7)\)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке \(\underbrace{77\dots77}_{500}\underbrace{33\dots33}_{120}\underbrace{88\dots88}_{280}?\)
Для удобства будем использвовать следующие обозначения для количества одинаковых цифр, идущих подряд: \(A_{(B)},\) где A - цифра, которая находится в строке, а B - количество этих цифр.
Изначально была строка \(7_{(500)} 3_{(120)} 8_{(280)}.\) Самое приоритетное действие в цикле ПОКА – это замена 7 на 33. На протяжении всей работы программы оно будет выполняться до тех пор, пока семерок не останется вообще. Для текущей же строки все семерки заменятся парами троек, которых будет в 2 раза больше, чем изначальное количество семерок, т.е. 1000.
\(7_{(500)} 3_{(120)} 8_{(280)} \rightarrow 3_{(1120)} 8_{(280)}\)
Второе по приоритету действие - это замена пары троек на одну тройку. Это действие перестанет выполняться, когда количество троек станет 1.
\(3_{(1120)} 8_{(280)} \rightarrow 3_{(1)} 8_{(280)}\)
Далее, необходимо прогонять получаемые строки по алгоритму до тех пор, пока мы не получим конструкцию из одной тройки и какого-то количества восьмерок, большего или равного 3. Если мы получим идентичную конструкцию, но с другим количеством цифр, то это значит, что выполнение определенного набора действий будет зациклено до тех пор, пока условие наличия одной единицы, двух троек или трех восьмерок не будет нарушено.
\(3_{(1)} 8_{(280)} \rightarrow 3_{(1)} 7_{(1)} 8_{(277)} \rightarrow 3_{(3)} 8_{(277)} \rightarrow 3_{(2)} 8_{(277)} \rightarrow 3_{(1)} 8_{(277)}\)
Итак, из \(3_{(1)} 8_{(280)}\) мы получили \(3_{(1)} 8_{(277)},\) значит выполнять те же действия большое количество раз не нужно, мы можем сразу снижать количество восьмерок.
За один шаг количество уменьшилось на 3, значит нужно вычесть из 280 ближайшее к этому числу значение, кратное 3, т.е. 276.
\(3_{(1)} 8_{(280)} \rightarrow 3_{(1)} 8_{(4)}\)
Теперь снова вручную прогоним полученную строку.
\(3_{(1)} 8_{(4)} \rightarrow 3_{(1)} 7_{(1)} 8_{(1)} \rightarrow 3_{(3)} 8_{(1)} \rightarrow 3_{(2)} 8_{(1)} \rightarrow 3_{(1)} 8_{(1)}\)
Таким образом, в конце выполнения программа будет выведено 38.
Ответ: 38