Модуль: 11.1d Динамическое программирование. Часть 4_Одномерная динамика


2. Калькулятор с восстановлением ответа

Имеется калькулятор, который выполняет три операции:
  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
 
Входные данные
Программа получает на вход одно число X, не превосходящее 106.

Выходные данные
Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. 
 
 
Примеры
Входные данные Выходные данные
1 1  
2 5 121
3 562340 3333312222122213312

Напишите программу
Auto
       

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python167
С++ Mingw-w6456
Комментарий учителя