Score : $300$ points

问题描述

为限制取款的便利性，某银行规定其客户在单次操作中仅能取出以下金额之一：

• 1 日元（日本货币）

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

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

至少需要进行多少次操作才能精确取出总计 N 日元？

不允许将已取出的资金再次存入。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 17:19:09