Исполнитель Панцирь получает на вход строку цифр и преобразовывает её. Панцирь может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Панцирь. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».
Дана программа для Панцирь:
НАЧАЛО
ПОКА нашлось(*3) или нашлось(*2)
ЕСЛИ нашлось(*23)
ТО заменить(*23, 5*)
ИНАЧЕ ЕСЛИ нашлось(*2)
ТО заменить(*2, 0*)
КОНЕЦ ЕСЛИ
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось(*3)
ТО заменить(*3, 3*)
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой программе поступает строка, начинающаяся с символа «*», после него в строке находится 10 троек и неизвестное количество двоек. Расположение цифр может быть любым. Определите наименьшее количество двоек, которые могли содержаться в изначальной строке, если сумма цифр строки, полученной в результате выполнения программы равна 50.
Решение руками
Программа заменяет двойки, за которыми находится тройка на пятерки. Если же за двойкой находится другая двойка, то левая двойка заменяется нулем. Свободные тройки не затрагиваются действиями программы. Чтобы минимизировать количество двоек нужно найти количество свободных троек, сумма которых будет кратна 5.
Допустим, это 5 свободных троек. Таким образом, необходимо количество двоек, которые в паре с остальными 5 тройками преобразуются в пятерки. Этих пятерок будет 5. Но условие суммы цифр, равных 50 не выполнено.
Больше 5 свободных троек брать смысла нет, т.к. если и 5 троек не допускает выполнение условия, то больше тем более, поскольку троек всего 10, а ровно 50 сложением троек получить не удастся.
Тогда возьмем 10 троек, находящихся в паре с двойками. В результате выполнения программы появится 10 пятерок, а значит условие суммы цифр будет выполнено.
Решение программой
def simulate(s):
while ’*3’ in s or ’*2’ in s:
if ’*23’ in s:
s = s.replace(’*23’, ’5*’, 1)
elif ’*2’ in s:
s = s.replace(’*2’, ’0*’, 1)
if ’*3’ in s:
s = s.replace(’*3’, ’3*’, 1)
return s.replace(’*’, ’’)
min_d = 0
for d in range(0, 101):
# Для оптимального результата все 10 троек должны быть спарены с двоек,
# поэтому минимальное количество двоек не может быть меньше 10.
if d < 10:
continue
# Оптимальное размещение: сначала 10 пар "23", затем оставшиеся (d-10) двоек.
s = ’*’ + ’23’ * 10 + ’2’ * (d - 10)
final = simulate(s)
if sum(int(ch) for ch in final) == 50:
min_d = d
break
print(min_d)