ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Physical Education

Time limit: 1.0 second
Memory limit: 64 MB
Once a week android Vasya attends his PE classes. His trainer believes that an ability to think has to be trained as well as physical skills. That is why the trainer often gives his group some tasks which are not quite easy to complete.
Today’s task was the following one. Initially n androids stood in one line. The trainer distributed among them different numbers in a decimal notation. All numbers were from 1 to n according to the order in which the androids stood, from left to right. On the trainer’s command students should re-form the line in a new order. Any two neighboring androids in the new line should meet one of the following conditions:
  • the sum of digits in the left android’s number is less than the sum of digits in the right android’s number;
  • the sums of digits in their numbers are equal and the left android’s number is less than the right one’s.
The group was completing the task very slowly. But Vasya found it very boring as he was the first in the line and didn’t have to change his place.
While the androids were re-forming, Vasya decided to determine how many of them didn’t need to change their places. Help him to count this.

Input

The only line contains an integer n that is the number of androids in the group (2 ≤ n ≤ 109).

Output

Output the number of androids who didn’t have to change their places.

Sample

inputoutput
19
3

Notes

New order is 1, 10, 2, 11, 3, 12, 4, 13, 5, 14, 6, 15, 7, 16, 8, 17, 9, 18, 19. Androids 18 and 19 along with Vasya didn’t have to change their places.
Problem Author: Alexander Ipatov (prepared by Bulat Zaynullin)
Problem Source: Ural Sport Programming Championship 2015
To submit the solution for this problem go to the Problem set: 2052. Physical Education