1857B.md (2625B)
1 Source: https://codeforces.com/problemset/problem/1857/B 2 3 B. Maximum Rounding 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 Given a natural number $x$. You can perform the following operation: 22 23 * choose a positive integer $k$ and round $x$ to the $k$-th digit 24 25 Note that the positions are numbered from right to left, starting from zero. If the number has $k$ digits, it is considered that the digit at the $k$-th position is equal to $0$. 26 27 The rounding is done as follows: 28 29 * if the digit at the $(k-1)$-th position is greater than or equal to $5$, then the digit at the $k$-th position is increased by $1$, otherwise the digit at the $k$-th position remains unchanged (mathematical rounding is used). 30 * if before the operations the digit at the $k$-th position was $9$, and it should be increased by $1$, then we search for the least position $k'$ ($k' \gt k$), where the digit at the $k'$-th position is less than $9$ and add $1$ to the digit at the $k'$-th position. Then we assign $k=k'$. 31 * after that, all digits which positions are less than $k$ are replaced with zeros. 32 33 Your task is to make $x$ as large as possible, if you can perform the operation as many times as you want. 34 35 For example, if $x$ is equal to $3451$, then if you choose consecutively: 36 37 * $k=1$, then after the operation $x$ will become $3450$ 38 * $k=2$, then after the operation $x$ will become $3500$ 39 * $k=3$, then after the operation $x$ will become $4000$ 40 * $k=4$, then after the operation $x$ will become $0$ 41 42 To maximize the answer, you need to choose $k=2$ first, and then $k=3$, then the number will become $4000$. 43 44 Input 45 46 The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. 47 48 Each test case consists of positive integer $x$ with a length of up to $2 \cdot 10^5$. It is guaranteed that there are no leading zeros in the integer. 49 50 It is guaranteed that the sum of the lengths of all integers $x$ over all test cases does not exceed $2 \cdot 10^5$. 51 52 Output 53 54 For each set of input data, output the maximum possible value of $x$ after the operations. The number should not have leading zeros in its representation. 55 56 Example 57 58 Input 59 60 ``` 61 10 62 63 1 64 65 5 66 67 99 68 69 913 70 71 1980 72 73 20444 74 75 20445 76 77 60947 78 79 419860 80 81 40862016542130810467 82 ``` 83 84 Output 85 86 ``` 87 1 88 10 89 100 90 1000 91 2000 92 20444 93 21000 94 100000 95 420000 96 41000000000000000000 97 ``` 98 99 Note 100 101 In the first sample, it is better not to perform any operations. 102 103 In the second sample, you can perform one operation and obtain $10$. 104 105 In the third sample, you can choose $k=1$ or $k=2$. In both cases the answer will be $100$.