410228: GYM103987 D Hard Tasks

After math class, Teacher Awson gave Sinoey $$$n$$$ tasks as his homework, the $$$i$$$-th of which is to calculate the sum of $$$3$$$ consecutive integers starting from $$$i-1$$$, i.e. $$$(i-1)+i+(i+1)$$$. Note that he does not need to calculate $$$i-1$$$ or $$$i+1$$$.

It is a big problem for Sinoey because he does not want to carry even once! For two numbers represented as $$$\overline{x_n\dots x_2x_1}$$$ and $$$\overline{y_n\dots y_2y_1}$$$, carrying means there exists an integer $$$i\ (1\le i\le n)$$$ such that $$$x_i+y_i\ge 10$$$. Take the $$$4$$$th task, $$$3+4+5$$$ as an example. Since $$$3+4+5>10$$$, Sinoey will have to minus the first digit by $$$10$$$ and add $$$1$$$ to the next digit in order to get the correct answer.

Carrying is awful, and Sinoey decides to do only the tasks that do not require carrying. Now you need to tell him the number of tasks he will do.

The only line of the input contains an integer $$$n\ (1\le n\le 10^{18})$$$, the total number of tasks.

Print an integer representing the number of tasks Sinoey decides to do.

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 ($$$30$$$ points): $$$n\le 10^6$$$.
• Subtask 2 ($$$30$$$ points): $$$n\le 10^{10}$$$.
• Subtask 3 ($$$40$$$ points): no additional constraints.

12

5

141214

1536

In the first example, task $$$1,2,3,11$$$ and $$$12$$$ are easy.