Problem:


Score: 500 points

Problem Statement

N programmers are going to participate in the preliminary stage of DDCC 20XX. Due to the size of the venue, however, at most 9 contestants can participate in the finals.

The preliminary stage consists of several rounds, which will take place as follows:

All the N contestants will participate in the first round.

When X contestants participate in some round, the number of contestants advancing to the next round will be decided as follows:

The organizer will choose two consecutive digits in the decimal notation of X, and replace them with the sum of these digits. The number resulted will be the number of contestants advancing to the next round.

For example, when X = 2378, the number of contestants advancing to the next round will be 578 (if 2 and 3 are chosen), 2108 (if 3 and 7 are chosen), or 2315 (if 7 and 8 are chosen).

When X = 100, the number of contestants advancing to the next round will be 10, no matter which two digits are chosen.

The preliminary stage ends when 9 or fewer contestants remain.

Ringo, the chief organizer, wants to hold as many rounds as possible.
Find the maximum possible number of rounds in the preliminary stage.

Since the number of contestants, N, can be enormous, it is given to you as two integer sequences d_1, \ldots, d_M and c_1, \ldots, c_M, which means the following: the decimal notation of N consists of c_1 + c_2 + \ldots + c_M digits, whose first c_1 digits are all d_1, the following c_2 digits are all d_2, \ldots, and the last c_M digits are all d_M.

Constraints

1 \leq M \leq 200000

0 \leq d_i \leq 9

d_1 \neq 0

d_i \neq d_{i+1}

c_i \geq 1

2 \leq c_1 + \ldots + c_M \leq 10^{15}

Input

Input is given from Standard Input in the following format:

M
d_1 c_1
d_2 c_2
:
d_M c_M

Output

Print the maximum possible number of rounds in the preliminary stage.

Sample Input 1

2
2 2
9 1

Sample Output 1

3

In this case, N = 229 contestants will participate in the first round. One possible progression of the preliminary stage is as follows:

229 contestants participate in Round 1, 49 contestants participate in Round 2, 13 contestants participate in Round 3, and 4 contestants advance to the finals.

Here, three rounds take place in the preliminary stage, which is the maximum possible number.  

Sample Input 2

3
1 1
0 8
7 1

Sample Output 2

9

In this case, 1000000007 will participate in the first round.  



Sample input:
2
2 2
9 1


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############

M = int(input())

n = []
for i in range(M):
    d,c = ip()
    n+= [d for i in range(c)]

def lsum(list=n):
    tmpn = []
    tix = 0
    for i in range(0,len(n)-1,2):
        tix += 1
        tmp = list[i] + list[i+1]
        if tmp>9:
            tmpn += [tmp//10,tmp%10]
        else:
            tmpn += [tmp]
    if len(list)%2==1:
        tmpn.append(list[-1])
    return tmpn,tix
# print(n)
ix = 0
while len(n)>1:
    # print(lsum(n))
    n,ttix = lsum(n)
    ix += ttix
print(ix)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
t = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
s = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]


def _sumall(prev, el):
    n, agg = prev
    agg += el
    n += 1
    if agg >= 10:
        n += 1
        agg = agg//10 + agg % 10
    return n, agg


def sumall(l):
    return reduce(_sumall, l, (-1, 0))


def f(d, c):
    ch = int(c/2)
    l = []
    if c % 2 == 1:
        l.append(d)
    n = t[d] * ch
    if ch >= 2:
        _n, _agg = f(s[d], ch)
        n += _n
        l.append(_agg)
    elif ch == 1:
        l.append(s[d])
    _n, agg = sumall(l)
    return _n+n, agg


m = int(input())

l = []
n = 0
for _ in range(m):
    d, c = map(int, input().split())
    _n, agg = f(d, c)
    n += _n
    l.append(agg)
_n, _ = sumall(l)
n += _n
print(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
M = int(input())
ans = 0
cnt = [1,1,1,1,1,2,2,2,2,2]
res = [0,2,4,6,8,1,3,5,7,9]
    
ans = 0
s = ""
for i in range(M):
    d,c= list(map(int,input().split()))
    t = ""
    while c:
        t += str(d)*(c % 2)
        c = c // 2
        ans += c * cnt[d]
        d = res[d]
    s += t

s = list(s)
while len(s) > 1:
    a = int(s.pop())
    b = int(s.pop())
    t = str(a+b)
    s.extend(list(t))
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
dc = [list(map(int, input().split())) for _ in range(m)]

def zero(n):
    return n - 1, "0"

def one(n):
    ret = 0
    while n // 10:
        q, r = divmod(n, 10)
        n = q + r
        ret += 10 * q
    return ret, "1" * n

def two(n):
    ret = 0
    q, r = divmod(n, 5)
    ret += 5 * q
    one_cnt, ones = one(q)
    ret += one_cnt
    return ret, ones + "2" * r

def three(n):
    ret = 0
    while n // 4:
        q, r = divmod(n, 4)
        n = q + r
        ret += 4 * q
    return ret, "3" * n

def four(n):
    ret = 0
    q, r = divmod(n, 3)
    ret += 3 * q
    three_cnt, threes = three(q)
    ret += three_cnt
    return ret, threes + "4" * r

def five(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    one_cnt, ones = one(q)
    ret += one_cnt
    return ret, ones + "5" * r

def six(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    three_cnt, threes = three(q)
    ret += three_cnt
    return ret, threes + "6" * r

def seven(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    five_cnt, fives = five(q)
    ret += five_cnt
    return ret, fives + "7" * r

def eight(n):
    ret = 0
    q, r = divmod(n, 2)
    ret += 2 * q
    one_cnt, ones = seven(q)
    ret += one_cnt
    return ret, ones + "8" * r

def nine(n):
    ret = 0
    while n // 2:
        q, r = divmod(n, 2)
        n = q + r
        ret += 2 * q
    return ret, "9" * n

new_dc = []
fs = [zero, one, two, three, four, five, six, seven, eight, nine]
for d, c in dc:
    cnt, s = fs[d](c)
    new_dc.append([cnt, s])

s = ""
cnt = 0
for d, c in new_dc:
    s += c
    cnt += d

while len(s) > 1:
    tmp = int(s[-1]) + int(s[-2])
    s = s[:-2] + str(tmp)
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
M = int(input())
ans = 0
cnt = [1,1,1,1,1,2,2,2,2,2]
res = [0,2,4,6,8,1,3,5,7,9]
    
ans = 0
s = ""
for i in range(M):
    d,c= list(map(int,input().split()))
    t = ""
    while c:
        t += str(d)*(c % 2)
        c = c // 2
        ans += c * cnt[d]
        d = res[d]
    s += t

while int(s) > 9:
    a = int(s[-1])
    b = int(s[-2])
    t = str(a+b)
    s = s[:-2]+t
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
m=int(input())
d,c=[],[]
ans=-1
for i in range(m):
  dd,cc=map(int,input().split())
  d.append(dd)
  c.append(cc)
  ans+=cc
a=0
ds=lambda n:sum(list(map(int,list(str(n)))))
for i in range(m):
  if d[i]*c[i]+a<10:a+=d[i]*c[i]
  else:
    if c[i]*d[i]>9:
      ci,di=c[i],d[i]
      while ci*di>9:
        cd=(0--10//di)
        ci,di,cci,ddi=ci//cd,ds(cd*di),ci-(ci//cd*cd),di
        ans+=ci
        if ddi*cci+a>9:ans+=1
        a=ds(ddi*cci+a)
      if di*ci+a>9:ans+=1
      a=ds(di*ci+a)
    else:
      ans+=1
      a=ds(a+c[i]*d[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


M = int(sys.stdin.buffer.readline())
DC = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]


def test(n):
    round = {str(n)}
    ret = 0
    while round:
        next_round = set()
        for n in round:
            for i in range(len(n) - 1):
                s = n[:i] + str(int(n[i]) + int(n[i + 1])) + n[i + 2:]
                if len(s) > 1:
                    next_round.add(s)
        round = next_round
        print(round)
        ret += 1
    print('test:', ret)
    print()


@lru_cache(maxsize=None)
def solve(n):
    n = str(n)
    if len(n) == 1:
        return 0, int(n)
    num = 0
    ret = 0
    for c in str(n):
        ret += 1
        num += int(c)
        while num >= 10:
            ret += 1
            num = num % 10 + 1
    return ret - 1, num


# ans = 0
# num = 0
# for d, c in DC:
#     if d == 0:
#         ans += c
#         n = num + d * c
#         ans += n // 10
#         num = n % 10
#     if d == 1:
#         ans += c
#         n = num + d * c
#         ans += n // 10
#         num = n % 10
#     if d == 2:
#         ans += c
#         n1 = c // 5
#
#         n
#         n = num + d * c
#         ans += c
#         ans += n // 10
#         num = n % 10

memo = [[None] * 10 for _ in range(10)]
for i, j in itertools.product(range(10), range(10)):
    memo[i][j] = solve(str(i) * j)


def kurikaesi(d, c):
    if c < 10:
        return memo[d][c]
    cnt, n1 = solve(str(d) * 10)
    ret = cnt * (c // 10)
    c2, n2 = kurikaesi(n1, c // 10)
    c3, n3 = solve(str(d) * (c % 10))
    ret += c2
    ret += c3
    c4, n4 = solve(str(n2) + str(n3))
    ret += c4
    return ret, n4


#
# n = ''
# for d, c in DC:
#     n += str(d) * c
# test(n)
# print(solve(n))

ans = 0
num = 0
for d, c in DC:
    cnt, n = kurikaesi(d, c)
    ans += cnt
    c2, n2 = solve(str(num) + str(n))
    ans += c2
    num = n2
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

M, = map(int, sys.stdin.readline().rstrip().split(" "))

def too_slow(d_pairs):
    ds = []
    for d, c in d_pairs:
        for _ in range(c):
            ds.append(d)
    d, c = 0, 0
    for next_d in ds:
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
    return c-1


def contract_list(ds):
    d, c = 0, -1
    for next_d, next_c in ds:
        c += next_c
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
        # print(d, c)
    return d, c

def contract_pair(d, orig_c):
    c = 0
    ds = [(d, c)]
    for _ in range(int(math.log(orig_c, 2)) + 1):
        d = d + d
        c = c*2 +1
        if d >= 10:
            d = d % 10 + 1
            c += 1
        ds.append((d, c))
    # print(ds)

    ds_for_calc = []
    for i, b in enumerate(reversed(bin(orig_c)[2:])):
        # print(bin(orig_c), b)
        if b == "1":
            ds_for_calc.append(ds[i])
    # print("for_cal", ds_for_calc)

    return contract_list(ds_for_calc)


ds_for_calc = []
orig_ds = []
for _ in range(M):
    d, c = map(int, sys.stdin.readline().rstrip().split(" "))
    orig_ds.append((d, c))
    ds_for_calc.append(contract_pair(d, c))
    # print(ds_for_calc[-1])
# print("last_list", ds_for_calc)
answer = contract_list(ds_for_calc)[1]
# print(too_slow(orig_ds), answer)
# assert too_slow(orig_ds) == answer
print(answer)

exit(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

M, = map(int, sys.stdin.readline().rstrip().split(" "))

def too_slow(d_pairs):
    ds = []
    for d, c in d_pairs:
        for _ in range(c):
            ds.append(d)
    d, c = 0, 0
    for next_d in ds:
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
    return c-1


def contract_list(ds):
    d, c = 0, -1
    for next_d, next_c in ds:
        c += next_c
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
        # print(d, c)
    return d, c

def contract_pair(d, orig_c):
    c = 0
    ds = [(d, c)]
    for _ in range(int(math.log(orig_c, 2)) + 1):
        d = d + d
        c = c*2 +1
        if d >= 10:
            d = d % 10 + 1
            c += 1
        ds.append((d, c))
    # print(ds)

    ds_for_calc = []
    for i, b in enumerate(reversed(bin(orig_c)[2:])):
        # print(bin(orig_c), b)
        if b == "1":
            ds_for_calc.append(ds[i])
    # print("for_cal", ds_for_calc)

    return contract_list(ds_for_calc)


ds_for_calc = []
orig_ds = []
for _ in range(M):
    d, c = map(int, sys.stdin.readline().rstrip().split(" "))
    orig_ds.append((d, c))
    ds_for_calc.append(contract_pair(d, c))
    # print(ds_for_calc[-1])
# print("last_list", ds_for_calc)
answer = contract_list(ds_for_calc)[1]
# print(too_slow(orig_ds), answer)
assert too_slow(orig_ds) == answer
print(answer)

exit(0)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


M = int(sys.stdin.buffer.readline())
DC = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]


def test(n):
    round = {str(n)}
    ret = 0
    while round:
        next_round = set()
        for n in round:
            for i in range(len(n) - 1):
                s = n[:i] + str(int(n[i]) + int(n[i + 1])) + n[i + 2:]
                if len(s) > 1:
                    next_round.add(s)
        round = next_round
        print(round)
        ret += 1
    print('test:', ret)
    print()


def solve(n):
    n = str(n)
    if len(n) == 1:
        return 0, int(n)
    num = 0
    ret = 0
    for c in str(n):
        ret += 1
        num += int(c)
        while num >= 10:
            ret += 1
            num = num % 10 + 1
    return ret - 1, num


# ans = 0
# num = 0
# for d, c in DC:
#     if d == 0:
#         ans += c
#         n = num + d * c
#         ans += n // 10
#         num = n % 10
#     if d == 1:
#         ans += c
#         n = num + d * c
#         ans += n // 10
#         num = n % 10
#     if d == 2:
#         ans += c
#         n1 = c // 5
#
#         n
#         n = num + d * c
#         ans += c
#         ans += n // 10
#         num = n % 10

memo = [[None] * 10 for _ in range(10)]
for i, j in itertools.product(range(10), range(10)):
    memo[i][j] = solve(str(i) * j)


def kurikaesi(d, c):
    if c < 10:
        return memo[d][c]
    cnt, n1 = solve(str(d) * 10)
    ret = cnt * (c // 10)
    c2, n2 = kurikaesi(n1, c // 10)
    c3, n3 = solve(str(d) * (c % 10))
    ret += c2
    ret += c3
    c4, n4 = solve(str(n2) + str(n3))
    ret += c4
    return ret, n4


#
# n = ''
# for d, c in DC:
#     n += str(d) * c
# test(n)
# print(solve(n))

ans = 0
num = 0
for d, c in DC:
    cnt, n = kurikaesi(d, c)
    ans += cnt
    c2, n2 = solve(str(num) + str(n))
    ans += c2
    num = n2
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############

M = int(input())

n = []
for i in range(M):
    d,c = ip()
    n+= [d for i in range(c)]

def lsum(i,list=n):
    tmp = list[i] + list[i+1]
    if tmp>9:
        return list[:i] + [tmp//10,tmp%10]
    else:
        return list[:i] + [tmp]
# print(n)
ix = 0
while len(n)>1:
    n = lsum(len(n)-2,n)
    ix += 1
print(ix)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
m=int(input())
input_nums=list(list(map(int,input().split())) for _ in range(m))
num=[]
for input_num in input_nums:
  num.extend(list(input_num[0] for _ in range(input_num[1])))
num.reverse()
l=len(num)
count=0
while l > 1:
  i=0
  while i < l-1:
    s=num[i]+num[i+1]
    if s>=10:
      num[i]=s%10
      num[i+1]=s//10
      i-=1
      count+=1
    else:
      i+=1
  num[l-2]=num[l-2]+num[l-1]
  num.pop()
  l-=1
  count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
M = int(input())
d = [0] * M
c = [0] * M
S = []
for i in range(M):
    d[i], c[i] = map(int, input().split())
    for j in range(c[i]):
        S.append(d[i])

cnt = 0
while len(S) > 1:
    S2 = [0] * (len(S)-1)
    
    for i in range(len(S)-1):
        S2[i] = S[i] + S[i+1]
    MAX = max(S2)
    m = S2.index(MAX)
    if MAX > 9:
        S[m] = MAX // 10
        S[m+1] = MAX % 10
    else:
        S[m] = MAX
        del S[m+1]
    
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


M = int(sys.stdin.buffer.readline())
DC = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]


def test(n):
    round = {str(n)}
    ret = 0
    while round:
        next_round = set()
        for n in round:
            for i in range(len(n) - 1):
                s = n[:i] + str(int(n[i]) + int(n[i + 1])) + n[i + 2:]
                if len(s) > 1:
                    next_round.add(s)
        round = next_round
        print(round)
        ret += 1
    print('test:', ret)
    print()


@lru_cache(maxsize=None)
def solve(n):
    n = str(n)
    if len(n) == 1:
        return 0, int(n)
    num = 0
    ret = 0
    for c in str(n):
        ret += 1
        num += int(c)
        while num >= 10:
            ret += 1
            num = num % 10 + 1
    return ret - 1, num


# ans = 0
# num = 0
# for d, c in DC:
#     if d == 0:
#         ans += c
#         n = num + d * c
#         ans += n // 10
#         num = n % 10
#     if d == 1:
#         ans += c
#         n = num + d * c
#         ans += n // 10
#         num = n % 10
#     if d == 2:
#         ans += c
#         n1 = c // 5
#
#         n
#         n = num + d * c
#         ans += c
#         ans += n // 10
#         num = n % 10


def kurikaesi(d, c):
    if c < 10:
        return solve(str(d) * c)
    cnt, n1 = solve(str(d) * 10)
    ret = cnt * (c // 10)
    c2, n2 = kurikaesi(n1, c // 10)
    c3, n3 = solve(str(d) * (c % 10))
    ret += c2
    ret += c3
    c4, n4 = solve(str(n2) + str(n3))
    ret += c4
    return ret, n4

#
# n = ''
# for d, c in DC:
#     n += str(d) * c
# test(n)
# print(solve(n))

ans = 0
num = 0
for i, (d, c) in enumerate(DC):
    cnt, n = kurikaesi(d, c)
    ans += cnt
    c2, n2 = solve(str(num) + str(n))
    ans += c2
    num = n2
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############

M = int(input())

n = []
for i in range(M):
    d,c = ip()
    n+= [d for i in range(c)]

def lsum(i=0,list=n):
    tmp = list[i] + list[i+1]
    if tmp>9:
        return list[:i] + [tmp//10,tmp%10] + list[i+2:]
    else:
        return list[:i] + [tmp] + list[i+2:]
# print(n)
ix = 0
while len(n)>1:
    n = lsum(0,n)
    ix += 1
print(ix)

Submission status: Time Limit Exceeded

Solution code:
M = int(input())
DC = [list(map(int,input().split())) for _ in [0]*M]

ans = 0
res = []
for d,c in DC:
    while c>0:
        if c%2==1:
            res.append(d)
            c -=1
        d *= 2
        if d>=10:
            d = d//10 + d%10
            ans += c
            c//=2
        else:
            ans += c//2
            c//=2

tmp = 0
for r in res:
    ans += 1
    tmp += r
    if tmp >= 10:
        tmp -=9
        ans += 1
ans -=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
m=int(input())
input_nums=list(list(map(int,input().split())) for _ in range(m))
num=[]
for input_num in input_nums:
  num.extend(list(input_num[0] for _ in range(input_num[1])))
num.reverse()
l=len(num)
count=0
while l > 1:
    flag=True
    for i in range(l-1):
        s=num[i]+num[i+1]
        if s>=10:
            num[i]=s%10
            num[i+1]=s//10
            flag=False
            count+=1
            break
    if flag:
        num[l-2]=num[l-2]+num[l-1]
        num.pop()
        l-=1
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

from collections import defaultdict
aaa = defaultdict(lambda:{})
for l in range(10):
    for r in range(10):
        aaa[l][r] = sum_lr(l,r,0)
        

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = aaa[d][d]
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    nums += tmp_nums
    cnt += tmp_cnt
    
#print(nums)    
    
for d, c in nums:
    l, tmp_cnt = aaa[l][d]
    cnt += tmp_cnt

print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
M = int(input())

N = ''

for i in range(M):
    d, c = map(int, input().split())
    
    for i in range(c):
        N += str(d)




def round_num(n):
    koufo = []
    n_int_list = [int(s) for s in list(n)]
    for i in range(len(n)-1):
        a = [n_int_list[i]+n_int_list[i+1]]
        aa = n_int_list[:i] + a + n_int_list[i+2:]
        koufo.append(int(''.join(map(str, aa))))
    
    return str(int(min(koufo)))
        
    
        
ans = 1 

while int(N) > 9:
    ans += 1
    N = round_num(N)
#     print('round:',ans)
#     print('N:', N)
    
        
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
M = int(input())
dc = [[int(i) for i in input().split()] for _ in range(M)]

digit = [0] * 10
for d, c in dc :
    digit[d] += c

ret = digit[0]
digit[0] = 0
while sum(digit) != 1 :
    for a in range(1, 10) :
        for b in range(1, 10) :
            if a + b >= 10 :
                na = (a + b) // 10
                nb = (a + b) % 10
                if a == b :
                    x = digit[a] // 2
                    digit[na] += x
                    digit[nb] += x
                    digit[a] -= 2 * x
                else :
                    x = min(digit[a], digit[b])
                    digit[na] += x
                    digit[nb] += x
                    digit[a] -= x
                    digit[b] -= x
                ret += x
            else :
                if a == b :
                    x = digit[a] // 2
                    digit[a+b] += x
                    digit[a] -= 2 * x
                else :
                    x = min(digit[a], digit[b])
                    digit[a+b] += x
                    digit[a] -= x
                    digit[b] -= x

for d, c in dc :
    if d != 0 :
        ret += c
        
print(ret - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def read_tokens():
    return input().strip().split(' ')

def read_ints():
    return [int(token) for token in read_tokens()]

n, = read_ints()
c = [0] * n
d = [0] * n

# s = ''
for i in range(n):
    # d[i] = (i + 1) % 10
    # c[i] = 10**15 // n
    d[i], c[i] = read_ints()
    if c[i] == 0:
        c[i] = 1/c[i]
    # s += str(d[i]) * c[i]



# print(f's={s}')
# cache = {}
# def f(s):
#     global cache
#     x = int(s)
#     if x <= 9:
#         return 0
#     if s in cache:
#         return cache[s]
#     ans = 0
#     best = ''
#     for i in range(len(s) - 1):
#         a = int(s[i])
#         b = int(s[i+1])
#         t = f(s[:i] + str(a+b) + s[i+2:])
#         ans = max(ans, t + 1)
#         if t + 1 == ans:
#             best = s[:i] + str(a+b) + s[i+2:]

#     for i in range(len(s) - 1):
#         a = int(s[i])
#         b = int(s[i+1])
#         t = f(s[:i] + str(a+b) + s[i+2:])
#         if t + 1 != ans:
#             print(f'!!! {s} {i} {s[:i] + str(a+b) + s[i+2:]} {t + 1} {bedt} {ans}')

#     cache[s] = ans
#     return ans

# print(f(s))

# while True:
#     s, = read_tokens()
#     print(f(s))

def processBlock(n, c):
    # if c < 0:
    #     c = 0
    #     c = 1 / c
    
    
    # if not (c > 0):
    #     while True:
    #         pass

    assert(c > 0)
    
    if c == 1:
        return n, 0

    if c % 2 == 0:
        assert (c > 0)
        if 2 * n < 10:
            rn, rc = processBlock(2 * n, c // 2)
            return rn, rc + c // 2
        else:
            d = (2 * n) // 10 + (2 * n) % 10
            rn, rc = processBlock(d, c // 2)
            return rn, rc + c

    # c % 2 == 1
    # c != 1

    assert(c > 1)
    rn, rc = processBlock(n, c - 1)
    if n + rn < 10:
        return n + rn, rc + 1
    else:
        d = (n + rn) // 10 + (n + rn) % 10
        return d, rc + 2

def solve(D, C):
    ret = 0
    a = []
    for d, c in zip(D, C):
        assert(c > 0)
        n, cc = processBlock(d, c)
        ret += cc
        a.append(n)
    while len(a) > 1:
        d1 = a.pop()
        d2 = a.pop()
        ret += 1
        if d1 + d2 < 10:
            a.append(d1 + d2)
        else:
            a.append(1)
            a.append((d1 + d2) % 10)
    return ret

print(solve(d, c))
# print(f(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft

memo = [
    [0, 1, 1],
    [1,10,9],
    [2,11,9],
    [3,4,3],
    [4,13,9],
    [5,14,9],
    [6,5,3],
    [7,16,9],
    [8,17,9],
    [9,2,1],
]


def main():
    m = int(input())
    dc = [[int(i) for i in input().split()] for _ in range(m)]
    s = []
    ans = 0
    for i in range(m):
        d = dc[i][0]
        c = dc[i][1]
        ans += c // memo[d][2] * memo[d][1]
        if d == 9:
            ans -= 2
            s.append([d, 1])
        else:
            s.append([d, (c % memo[d][2])])
    if not s:
        print(ans)
        return

    t = s[0][0]
    s[0][1] -= 1
    for i in range(len(s)):
        while s[i][1]:
            s[i][1] -= 1
            ans += 1
            t += s[i][0]
            if t > 9:
                ans += 1
                t = t % 10 + t // 10

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def read_tokens():
    return input().strip().split(' ')

def read_ints():
    return [int(token) for token in read_tokens()]

n, = read_ints()
c = [0] * n
d = [0] * n

# s = ''
for i in range(n):
    # d[i] = (i + 1) % 10
    # c[i] = 10**15 // n
    d[i], c[i] = read_ints()
    if c[i] == 0:
        c[i] = 1/c[i]
    # s += str(d[i]) * c[i]



# print(f's={s}')
# cache = {}
# def f(s):
#     global cache
#     x = int(s)
#     if x <= 9:
#         return 0
#     if s in cache:
#         return cache[s]
#     ans = 0
#     best = ''
#     for i in range(len(s) - 1):
#         a = int(s[i])
#         b = int(s[i+1])
#         t = f(s[:i] + str(a+b) + s[i+2:])
#         ans = max(ans, t + 1)
#         if t + 1 == ans:
#             best = s[:i] + str(a+b) + s[i+2:]

#     for i in range(len(s) - 1):
#         a = int(s[i])
#         b = int(s[i+1])
#         t = f(s[:i] + str(a+b) + s[i+2:])
#         if t + 1 != ans:
#             print(f'!!! {s} {i} {s[:i] + str(a+b) + s[i+2:]} {t + 1} {bedt} {ans}')

#     cache[s] = ans
#     return ans

# print(f(s))

# while True:
#     s, = read_tokens()
#     print(f(s))

def processBlock(n, c):
    # if c < 0:
    #     c = 0
    #     c = 1 / c
    
    
    # if not (c > 0):
    #     while True:
    #         pass


    if c == 1:
        return n, 0

    if c % 2 == 0:
        assert (c > 0)
        if 2 * n < 10:
            rn, rc = processBlock(2 * n, c // 2)
            return rn, rc + c // 2
        else:
            d = (2 * n) // 10 + (2 * n) % 10
            rn, rc = processBlock(d, c // 2)
            return rn, rc + c

    # c % 2 == 1
    # c != 1

    assert(c > 1)
    rn, rc = processBlock(n, c - 1)
    if n + rn < 10:
        return n + rn, rc + 1
    else:
        d = (n + rn) // 10 + (n + rn) % 10
        return d, rc + 2

def solve(D, C):
    ret = 0
    a = []
    for d, c in zip(D, C):
        assert(c > 0)
        n, cc = processBlock(d, c)
        ret += cc
        a.append(n)
    while len(a) > 1:
        d1 = a.pop()
        d2 = a.pop()
        ret += 1
        if d1 + d2 < 10:
            a.append(d1 + d2)
        else:
            a.append(1)
            a.append((d1 + d2) % 10)
    return ret

print(solve(d, c))
# print(f(s))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def read_tokens():
    return input().strip().split(' ')

def read_ints():
    return [int(token) for token in read_tokens()]

n, = read_ints()
c = [0] * n
d = [0] * n

# s = ''
for i in range(n):
    # d[i] = (i + 1) % 10
    # c[i] = 10**15 // n
    d[i], c[i] = read_ints()
    if c[i] == 0:
        c[i] = 1/c[i]
    # s += str(d[i]) * c[i]



# print(f's={s}')
# cache = {}
# def f(s):
#     global cache
#     x = int(s)
#     if x <= 9:
#         return 0
#     if s in cache:
#         return cache[s]
#     ans = 0
#     best = ''
#     for i in range(len(s) - 1):
#         a = int(s[i])
#         b = int(s[i+1])
#         t = f(s[:i] + str(a+b) + s[i+2:])
#         ans = max(ans, t + 1)
#         if t + 1 == ans:
#             best = s[:i] + str(a+b) + s[i+2:]

#     for i in range(len(s) - 1):
#         a = int(s[i])
#         b = int(s[i+1])
#         t = f(s[:i] + str(a+b) + s[i+2:])
#         if t + 1 != ans:
#             print(f'!!! {s} {i} {s[:i] + str(a+b) + s[i+2:]} {t + 1} {bedt} {ans}')

#     cache[s] = ans
#     return ans

# print(f(s))

# while True:
#     s, = read_tokens()
#     print(f(s))

def processBlock(n, c):
    if c < 0:
        c = 0
        c = 1 / c
    
    
    if not (c > 0):
        while True:
            pass


    if c == 1:
        return n, 0
    if c % 2 == 0:
        if 2 * n < 10:
            rn, rc = processBlock(2 * n, c // 2)
            return rn, rc + c // 2
        else:
            d = (2 * n) // 10 + (2 * n) % 10
            rn, rc = processBlock(d, c // 2)
            return rn, rc + c

    # c % 2 == 1
    # c != 1

    rn, rc = processBlock(n, c - 1)
    if n + rn < 10:
        return n + rn, rc + 1
    else:
        d = (n + rn) // 10 + (n + rn) % 10
        return d, rc + 2

def solve(D, C):
    ret = 0
    a = []
    for d, c in zip(D, C):
        n, cc = processBlock(d, c)
        ret += cc
        a.append(n)
    while len(a) > 1:
        d1 = a.pop()
        d2 = a.pop()
        ret += 1
        if d1 + d2 < 10:
            a.append(d1 + d2)
        else:
            a.append(1)
            a.append((d1 + d2) % 10)
    return ret

print(solve(d, c))
# print(f(s))

Submission status: Time Limit Exceeded

Solution code:

def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = sum_lr(d, d, 0)
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    nums += tmp_nums
    cnt += tmp_cnt
    
for d, c in nums:
    for _ in range(c):
        l, tmp_cnt = sum_lr(l,d,0)
        cnt += tmp_cnt

print(cnt-1)