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


Задача

10 /16


Крокрыс банк


Задача

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=62) крокрыскоинов, 216(=63) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=92) крокрыскоинов, 729(=93) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.

Входные данные
На вход подается целое число N (\(1<=N<=100000\)).

Выходные данные
Выведите ответ на задачу.

 

Примеры
Входные данные Выходные данные Пояснения
1 127 4 При снятии 1 + 9 + 36 + 81 получится снять 127 крокрыскоина за 4 операции.
2 3 3 1+1+1 = 3, всего 3 операции
3 44852 16  

 

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

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