← 返回题目列表

AtCoder · abc099_c

C. 奇怪的银行

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

为增加取款难度,某银行允许客户一次操作只能提取以下金额之一:

  • 1 日元(日本货币)

  • 6 日元, 6^2(=36) 日元, 6^3(=216) 日元,...

  • 9 日元, 9^2(=81) 日元, 9^3(=729) 日元,...

至少需要多少次操作才能准确提现 N 总共日元?

您提取的资金不允许重新存入。

约束

  • 1 \leq N \leq 100000
  • N 是一个整数。

输入

输入由标准输入按以下格式给出:

N

输出

如果至少 x 提现需要操作 N 总计日元,打印 x.


示例输入 1

127

示例输出 1

4

通过撤回 1 日元, 9 日元, 36(=6^2) 日元和 81(=9^2) 日元,我们可以提现 127 日元四次操作。


示例输入 2

3

示例输出 2

3

通过撤回 1 日元三倍,我们可以提现 3 日元三项操作。


示例输入 3

44852

示例输出 3

16