← 返回题目列表

Codeforces · 899/D

D. 铲子销售

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

波利卡普的商店里有n把铲子。第 i 铲子花费 i 节,即第一把铲子花费 1 节,第二把铲子花费 2 节,第三把铲子花费 3 节,以此类推。波利卡普斯想要成对出售铲子。

如果总成本以几个 9 结尾,访客更有可能购买一把铲子。因此,波利卡普想要选择一对铲子来出售,使得它们的成本总和以最大可能的 9 个数结尾。例如,如果他选择成本为 12345 和 37454 的铲子,则它们的总成本为 49799,以两个 9 结尾。

您要计算铲子对的数量,使得它们的总成本以最大可能的 9 个数结束。如果一对中有铲子,而另一对中没有,则认为两对不同。

输入

第一行包含一个整数 n (2 ≤ n ≤ 109) — 波利卡普商店中的铲子数量。

输出

打印铲子对的数量,使其总成本以最大可能数量的 9 结尾。

注意,最后的9的最大个数有可能是0,那么你应该把这样的方式都数一遍。

保证对于每个 n ≤ 109,答案不超过 2·109。

示例

输入 #1

7

输出 #1

3

输入 #2

14

输出 #2

9

输入 #3

50

输出 #3

1

注意

在第一个示例中,末尾的 9 的最大可能数量是 1。 Polycarp 为此目的选择以下几对铲子:

- 2 和 7;
- 3 和 6;
- 4 和 5。

在第二个示例中,两把铲子的总成本末尾的 9 的最大数量是 1。以下几对铲子适合波利卡普:

- 1 和 8;
- 2 和 7;
- 3 和 6;
- 4 和 5;
- 5 和 14;
- 6 和 13;
- 7 和 12;
- 8 和 11;
- 9 和 10。

在第三个示例中,需要选择铲子 49 和 50,因为它们的成本之和为 99,这意味着 9 的总数等于 2,这是 n = 50 时的最大可能值。