AtCoder题解｜Strange Bank

AtCoder题解｜ABC 99B Strange Bank

---

题目信息 📚

【题目描述】

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.

【输入】

The input is given from Standard Input in the following format:

$N$

【输出】

If at least $x$ operations are required to withdraw exactly $N$ yen in total, print $x$.

【数据范围】

• $1 \leq N \leq 100000$
• $N$ is an integer.

【输入样例1】

127

【输出样例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.

【输入样例2】

3

【输出样例2】

3

By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.

【输入样例3】

44852

【输出样例3】

16

【题目来源】

https://atcoder.jp/contests/abc099/tasks/abc099_c

---

题目解析 🍉

【题目分析】

【C++代码】

【Python代码】