Question

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
нашлось (v)
Дана программа для исполнителя Редактор:
ПОКА нашлось (555) ИЛИ нашлось (333)
ЕСЛИ нашлось (333)
ТО заменить (333, 5)
ИНАЧЕ заменить (555, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
Дана строка, состоящая из 500 цифр 5. Сколько пятёрок было удалено за время обработки строки по этой программе?

Answer 1

После первого шага алгоритма из 500 "5" получается 1 "3" и 497 "5"; после второго - 2 "3" и 494 "5", после третьего - 3 "3" и 491 "5"; после четвертого - 492 "5". Таким образом, после каждых 4 шагов количество "5" уменьшается на 8.

К последнему шагу алгоритма в строке останется 500-62*8 = 4 "5".

После последнего шага - 1 "3" и 1 "5", т.е. "35".

Таким образом, за время обработки из строки удалится 500-1 = 499 пятёрок.