Maximum Rounding (Codeforces 1857B)
Tags: Math, implementation

Given a natural number $$$x$$$. You can perform the following operation:   choose a positive integer $$$k$$$ and round $$$x$$$ to the $$$k$$$-th digit 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$$$.The rounding is done as follows:   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).  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'>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'$$$.  after that, all digits which positions are less than $$$k$$$ are replaced with zeros.Your task is to make $$$x$$$ as large as possible, if you can perform the operation as many times as you want.For example, if $$$x$$$ is equal to $$$3451$$$, then if you choose consecutively:   $$$k=1$$$, then after the operation $$$x$$$ will become $$$3450$$$  $$$k=2$$$, then after the operation $$$x$$$ will become $$$3500$$$  $$$k=3$$$, then after the operation $$$x$$$ will become $$$4000$$$  $$$k=4$$$, then after the operation $$$x$$$ will become $$$0$$$  To maximize the answer, you need to choose $$$k=2$$$ first, and then $$$k=3$$$, then the number will become $$$4000$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.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.It is guaranteed that the sum of the lengths of all integers $$$x$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: 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.

Note: In the first sample, it is better not to perform any operations.In the second sample, you can perform one operation and obtain $$$10$$$.In the third sample, you can choose $$$k=1$$$ or $$$k=2$$$. In both cases the answer will be $$$100$$$.

Sample Inputs:
10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467

Sample Outputs:
1
10
100
1000
2000
20444
21000
100000
420000
41000000000000000000

Solution (Python):
for i in range(int(input())):
    s = input()
    n = len(s)
    p = 0
    l = -1
    for i in range(n - 1, -1, -1):
        if int(s[i]) + p > 4:
            p = 1
            l = i
        else:
            p = 0
    if l > -1:
        if l == 0:
            print('1' + '0' * n)
        else:
            print(s[:l - 1] + str(int(s[l - 1]) + 1) + '0' * (n - l))
    else:
        print(s)

Solution (Python):
def f(s):
    n = len(s)
    pre4 = -1
    for i in range(n):
        if int(s[i]) >= 5:
            if i == 0:
                return '1' + '0' * n
            else:
                curr = i - 1
                while curr >= 0 and s[curr] == '4':
                    curr -= 1
                if curr == -1:
                    return '1' + '0' * n
                else:
                    digit = int(s[curr])
                    return s[:curr] + str(digit + 1) + '0' * (n - 1 - curr)
    return s
tc = int(input())
while tc > 0:
    s = input()
    print(f(s))
    tc = tc - 1

Solution (Python):
for i in range(int(input())):
    s = input()
    n = len(s)
    p = 0
    l = -1
    for i in range(n - 1, -1, -1):
        if int(s[i]) + p > 4:
            p = 1
            l = i
        else:
            p = 0
    if l > -1:
        if l == 0:
            print('1' + '0' * n)
        else:
            print(s[:l - 1] + str(int(s[l - 1]) + 1) + '0' * (n - l))
    else:
        print(s)