Final Countdown (Codeforces 1932E)
Tags: Math, number theory

You are in a nuclear laboratory that is about to explode and destroy the Earth. You must save the Earth before the final countdown reaches zero. The countdown consists of $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) mechanical indicators, each showing one decimal digit. You noticed that when the countdown changes its state from $$$x$$$ to $$$x-1$$$, it doesn't happen in one move. Instead, each change of a single digit takes one second. So, for example, if the countdown shows 42, then it will change to 41 in one second, because only one digit is changed, but if the countdown shows 2300, then it will change to 2299 in three seconds, because the three last digits are changed.Find out how much time is left before the countdown reaches zero.

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the descriptions of the test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 4\cdot 10^5$$$). The second line contains a string of $$$n$$$ digits, the current state of the countdown. It is guaranteed that at least one digit is not zero.The sum of $$$n$$$ for all tests does not exceed $$$4\cdot 10^5$$$.

Output: For each test case, print a single integer without leading zeroes, the number of seconds left before the countdown reaches zero. Note that this number may be huge.

Note: In the first example, there are four changes that take 2 seconds: 40 to 39, 30 to 29, 20 to 19, and 10 to 09, other changes take 1 second each. So the total time is $$$2\cdot 4 + 1\cdot(42-4) = 46$$$.

Sample Inputs:
5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002

Sample Outputs:
46
13715
108
5
507200774732968121125145546

Solution (Python):
def gcd(a, b):
    while b:
        (a, b) = (b, a % b)
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def minput():
    return map(int, input().split())

def linput():
    return list(map(int, input().split()))
MOD = int(1000000000.0) + 7
sz = int(100000.0) + 5
INT_MAX = float('inf')

def solve():
    n = int(input())
    s = input()
    total = 0
    for i in s:
        total += ord(i) - 48
    res = ''
    carry = 0
    for c in s[::-1]:
        x = carry + total
        carry = x // 10
        d = x % 10
        total -= ord(c) - 48
        res += chr(d + 48)
    res = str(carry) + res[::-1]
    res = res.lstrip('0')
    print(res)

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
def solve(n, s):
    d = [0] * n
    ss = 0
    for i in range(n):
        ss += ord(s[i]) - ord('0')
        d[i] = ss
    z = 0
    for i in range(n - 1, -1, -1):
        z += d[i]
        d[i] = z % 10
        z //= 10
    while z != 0:
        d = [z] + d
        z //= 10
    return ''.join(map(str, d)).lstrip('0')
tests = int(input())
for test in range(tests):
    n = int(input())
    s = input()
    print(solve(n, s))

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def main():
    for i in range(int(input())):
        d = int(input())
        n = list(map(int, input()))
        count = 0
        for j in range(d):
            count += n[j]
        tot = count
        ans = str(count)[-1]
        count = count // 10
        for j in range(d - 1, 0, -1):
            tot -= n[j]
            count += tot
            ans += str(count)[-1]
            count = count // 10
        if count != 0:
            ans += str(count)
        ans1 = ''
        for j in range(-1, -len(ans) - 1, -1):
            ans1 += ans[j]
        j = 0
        while ans1[j] == '0':
            j += 1
        print(ans1[j:])
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()