/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかとなっています。
-
1 円
-
6 円、6^2(=36) 円、6^3(=216) 円、...
-
9 円、9^2(=81) 円、9^3(=729) 円、...
この銀行からちょうど N 円を引き出すには少なくとも何回の操作が必要か求めてください。
ただし、一度引き出したお金を再び預け入れてはならないとします。
制約
- 1 \leq N \leq 100000
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
この銀行からちょうど N 円を引き出すのに少なくとも x 回の操作が必要な時、x を出力せよ。
入力例 1
127
出力例 1
4
1 円、9 円、36(=6^2) 円、81(=9^2) 円を引き出す操作をそれぞれ 1 回ずつ行うことで、合計 4 回の操作で 127 円を引き出すことができます。
入力例 2
3
出力例 2
3
1 円を 引き出す操作を 3 回 行うことで、合計 3 回の操作で 3 円を引き出すことができます。
入力例 3
44852
出力例 3
16
Score : 300 points
Problem Statement
To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:
-
1 yen (the currency of Japan)
-
6 yen, 6^2(=36) yen, 6^3(=216) yen, ...
-
9 yen, 9^2(=81) yen, 9^3(=729) yen, ...
At least how many operations are required to withdraw exactly N yen in total?
It is not allowed to re-deposit the money you withdrew.
Constraints
- 1 \leq N \leq 100000
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
If at least x operations are required to withdraw exactly N yen in total, print x.
Sample Input 1
127
Sample Output 1
4
By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.
Sample Input 2
3
Sample Output 2
3
By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.
Sample Input 3
44852
Sample Output 3
16