2132D.md (1397B)
1 Source: https://codeforces.com/problemset/problem/2132/D 2 3 D. From 1 to Infinity 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Vadim wanted to understand the infinite sequence of digits that consists of the positive integers written consecutively from $1$ to infinity. That is, this sequence looks like $123456789101112131415 \ldots$ 22 23 To avoid looking into infinity, Vadim cut this sequence at the $k$-th digit and discarded everything after it. Thus, exactly $k$ digits remained in the sequence. Help him find the sum of the digits in the remaining sequence. 24 25 Input 26 27 Each test consists of several test cases. The first line contains a single integer $t$ $(1 \le t \le 2 \cdot 10^4)$ — the number of test cases. The following lines describe the test cases. 28 29 In a single line of each test case, there is an integer $k$ — the number of digits in the remaining sequence $(1 \le k \le 10^{15})$. 30 31 Output 32 33 For each given $k$, output the sum of the digits in the sequence of length $k$. 34 35 Example 36 37 Input 38 39 ``` 40 6 41 42 5 43 44 10 45 46 13 47 48 29 49 50 1000000000 51 52 1000000000000000 53 ``` 54 55 Output 56 57 ``` 58 15 59 46 60 48 61 100 62 4366712386 63 4441049382716054 64 ``` 65 66 Note 67 68 In the first sample, the remaining sequence will be $12345$. 69 70 In the second sample, the remaining sequence will be $1234567891$. 71 72 In the third sample, the remaining sequence will be $1234567891011$.