Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (111)
заменить (111, 22)
заменить (222, 11)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка содержала более 50 единиц и не содержала других цифр. Укажите минимально возможную длину исходной строки, при которой в результате работы этой программы получится строка, содержащая минимально возможное количество единиц.
mndl = 10000
mn = 10000
for i in range(51, 1000):
s = ’1’*i
while ’111’ in s:
s = s.replace(’111’, ’22’, 1)
s = s.replace(’222’, ’11’, 1)
if s.count(’1’) < mndl:
mndl = s.count(’1’)
mn = i
print(mn)