Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в которых v и w обозначают последовательности цифр.
А) заменить (v,w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (121, 3) преобразует строку 112112 в строку 1312.
Если в строке нет вхождений последовательности v, то выполнение команды не изменяет исходную строку.
Б) Нашлось (v).
Эта команда проверяет, встречается ли последовательность v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для редактора:
НАЧАЛО
ПОКА нашлось (90) или нашлось (09)
ЕСЛИ нашлось (90)
ТО заменить (90,090)
ИНАЧЕ
заменить (09, 9)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программы поступает строка из n цифр, содержащая равное количество цифр 0, 9, расположенных в произвольном порядке. При каком минимальном значении n в строке, полученной в результате работы программы, количество цифр 9 будет больше 40?
mn = 10**10
for n in range(100):
s = ’0’*n+’9’*n
while ’90’ in s or ’09’ in s:
if ’90’ in s:
s = s.replace(’90’, ’090’, 1)
else:
s = s.replace(’09’, ’9’, 1)
if s.count(’9’) > 40:
mn = min(mn, n)
break
# В программе n это кол-во одного типа цифр.
# В условии задачи n — общее кол-во цифр.
# Поэтому значение умножаем на 2.
print(mn*2)