373B.md (1230B)
1 Source: https://codeforces.com/problemset/problem/373/B 2 3 B. Making Sequences is Fun 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 We'll define *S*(*n*) for positive integer *n* as follows: the number of the *n*'s digits in the decimal base. For example, *S*(893) = 3, *S*(114514) = 6. 22 23 You want to make a consecutive integer sequence starting from number *m* (*m*, *m* + 1, ...). But you need to pay *S*(*n*)·*k* to add the number *n* to the sequence. 24 25 You can spend a cost up to *w*, and you want to make the sequence as long as possible. Write a program that tells sequence's maximum length. 26 27 Input 28 29 The first line contains three integers *w* (1 ≤ *w* ≤ 1016), *m* (1 ≤ *m* ≤ 1016), *k* (1 ≤ *k* ≤ 109). 30 31 Please, do not write the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier. 32 33 Output 34 35 The first line should contain a single integer — the answer to the problem. 36 37 Examples 38 39 Input 40 41 ``` 42 9 1 1 43 ``` 44 45 Output 46 47 ``` 48 9 49 ``` 50 51 Input 52 53 ``` 54 77 7 7 55 ``` 56 57 Output 58 59 ``` 60 7 61 ``` 62 63 Input 64 65 ``` 66 114 5 14 67 ``` 68 69 Output 70 71 ``` 72 6 73 ``` 74 75 Input 76 77 ``` 78 1 1 2 79 ``` 80 81 Output 82 83 ``` 84 0 85 ```