Problem:


Score: 500 points

Problem Statement

In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. (Takoyaki is the name of a Japanese snack.)

To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.

What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?

Assume that you have sufficient numbers of banknotes, and so does the clerk.

Constraints

N is an integer between 1 and 10^{1,000,000} (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print the minimum possible number of total banknotes used by you and the clerk.

Sample Input 1

36

Sample Output 1

8

If you give four banknotes of value 10 each, and the clerk gives you back four banknotes of value 1 each, a total of eight banknotes are used.

The payment cannot be made with less than eight banknotes in total, so the answer is 8.

Sample Input 2

91

Sample Output 2

3

If you give two banknotes of value 100, 1, and the clerk gives you back one banknote of value 10, a total of three banknotes are used.

Sample Input 3

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

Sample Output 3

243



Sample input:
36


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

flag = 0
res = 0
while N > 0:
	n = N % 10
	if flag == 2:
		if n <= 4:
			flag = 0
			res += n
		elif n == 5:
			flag = 1
			res += 4
		elif n >= 6:
			flag = 1
			res += 9 - n
	else:
		if flag == 1:
			n += 1
		if n == 5:
			flag = 2
			res += 5
		elif n > 5:
			flag = 1
			res += 10 - n
		else:
			flag = 0
			res += n
		
	N = N // 10

if flag == 1:
	print(res + 1)
else:
	print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

flag = 0
res = 0
while N >= 0:
	n = N % 10
	if flag == 2:
		if n <= 4:
			flag = 0
			res += n
		elif n == 5:
			flag = 1
			res += 4
		elif n >= 6:
			flag = 1
			res += 9 - n
	else:
		if flag == 1:
			n += 1
		if n == 5:
			flag = 2
			res += 5
		elif n > 5:
			flag = 1
			res += 10 - n
		else:
			flag = 0
			res += n
		
	N = N // 10
	if N == 0 and flag == 0:
		break

print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3.6
import sys
input = sys.stdin.readline
INF = 10**9

a = [int(item) for item in list(input().rstrip())]
n = len(a)
# DP[i-th item][0:pay just / 1:pay over]
dp = [[INF] * 2 for _ in range(n + 1)] 
dp[0][0] = 0

for i, item in enumerate(a):
    dp[i+1][0] = min(dp[i+1][0], dp[i][0] + item, dp[i][1] + item)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0] + 10 - item + 1, dp[i][1] + 10 - item - 1)

print(min(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3.6
import sys
input = sys.stdin.readline
INF = 10**9

s = input().rstrip()[::-1]
n = len(s)
# DP[i-th item][0:pay just / 1:pay over]
dp = [[INF] * 2 for _ in range(n + 1)] 
dp[0][0] = 0

for i, ch in enumerate(s):
    a = int(ch)
    dp[i+1][0] = min(dp[i+1][0], dp[i][0] + a)
    dp[i+1][0] = min(dp[i+1][0], dp[i][1] + a)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0] + 10 - a + 1)
    dp[i+1][1] = min(dp[i+1][1], dp[i][1] + 10 - a - 1)

print(min(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
s = input()

s = s[::-1]
s += "0"
l = len(s)

dp = [[float("inf")] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i, e in enumerate(s):
    for j in range(2):
        x = int(e)
        x += j
        if x < 10:
            dp[i+1][0] = min(dp[i+1][0], dp[i][j] + x)
        dp[i+1][1] = min(dp[i+1][1], dp[i][j] + 10 - x)

ans = dp[l][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
S = str(N)

S = S[::-1] + "0"
len_s = len(S)
dp = [[float("inf") for j in range(2)] for i in range(len_s+1)]
dp[0][0] = 0

for i in range(len_s):
  for j in range(2):
    x = int(S[i])
    x += j

    if x == 0:
      dp[i+1][0] = min(dp[i][j], dp[i+1][0])
    elif x == 5:
      next = int(S[i+1])
      if next <= 4:
        dp[i+1][0] = min(dp[i][j]+x, dp[i+1][0])
      else:
        dp[i+1][1] = min(dp[i][j]+10-x, dp[i+1][1])
    elif x <= 4:
      dp[i+1][0] = min(dp[i][j]+x, dp[i+1][0])
    else:
      dp[i+1][1] = min(dp[i][j]+10-x, dp[i+1][1])

print(dp[len_s][0])

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
S = str(N)

S = S[::-1] + "0"
len_s = len(S)
dp = [[float("inf") for j in range(2)] for i in range(len_s+1)]
dp[0][0] = 0

for i in range(len_s):
  for j in range(2):
    x = int(S[i])
    x += j
    for a in range(10):
      ni, nj = i+1, 0
      b = a - x
      if b < 0:
        nj = 1
        b += 10
      dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b)

print(dp[len_s][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()

s = s[::-1]
s += "0"
l = len(s)

dp = [[float("inf")] * 2 for _ in range(l + 1)]
dp[0][0] = 0

for i, e in enumerate(s):
    for j in range(2):
        x = int(e)
        x += j
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - x
            if b < 0:
                nj = 1
                b += 10

            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

ans = dp[l][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
# 下の桁から見ていく
S = S[::-1]
N = len(S)

# dp0[i] := 下からi桁目まで見た時の最小値(直前で繰り上げなし)
dp0 = [INF] * (N+1)
# dp1[i] := 下からi桁目まで見た時の最小値(直前で繰り上げあり)
dp1 = [INF] * (N+1)
dp0[0] = 0
for i, s in enumerate(S):
    s = int(s)
    # この桁で繰り上げない遷移
    dp0[i+1] = min(dp0[i+1], dp0[i] + s)
    dp0[i+1] = min(dp0[i+1], dp1[i] + (s+1))
    # この桁で繰り上げる遷移
    dp1[i+1] = min(dp1[i+1], dp0[i] + 10-s)
    dp1[i+1] = min(dp1[i+1], dp1[i] + 10-(s+1))
# 繰り上げる方は最後の繰り上げ分を足す
ans = min(dp0[N], dp1[N]+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input().strip())
N = list(map(int, str(N)[::-1]))
before = 0
ans = 0
L = len(N)
for i, c in enumerate(N):
    n = c + before
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == L:
            before = 0
            ans += n
            continue
        if N[i+1] < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N = int(input().strip())
N = str(N)[::-1]
before = 0
ans = 0
ansB = 0
for i, c in enumerate(N):
    n = int(c)+before
    ansB += int(c)
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == len(N):
            before = 0
            ans += n
            continue
        if int(N[i+1]) < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
N = str(N)[::-1]
before = 0
ans = 0
ansB = 0
for i, c in enumerate(N):
    n = int(c)+before
    ansB += int(c)
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == len(N):
            before = 0
            ans += n
            continue
        if int(N[i+1]) < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)

Submission status: Time Limit Exceeded

Solution code:
# 解説放送
# 写経

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s
    *s, = map(int, s)  # 先に一括でintにした

    n = len(s)

    dp = [[inf] * 2 for _ in range(n + 1)]
    dp[0][0] = 0

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            x = c + j
            if x < 10:
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)  # a=x,b=0
            if x > 0:
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))  # a=0,bに繰り下がり

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送
# 写経

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

    dp = [[inf] * 2 for _ in range(n + 1)]
    dp[0][0] = 0

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            x = int(c) + j
            if x < 10:
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)  # a=x,b=0
            if x > 0:
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))  # a=0,bに繰り下がり

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

    dp = [[inf] * 2 for _ in range(n + 1)]
    dp[0][0] = 0

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            for a in range(10):
                ni = i + 1
                nj = 0  # unpackをやめた
                x = int(c) + j
                b = a - x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送

def main():
    inf = 18 * (10 ** 6 + 1)

    s = input()
    s = '0' + s

    n = len(s)

    dp = [[inf] * 2 for _ in range(n + 1)]
    dp[0][0] = 0

    for i, c in enumerate(s[::-1]):
        for j in range(2):
            for a in range(10):
                ni, nj = i + 1, 0
                x = int(c) + j
                b = a - x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=input()
X=len(N)
INF=10**100
dp=[[INF,INF] for i in range(0,X+1)]
dp[0][0]=0
dp[0][1]=1
for j in range(1,X+1):
    dp[j][0]=min(dp[j-1][0]+int(N[j-1])%10,dp[j-1][1]+10-int(N[j-1])%10)
    if int(N[j-1])%10!=9:
        dp[j][1]=min(dp[j-1][1]+9-int(N[j-1])%10,dp[j-1][0]+int(N[j-1])%10+1)
    else:
        dp[j][1]=dp[j-1][1]+9-int(N[j-1])%10
print(dp[X][0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
X=len(str(N))
INF=10**100
dp=[[INF,INF] for i in range(0,X+1)]
dp[0][0]=0
dp[0][1]=1
for j in range(1,X+1):
    i=N//(10**(X-j))
    dp[j][0]=min(dp[j-1][0]+i%10,dp[j-1][1]+10-i%10)
    if i%10!=9:
        dp[j][1]=min(dp[j-1][1]+9-i%10,dp[j-1][0]+i%10+1)
    else:
        dp[j][1]=dp[j-1][1]+9-i%10
print(dp[X][0])

Submission status: Time Limit Exceeded

Solution code:
a = int(input())

x = dict()
x[0] = 0
x[1] = 1
x[2] = 2
x[3] = 3
x[4] = 4
x[5] = 5
x[6] = 5
x[7] = 4
x[8] = 3
x[9] = 2
x[10] = 1
x[11] = 2
x[12] = 3
x[13] = 4
x[14] = 5
x[15] = 6
x[16] = 6
x[17] = 5
x[18] = 4
x[19] = 3
x[20] = 2

def dp(n):
    if n in x:
        return x[n]
    else:
        if 10**len(str(n)) - n < n:
            x[n] = min(dp(10**len(str(n)) - n) + 1, int(str(n)[0]) + dp(int(str(n)[1:])))
        else:
            x[n] = int(str(n)[0]) + dp(int(str(n)[1:]))
        return x[n]

print(dp(a))

Submission status: Time Limit Exceeded

Solution code:

N=input()
cnt=0
bit=0
bitflag=0
cur=0
inf=1001001001

Nd="".join(("0",N))


dp=[[inf for _ in range(2)] for _ in range(1000005)]
dp[0][0]=0
print(dp)
for i in range(0,len(Nd),1):
    for j in range(2):
        x=int(Nd[len(Nd)-1-i])
        #print(x)
        x=x+j
        for a in range(0,10,1):
            ni=i+1
            nj=0
            b=a-x
            if b<0:
                nj=1
                b=b+10
            dp[ni][nj]=min(dp[ni][nj],dp[i][j]+a+b)

print(dp[len(Nd)][0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=input()
cnt=0
bit=0
bitflag=0
cur=0
inf=1001001001
dp=np.zeros((1000005,2)) #dp[N][2]
dp=dp.tolist()
Nd="".join(("0",N))
#print(Nd)
for i in range(0,len(Nd)+1,1):
    for j in range(2):
        dp[i][j]=inf
dp[0][0]=0
for i in range(0,len(Nd),1):
    for j in range(2):
        x=int(Nd[len(Nd)-1-i])
        #print(x)
        x=x+j
        for a in range(0,10,1):
            ni=i+1
            nj=0
            b=a-x
            if b<0:
                nj=1
                b=b+10
            dp[ni][nj]=min(dp[ni][nj],dp[i][j]+a+b)

print(dp[len(Nd)][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
s += "0"
n = len(s)
dp = [[10**7 for _ in range(2)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	for j in range(2):
		x = int(s[i]) + j
		for a in range(10):
			kurisagaru = False
			if a >= x:
				b = 0
			else:
				b = 10 + a - x
				kurisagaru = True
			dp[i+1][kurisagaru] = min(dp[i+1][kurisagaru], dp[i][j]+a+b)
print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()
s += ["0"]
n = len(s)
dp = [[10**7 for _ in range(2)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	for j in range(2):
		x = int(s[i]) + j
		for a in range(10):
			kurisagaru = False
			if a >= x:
				b = 0
			else:
				b = 10 + a - x
				kurisagaru = True
			dp[i+1][kurisagaru] = min(dp[i+1][kurisagaru], dp[i][j]+a+b)
print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j

        if x < 10:
            dp[i+1][0] = min(dp[i][j] + x,dp[i+1][0])
        if x > 0:
            dp[i+1][1] = min(dp[i][j] + (10 - x),dp[i+1][1])


print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]
s += "0"
n = len(s)

dp = [[1001001001]*2 for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = int(s[i]) + j
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - x
            if b < 0:
                nj = 1
                b += 10
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)

print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n = str(input().rstrip())

def solve1(n):
    ans = 0

    a = list(map(int, list(n)))
    a = a[::-1]
    a.append(0)
    for i in range(len(a) - 1):
        c = a[i]
        if c < 5:
            ans += c
        else:
            if c == 5 and a[i+1] < 5:
                ans += 5
            else:
                a[i+1] += 1
                ans += 10 - c
    ans += n_list[-1]

    print(ans)

def solve2(n):
    INF = 10**9
    n = n[::-1]
    n += '0'
    n_len = len(n)
    dp = [INF for _ in range(2)]
    dp[0] = 0

    for i in range(n_len):
        pre_dp = deepcopy(dp)
        dp = [INF, INF]
        for j in range(2):
            x = int(n[i])
            x += j
            if x < 10:
                dp[0] = min(dp[0], pre_dp[j]+x)
            if x > 0:
                dp[1] = min(dp[1], pre_dp[j]+(10-x))

    print(dp[0])
solve2(n)

Submission status: Time Limit Exceeded

Solution code:
n = str(input().rstrip())

def solve1(n):
    ans = 0

    a = list(map(int, list(n)))
    a = a[::-1]
    a.append(0)
    for i in range(len(a) - 1):
        c = a[i]
        if c < 5:
            ans += c
        else:
            if c == 5 and a[i+1] < 5:
                ans += 5
            else:
                a[i+1] += 1
                ans += 10 - c
    ans += n_list[-1]

    print(ans)

def solve2(n):
    INF = 10**9
    n = n[::-1]
    n += '0'
    n_len = len(n)
    dp = [[INF for _ in range(2)] for _ in range(n_len+1)]
    dp[0][0] = 0

    for i in range(n_len):
        for j in range(2):
            x = int(n[i])
            x += j
            if x < 10:
                dp[i+1][0] = min(dp[i+1][0], dp[i][j]+x)
            if x > 0:
                dp[i+1][1] = min(dp[i+1][1], dp[i][j]+(10-x))

    print(dp[n_len][0])
solve2(n)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
Nr = list(reversed(list(map(int,str(n)))))
Nr.append(0)

ans = 0 
for i in range(len(Nr)):
    if Nr[i] > 5:
        Nr[i+1] += 1
        ans += (10 - Nr[i])
    elif Nr[i]==5:
        if Nr[i+1]>=5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        else:
            ans += Nr[i]
    else:
        ans += Nr[i]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
Nr = list(reversed(list(map(int,str(n)))))
Nr.append(0)

ans = 0 
for i in range(len(Nr)):
    if i<(10**100):
        if Nr[i] > 5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        elif Nr[i]==5:
            if Nr[i+1]>=5:
                Nr[i+1] += 1
                ans += (10 - Nr[i])
            else:
                ans += Nr[i]
        else:
            ans += Nr[i]
    elif i==(10**100):
        A = Nr[i:]
        B = list(map(str,A))
        C = "".join(B)
        D = int(C)
        ans += D
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

N = list(map(int,str(n)))

# print(N)

Nr = list(reversed(N))
Nr.append(0)
# print(Nr)

ans = 0 
for i in range(len(Nr)):
    if i<(10**100):
        if Nr[i] > 5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        elif Nr[i]==5:
            if Nr[i+1]>=5:
                Nr[i+1] += 1
                ans += (10 - Nr[i])
            else:
                ans += Nr[i]
        else:
            ans += Nr[i]
    elif i==(10**100):
        A = Nr[i:]
        B = list(map(str,A))
        C = "".join(B)
        D = int(C)
        ans += D
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
ans = 0
N1 = N[::-1]
b = ""
l = 0
for i in range(len(N)):
  if int(N1[i])+l==5 and i<len(N)-1 and int(N1[i+1])>=5:
    b+="0"
    l=1
    continue
  if int(N1[i])+l>10-(int(N1[i])+l):
    if i==len(N)-1:
      b+="01"
      continue
    b+="0"
    l=1
  else:
    b+=str(int(N1[i])+l)
    l=0
#print(b[::-1])
b1 = int(b[::-1])
b2 = b1-int(N)
ans+=sum(list(map(int, str(b1))))
ans+=sum(list(map(int, str(b2))))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
n = [0] + list(str(m))
n = [int(n[i]) for i in range(len(n))]

for i in range(len(n)):
    if n[(i + 1) * (-1)] >= 10:
        n[(i + 1) * (-1)] -= 10
        n[(i + 2) * (-1)] += 1
    elif n[(i + 1) * (-1)] >= 6:
        n[(i + 2) * (-1)] += 1
        n[(i + 1) * (-1)] = 0
    elif n[(i + 1) * (-1)] == 5:
        if n[(i + 2) * (-1)] >= 5:
            n[(i + 2) * (-1)] += 1
            n[(i + 1) * (-1)] = 0
cnt = sum(n)

num = ''
for i in n:
    num = num + str(i)
num = int(num)

m = num - m
n = [0] + list(str(m))
n = [int(n[i]) for i in range(len(n))]
cnt += sum(n)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:

n = input()
n_r = list(map(int,list(n)[::-1]))
for i in range(len(n)):
    if len(n_r) < i+1+1:
        n_r.append(0)
    if n_r[i] >= 10:
        n_r[i] -= 10
        n_r[i+1] += 1
    if n_r[i] > 5 or (n_r[i] > 4 and n_r[i+1] > 4) or (n_r[i] > 3 and n_r[i+1] > 9):
        n_r[i+1] += 1
        n_r[i] = 0
a = sum(map(int,list(n)))
# print(int("".join(list(map(str,n_r[::-1]) ) ) ))
# print("0000"+str(int("".join(list(map(str,n_r[::-1]) ) ) ) - int(n)))
tmp = map(int,list(str(int("".join(list(map(str,n_r[::-1]) ) ) ) - int(n))))
b = sum(n_r[::-1]) + sum(tmp)

if a > b:
    print(b)
else:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
S = "0" + input()

digits = [int(c) for c in S.rstrip("0")]

f = [
    None,
    [None] * len(digits),
    [None] * len(digits),
]  # f[sign][place] where sign is 1 or -1


for place in reversed(range(len(digits))):
    for sign in [-1, 1]:
        if place == len(digits) - 1:
            if sign > 0:
                exact = digits[place]
            else:
                exact = 10 - digits[place]
            f[sign][place] = exact
            continue

        if sign > 0:
            exact = digits[place]
            overpay = exact + 1  # Overpaying flips the sign of the balance
        else:
            assert sign < 0
            exact = 10 - digits[place] - 1
            overpay = exact + 1
        f[sign][place] = min(exact + f[sign][place + 1], overpay + f[-sign][place + 1])
print(f[1][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = input()
    N_list = list((map(int,list(N))))
    N_list.insert(0,0)
    for i in range(len(N_list)-1,0,-1):
        if 6<=N_list[i] and N_list[i-1]<9:
            N_list[i] = 0
            N_list[i-1] += 1
        elif 5<=N_list[i] and N_list[i-1] == 9:
            N_list[i] = 0
            d = i-1
            while N_list[d]==9:
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        elif 1<i:
            if N_list[i] == 5 and 5<=N_list[i-1]:
                N_list[i] = 0
                N_list[i-1] = 0
                d = i-2
                while N_list[d]==9:
                    N_list[d] = 0
                    d -= 1
                N_list[d] += 1

    print(sum(N_list)+sum(map(int,list(str(int("".join(map(str,N_list)))-int(N))))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

S = "0" + input()

digits = [int(c) for c in S.rstrip("0")]


@lru_cache(maxsize=None)
def f(sign, place):
    if place == len(digits) - 1:
        if sign > 0:
            exact = digits[place]
        else:
            exact = 10 - digits[place]
        return exact

    if sign > 0:
        exact = digits[place]
        overpay = exact + 1  # Overpaying flips the sign of the balance
    else:
        assert sign < 0
        exact = 10 - digits[place] - 1
        overpay = exact + 1

    return min(exact + f(sign, place + 1), overpay + f(-sign, place + 1))


for sign in [-1, 1]:
    for place in reversed(range(len(digits))):
        f(sign, place)

print(f(1, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    # dp:=上からi桁目まで払える最小の枚数
    S = list(map(int, '0'+input()))
    l = len(S)
    dp = [[1e18]*2 for _ in range(1001001)]
    dp[0][0]=0
    for i in range(l):
        k = S[i]
        dp[i+1][0] = min(dp[i+1][0], dp[i][0]+k)
        dp[i+1][1] = min(dp[i+1][1], dp[i][0]+k+1)
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+10-k)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+10-k-1)
    print(dp[l][0])

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
N = str(N)
N = tuple(map(int, N))

ans = 0
flag = False
flag5 = False
i = len(N)-1


for x in reversed(N):
    if flag or (flag5 and x >= 5):
        x += 1
    flag5 = False
    flag = False
    if x > 5:
        ans += (10 - x)
        flag = True
        if i == 0:
            ans += 1
    else:

        ans += x
    if x == 5:
        flag5 = True
    i -= 1

print(ans)

Submission status: Time Limit Exceeded

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


from functools import lru_cache

n = list(map(int, list(input())))
m = len(n)

@lru_cache(10**10)
def rec(keta, tight):
    if keta == m:
        if tight:
            return 1
        else:
            return 0
    tmp = float("inf")
    for i in range(10):
        if tight:
            if i == 0:
                tmp = min(tmp, rec(keta+1, True)+9-n[keta])

            elif i <= n[keta]:
                tmp = min(tmp, rec(keta+1, True)+i+10+i-1-n[keta])
            else:
                tmp = min(tmp, rec(keta+1, False)+i+i-1-n[keta])
        else:
            if i < n[keta]:
                tmp = min(tmp, rec(keta+1, True)+i+(10+i)-n[keta])
            else:
               tmp = min(tmp, rec(keta+1, False)+i+i-n[keta])
    return tmp

ans = rec(0, False)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    kuriage = 0
    LEN = len(n)
    pay_count = 0
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    print(pay_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


from functools import lru_cache

n = list(map(int, list(input())))
m = len(n)

@lru_cache(10**10)
def rec(keta, tight):
    if keta == m:
        if tight:
            return 1
        else:
            return 0
    tmp = float("inf")
    for i in range(10):
        if tight:
            if i == 0:
                tmp = min(tmp, rec(keta+1, True)+9-n[keta])

            elif i <= n[keta]:
                tmp = min(tmp, rec(keta+1, True)+i+10+i-1-n[keta])
            else:
                tmp = min(tmp, rec(keta+1, False)+i+i-1-n[keta])
        else:
            if i < n[keta]:
                tmp = min(tmp, rec(keta+1, True)+i+(10+i)-n[keta])
            else:
               tmp = min(tmp, rec(keta+1, False)+i+i-n[keta])
    return tmp

ans = rec(0, False)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    pay = []
    kuriage = 0
    LEN = len(n)
    pay_count = 0
    oturi_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    oturi_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    oturi_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                oturi_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    
    print(pay_count+oturi_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 0
s = str(n)
l = len(s)

N = [0 for i in range(l)]

for i in range(l):
    N[i] = int(s[-i-1])
N.append(0)

for i in range(l+1):
    if N[i]<5:
        ans += N[i]
    elif N[i]>5:
        ans += 10-N[i]
        N[i+1] += 1
    elif N[i+1]>4:
        ans += 10-N[i]
        N[i+1] += 1
    else:
        ans += N[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    pay = []
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay.append(str(n[i]+kuriage))
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay.append("0")
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay.append(str(n[i]+kuriage))
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay.append("0")
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay.append(str(n[i]+kuriage))
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay.append("0") 
                kuriage = 1

    if kuriage == 1:
        pay.append("1")
        pay_count += 1
    
    pay = ''.join(pay[::-1])
    oturi = int(pay)-N
    oturi_count = 0
    
    for i in str(oturi):
        oturi_count += int(i)

    print(pay_count+oturi_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 0
l = len(str(n))

N = [0 for i in range(l)]

for i in range(l):
    N[i] = int(str(n)[-i-1])
N.append(0)

for i in range(l+1):
    if N[i]<5:
        ans += N[i]
    elif N[i]>5:
        ans += 10-N[i]
        N[i+1] += 1
    elif N[i+1]>4:
        ans += 10-N[i]
        N[i+1] += 1
    else:
        ans += N[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
n = str(n)
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
ans = 0
for i in range(len(n_list) - 1):
    num = n_list[i]
    if (num <= 5 and n_list[i + 1] < 5) or num < 5:
        # pay += num * 10 ** k
        ans += num
    else:
        n_list[i + 1] += 1
        ans += 10 - n_list[i]
    k += 1

# pay += n_list[-1] * 10 ** k
ans += n_list[-1]
print(ans)
# oturi = pay - int(n)
# ans = 0
#
# for i in str(pay):
#     ans += int(i)
# for i in str(oturi):
#     ans += int(i)
# print(ans)