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.