Petr likes to climb to the top floor of the skyscraper
“Antey” by stairs. While going upstairs Petr looks at the floor numbers and
counts how many digits “1” he comes across. Unfortunately,
last time Petr failed to climb to the top: he fainted
somewhere in the middle.
At hospital he could only recall the
number of ones he had counted.
Help Petr to find out the number of the floor he reached, or, at least,
the number of the floor where the last
of the ones was counted.
Input
The number of ones Petr has counted (an integer not less than 1 and not greater than
1018).
Output
Output the floor number where the last of ones has been sighted.
If Petr has recalled an incorrect number, then output
“Petr lies”.
Samples
input | output |
---|
4
| 11
|
3
| Petr lies
|
Problem Author: Sergey Pupyrev
Problem Source: The XIIth USU Programing Championship, October 6, 2007