AT_abc099_c [ABC099C] Strange Bank

题目描述

在某银行，为了增加取款的难度，每次操作可以取出的金额仅限于以下几种：

• $1$ 日元
• $6$ 日元、$6^2(=36)$ 日元、$6^3(=216)$ 日元、……
• $9$ 日元、$9^2(=81)$ 日元、$9^3(=729)$ 日元、……

请你求出，若要从该银行恰好取出 $N$ 日元，至少需要多少次操作。

注意，已经取出的金额不能再次存入银行。

输入格式

输入以以下格式从标准输入读入。

$N$

输出格式

当从该银行恰好取出 $N$ 日元所需的最少操作次数为 $x$ 时，输出 $x$。

样例 1

输入

127

输出

4

样例 2

输入

3

输出

3

样例 3

输入

44852

输出

16

说明/提示

限制条件

• $1 \leq N \leq 100000$
• $N$ 是整数

样例解释 1

通过各取一次 $1$ 日元、$9$ 日元、$36(=6^2)$ 日元、$81(=9^2)$ 日元，可以在 $4$ 次操作内取出 $127$ 日元。

样例解释 2

通过 $3$ 次各取 $1$ 日元，可以在 $3$ 次操作内取出 $3$ 日元。

由 ChatGPT 4.1 翻译