codeforces-scrape

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

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