codeforces-scrape

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

1626B.md (1767B)


      1 Source: https://codeforces.com/problemset/problem/1626/B
      2 
      3 B. Minor Reduction
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a decimal representation of an integer $x$ without leading zeros.
     22 
     23 You have to perform the following reduction on it exactly once: take two neighboring digits in $x$ and replace them with their sum without leading zeros (if the sum is $0$, it's represented as a single $0$).
     24 
     25 For example, if $x = 10057$, the possible reductions are:
     26 
     27 * choose the first and the second digits $1$ and $0$, replace them with $1+0=1$; the result is $1057$;
     28 * choose the second and the third digits $0$ and $0$, replace them with $0+0=0$; the result is also $1057$;
     29 * choose the third and the fourth digits $0$ and $5$, replace them with $0+5=5$; the result is still $1057$;
     30 * choose the fourth and the fifth digits $5$ and $7$, replace them with $5+7=12$; the result is $10012$.
     31 
     32 What's the largest number that can be obtained?
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     37 
     38 Each testcase consists of a single integer $x$ ($10 \le x \lt 10^{200000}$). $x$ doesn't contain leading zeros.
     39 
     40 The total length of the decimal representations of $x$ over all testcases doesn't exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each testcase, print a single integer — the largest number that can be obtained after the reduction is applied exactly once. The number should not contain leading zeros.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 2
     52 
     53 10057
     54 
     55 90
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 10012
     62 9
     63 ```
     64 
     65 Note
     66 
     67 The first testcase of the example is already explained in the statement.
     68 
     69 In the second testcase, there is only one possible reduction: the first and the second digits.