Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
Дана программа для редактора:
НАЧАЛО
ПОКА нашлось (444)
заменить (444, 33)
заменить (33, 44)
КОНЕЦ ПОКА
КОНЕЦ
Известно, что исходная строка содержала более 100 четверок и не содержала других цифр. Укажите минимально возможную длину исходной строки, при которой в результате работы этой программы получится строка, содержащая минимально возможное четное количество четверок.
Решение руками:
Две замены в цикле преобразуют 444 в 44 (убирает одну четвёрку) пока в строке есть 444.
Так как преобразование убирает одну четверку, не имеет значения длина исходной строки (большая 100), ведь получится в результате одна и та же строка — 44.
Тогда нам ничего не мешает взять наименьшее число большее 100. Это 101.
Решение программой:
def process_string(s):
while "444" in s:
s = s.replace("444", "33", 1)
s = s.replace("33", "44", 1)
return s
def count_fours(s):
return s.count("4")
min_even_fours = float(’inf’)
min_length = float(’inf’)
for length in range(101, 200):
s = "4" * length
result = process_string(s)
fours = count_fours(result)
if fours % 2 == 0 and fours < min_even_fours:
min_even_fours = fours
min_length = length
elif fours == min_even_fours and length < min_length:
min_length = length
print(min_length)