410228: GYM103987 D Hard Tasks

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Hard Taskstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

Scoring

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.
ExamplesInput
12
Output
5
Input
141214
Output
1536
Note

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

加入题单

上一题 下一题 算法标签: