Strange Bank

题目描述

为了使取钱变得困难，某银行只允许客户在一次操作中取出以下金额之一：

$1$ 日元（日本的货币）

$6$ 日元，$6^2(=36)$ 日元，$6^3(=216)$ 日元，...

$9$ 日元，$9^2(=81)$ 日元，$9^3(=729)$ 日元，...

至少需要多少次操作才能总共取出恰好 $N$ 日元？ 不允许将已取出的钱重新存入。

输入格式

输入按以下格式从标准输入给出： $N$

输出格式

如果至少需要 $x$ 次操作才能恰好取出 $N$ 日元，则打印 $x$。

127

4

3

3

44852

16

提示

$1 \leq N \leq 100000$ $N$ 是整数。通过取出 $1$ 日元、$9$ 日元、$36(=6^2)$ 日元和 $81(=9^2)$ 日元，我们可以在四次操作中取出 $127$ 日元。
通过三次取出 $1$ 日元，我们可以在三次操作中取出 $3$ 日元。

标签: AtCoder|abc099C

来源

AtCoder|abc099C