← 返回题目列表

Codeforces · 331/C3

C3. 伟大的朱利亚日历

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

又一场世界末日即将来临!这次的罪魁祸首就是朱利亚部落的历法。

这个部落的海狸非常了解数学。聪明的海狸是一位考古学家,他得到了一个神圣的盘子,上面有一个神奇的整数。 Old Beaverish 的翻译如下:

“愿伟大的海狸保佑你!愿你的查克斯张开,愿你的第三只眼睛永远不会因看到真相而失明!取出魔法数字,从中减去一个数字(该数字必须出现在数字中)并得到一个新的魔法数字。重复此操作,直到魔法数字等于零。地球将在三只海狸上停留一段时间,等于你执行减法的次数!”

不同的减法序列显然可以得到不同的运算次数。但聪明的海狸已准备好面对最坏的情况,并要求您计算他将幻数减少到零所需的最少操作次数。

输入

单行包含幻数 n,0 ≤ n。

- 要得到20分,需要解决有约束的问题:n ≤ 106(子问题C1);
- 要得到40分,需要解决有约束的问题:n ≤ 1012(子问题C1+C2);
- 要获得 100 分,您需要解决具有约束条件的问题:n ≤ 1018(子问题 C1+C2+C3)。

输出

打印一个整数——将幻数变成零的最小减法次数。

示例

输入 #1

24

输出 #1

5

注意

在第一个测试样本中,可以通过以下减法序列达到最小操作数:

24 → 20 → 18 → 10 → 9 → 0