codeforces-scrape

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

1932E.md (1911B)


      1 Source: https://codeforces.com/problemset/problem/1932/E
      2 
      3 E. Final Countdown
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are in a nuclear laboratory that is about to explode and destroy the Earth. You must save the Earth before the final countdown reaches zero.
     22 
     23 The countdown consists of $n$ ($1 \le n \le 4 \cdot 10^5$) mechanical indicators, each showing one decimal digit. You noticed that when the countdown changes its state from $x$ to $x-1$, it doesn't happen in one move. Instead, each change of a single digit takes one second.
     24 
     25 So, for example, if the countdown shows 42, then it will change to 41 in one second, because only one digit is changed, but if the countdown shows 2300, then it will change to 2299 in three seconds, because the three last digits are changed.
     26 
     27 Find out how much time is left before the countdown reaches zero.
     28 
     29 Input
     30 
     31 The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.
     32 
     33 The first line of each test case contains a single integer $n$ ($1\le n\le 4\cdot 10^5$).
     34 
     35 The second line contains a string of $n$ digits, the current state of the countdown. It is guaranteed that at least one digit is not zero.
     36 
     37 The sum of $n$ for all tests does not exceed $4\cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer without leading zeroes, the number of seconds left before the countdown reaches zero. Note that this number may be huge.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 2
     51 
     52 42
     53 
     54 5
     55 
     56 12345
     57 
     58 2
     59 
     60 99
     61 
     62 4
     63 
     64 0005
     65 
     66 27
     67 
     68 456480697259671309012631002
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 46
     75 13715
     76 108
     77 5
     78 507200774732968121125145546
     79 ```
     80 
     81 Note
     82 
     83 In the first example, there are four changes that take 2 seconds: 40 to 39, 30 to 29, 20 to 19, and 10 to 09, other changes take 1 second each. So the total time is $2\cdot 4 + 1\cdot(42-4) = 46$.