Minor Reduction (Codeforces 1626B)
Tags: Greedy, strings

You are given a decimal representation of an integer $$$x$$$ without leading zeros.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$$$).For example, if $$$x = 10057$$$, the possible reductions are:   choose the first and the second digits $$$1$$$ and $$$0$$$, replace them with $$$1+0=1$$$; the result is $$$1057$$$;  choose the second and the third digits $$$0$$$ and $$$0$$$, replace them with $$$0+0=0$$$; the result is also $$$1057$$$;  choose the third and the fourth digits $$$0$$$ and $$$5$$$, replace them with $$$0+5=5$$$; the result is still $$$1057$$$;  choose the fourth and the fifth digits $$$5$$$ and $$$7$$$, replace them with $$$5+7=12$$$; the result is $$$10012$$$. What's the largest number that can be obtained?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.Each testcase consists of a single integer $$$x$$$ ($$$10 \le x < 10^{200000}$$$). $$$x$$$ doesn't contain leading zeros.The total length of the decimal representations of $$$x$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

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

Note: The first testcase of the example is already explained in the statement.In the second testcase, there is only one possible reduction: the first and the second digits.

Sample Inputs:
2
10057
90

Sample Outputs:
10012
9

Solution (Python):
import sys

def main():
    for x in range(int(sys.stdin.readline())):
        a = sys.stdin.readline().replace('\n', '')
        mx = 9
        pos = 0
        for x in range(len(a) - 2, -1, -1):
            k = int(a[x]) + int(a[x + 1])
            if k > mx:
                pos = x
                mx = k
                break
        if mx == 9:
            mx = k = int(a[0]) + int(a[1])
        a = a[:pos] + str(mx) + a[pos + 2:]
        sys.stdout.write(a + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
for i in range(int(input())):
    x = input()
    x = x[::-1]
    f = 0
    for j in range(len(x) - 1):
        if int(x[j]) + int(x[j + 1]) >= 10:
            y = str(int(x[j]) + int(x[j + 1]))
            y = y[::-1]
            x = x[:j] + y + x[j + 2:]
            x = x[::-1]
            f = 1
            break
    if f == 1:
        print(x)
    else:
        x = x[::-1]
        z = str(int(x[1]) + int(x[0])) + x[2:]
        print(z)

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    x = [ord(c) - ord('0') for c in readline()]
    n = len(x)
    for i in range(n - 2, -1, -1):
        if x[i] + x[i + 1] >= 10:
            x[i + 1] += x[i] - 10
            x[i] = 1
            break
    else:
        x[1] += x[0]
        x.pop(0)
    print(''.join([chr(c + ord('0')) for c in x]))

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()