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

USU Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Counting Ones

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
4
11
3
Petr lies
Problem Author: Sergey Pupyrev
Problem Source: The XIIth USU Programing Championship, October 6, 2007
To submit the solution for this problem go to the Problem set: 1564. Counting Ones