Hide
Problem M
Champernowne Verification
The $k^{\text {th}}$ Champernowne word is obtained by writing down the first $k$ positive integers and concatenating them together. For example, the $10^{\text {th}}$ Champernowne word is $12345678910$.
Given a positive integer $n$, determine if it is a Champernowne word, and if so, which word.
Input
The first line contains a single integer, $n$ ($1 \le n \le 10^9$). $n$ will not have leading zeroes.
Output
If $n$ is the $k^{\text {th}}$ Champernowne word, output $k$. Otherwise, output $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
123456789 |
9 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1000000000 |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
11 |
-1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
1324 |
-1 |
