На доске написаны 4 цифры в некотором порядке. За один ход разрешается или выбрать две соседние ненулевые цифры и уменьшить каждую из них на 1, или выбрать две соседние, отличные от девяток цифры и увеличить каждую из них на 1. За какое наименьшее число ходов из последовательности цифр 8, 4, 3, 7 (именно в таком порядке) можно получить 5, 2, 0, 3 (именно в таком порядке)?
Оценка. Пусть
Нужное изменение цифр:
Всего ходов не меньше, чем
Пример за
- Увеличиваем
-ю и -ю цифры на : .
Все ходы допустимы: уменьшаем только ненулевые цифры, увеличиваем только цифры, не равные
Каждый ход меняет сразу две соседние цифры на одно и то же число, поэтому суммарные изменения цифр однозначно задают число ходов над каждой парой. Меньше
