codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.