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: Accepted

Solution code:
s = input()
n = len(s)

s = list(map(int, list(s)))
dp1 = [0] * (n + 1)
dp2 = [0] * (n + 1)
dp2[0] = 1

for k in range(n):
    dp1[k + 1] = min([dp1[k] + s[k]       , dp2[k] + 10 - s[k]])
    dp2[k + 1] = min([dp1[k] + s[k] + 1, dp2[k] + 10 - s[k] - 1])

print(dp1[-1])

Submission status: Accepted

Solution code:
digits = input()
digits = list(map(int, digits[::-1]))
digits.append(0)

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

print(ans)

Submission status: Accepted

Solution code:
n = input()
t = len(n)+1
dp1 = [0] * t
dp2 = [0]*t
dp2[0] = 1

for i in range(t-1):
    x = int(n[i])
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + 10 - x)
    x += 1
    dp2[i+1] = min(dp1[i]+x, dp2[i]+10-x)
print(dp1[-1])

Submission status: Accepted

Solution code:
N = input()
a, b = 0, 1
for i in N:
    x = int(i)
    a, b = min(a+x, b+10-x), min(a+x+1, b+9-x)
print (a)

Submission status: Accepted

Solution code:

N = input()
N = N[::-1]

c = 0
otsuri = 0
mai = 0
for i in range(len(N)):
    if int(N[i]) + c == 5 and i < len(N) - 1:
        if int(N[i+1]) >= 5:
            otsuri += 5
            c = 1
        else:
            mai += int(N[i]) + c
            c = 0
    elif int(N[i]) + c > 5:
        otsuri += 10 - int(N[i]) - c
        c = 1
    else:
        mai += int(N[i]) + c
        c = 0

print(otsuri + mai + c)

Submission status: Accepted

Solution code:
N = input()

dp0 = 0  
dp1 = 1  
 
for n in N:
    n = int(n)
    dp0_new = min(dp0 + n, dp1 + (10 - n))
    n = n + 1 #繰り上げさせてる
    dp1_new = min(dp0 + n, dp1 + (10 - n))
    dp0, dp1 = dp0_new, dp1_new

print(dp0)

Submission status: Accepted

Solution code:
N=input()

dp0=[0]*(len(N)+1)
dp1=[0]*(len(N)+1)
dp1[0]=1

for i in range(len(N)):
    n=int(N[i])
    dp0[i+1]=min(dp0[i]+n, dp1[i]+(10-n))
    n+=1
    dp1[i+1]=min(dp0[i]+n, dp1[i]+(10-n))

#print(dp0)
#print(dp1)
print(dp0[-1])

Submission status: Accepted

Solution code:
x = list(map(int,list(input())))
n = len(x)
dp = [[0,1] for _ in range(n+1)]
for i in range(n):
    dp[i+1][0] = min(dp[i][0]+x[i],dp[i][1]+10-x[i])
    dp[i+1][1] = min(dp[i][0]+x[i]+1,dp[i][1]+9-x[i])
print(dp[n][0])

Submission status: Accepted

Solution code:
n='0'+input()

X=[]
for i in range(len(n)):
    X.append(int(n[i]))
cnt=0
i=len(n)-1
while i>=0:
    if X[i]>5:
        cnt+=10-X[i]
        X[i-1]+=1
        
    elif X[i]==5:
        cnt+=5
        if X[i-1]>=5:
            X[i-1]+=1
    else:
        cnt+=X[i]
    i-=1
print(cnt)

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))[::-1]
L = len(N)

answer = 0
for i, n in enumerate(N):
    if n < 5:
        answer += n
    elif n > 5:
        answer += 10 - n
        if i < L - 1:
            N[i + 1] += 1
        else:
            answer += 1
    else:
        answer += 5
        if i < L - 1:
            if N[i + 1] >= 5:
                N[i + 1] += 1

print(answer)

Submission status: Accepted

Solution code:
# E - Payment

N = input().strip()

s = 0
carry = 0
prev = None
for c in reversed(N):
    x = int(c) + carry
    if x > 5 or x == prev == 5:
        if prev == 5:
            x += 1
        s += 10 - x
        carry = 1
    else:
        s += x
        carry = 0
    prev = x
s += carry

print(s)

Submission status: Accepted

Solution code:
# E - Payment

N = input().strip()

s = 0
carry = 0
five = False
for c in reversed(N):
    x = int(c) + carry
    if x == 5 and not five:
        s += x
        carry = 0
        five = True
    elif x >= 5:
        if five:
            x += 1
        s += 10 - x
        carry = 1
        five = False
    else:
        s += x
        carry = 0
        five = False
s += carry

print(s)

Submission status: Accepted

Solution code:
N = (list(input()))
N =N[::-1]
N_int = [int(i) for i in N]
N_int.append(0)
maisu = 0
keta = False
for i in range(len(N_int)-1):
    if keta ==True:
        N_int[i] +=1
    if N_int[i]<5:
        maisu +=N_int[i]
        keta =False
    elif N_int[i]==5 :
        if N_int[i+1]>4:
            keta =True
            maisu +=(10-N_int[i])
        else:
            keta =False
            maisu += N_int[i]
    else:
        keta =True
        maisu +=(10-N_int[i])  
if keta ==True:
    maisu +=1
print(maisu)

Submission status: Accepted

Solution code:
def main():
    n = input()
    a, b = 0, 1
    for i in n:
        x = int(i)
        a, b = min(a + x, b + 10 - x), min(a + x + 1, b + 10 - x - 1)
    print(a)

main()

Submission status: Accepted

Solution code:
N = input()

keta = len(N)

dp = [[10**18 for i in range(2)] for j in range(keta)]

t = int(N[-1])

dp[0][0] = t
dp[0][1] = 10 - t

for i in range(keta - 2, -1, -1):
    
    t = int(N[i])
    #print(keta-i,i,t)
    dp[keta-i-1][0] = min(dp[keta-i-2][0]+t,dp[keta-i-2][1]+t+1)
    dp[keta-i-1][1] = min(dp[keta-i-2][0]+(10-t),dp[keta-i-2][1]+(10-(t+1)))
    #a, b = min(a + t, b + (t + 1)), min(a + (10 - t), b + (10 - (t + 1)))

#print(dp)

print(min(dp[keta-1][0],dp[keta-1][1]+1))

Submission status: Accepted

Solution code:
n = input()
a = 0
b = 2
for s in n:
  v = int(s)
  a_ = min(a + v, b + v)
  b_ = min(a + 10 - v + 1, b + 10 - v + 1 - 2)
  a = a_
  b = b_
  
print(min(a, b))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = ["0"] + S()
    n = n[::-1]
    dp1 = [inf] * (len(n))
    dp2 = [inf] * (len(n))
    dp1[0] = int(n[0])
    dp2[0] = 10-int(n[0])
    for i in range(len(n)-1):
        x = int(n[i+1])
        if dp1[i] + x < dp1[i + 1]:
            dp1[i + 1] = dp1[i] + x
        if x != 0:
            if dp1[i] + (10 - x) < dp2[i + 1]:
                dp2[i + 1] = dp1[i] + (10 - x)
        x += 1
        if x != 10:
            if dp2[i] + x < dp1[i + 1]:
                dp1[i + 1] = dp2[i] + x
        if dp2[i] + (10 - x) < dp2[i + 1]:
            dp2[i + 1] = dp2[i] + (10 - x)

    print(min(dp1[-1],dp2[-1]))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N = input()
    
    INF = 10 ** 32
    
    dp = [[INF, INF] for i in range(len(N) + 1)]
    dp[0][0] = 0
    
    for i, x in enumerate(int(n) for n in N[::-1]):
        ni = i + 1
        dp[ni][0] = min(dp[i][0] + x, dp[i][1] + x)
        dp[ni][1] = min(dp[i][0] + 11 - x, dp[i][1] + 9 - x)
    
    ans = min(dp[-1])
    
    print(ans)

solve()

Submission status: Accepted

Solution code:
N = input()
DP = [0,0]
kuriagari = 0
kuriagarazu = 0
for n in N:
    n = int(n)
    kuriagaru = 11 - n + kuriagari
    kuriagaranai = n + kuriagarazu
    DP.append([kuriagaru, kuriagaranai])
    kuriagari = DP[-1][0] - 2 if DP[-1][0] - 2 < DP[-1][1] else DP[-1][1]
    kuriagarazu = DP[-1][0] if DP[-1][0] < DP[-1][1] else DP[-1][1]

answer = min(DP[-1])
print(answer)

Submission status: Accepted

Solution code:
#E
#greedy 
n = input()
l = len(n)

#a is kuriagari naku, pittari na case
#b is kuriagari ari
a,b = 0,1
for v in n:
    v = int(v)
    a_next = min(a+v, b+(10-v))
    b_next = min(a+v+1, b+(10-(v+1)))
    a = a_next
    b = b_next
    
    #繰り上がりが発生する⇔引く数を+1する
    #(10-v)や(10-(v+1)) means charges
    #last keta is pittari, no amari happenes

print(a)

Submission status: Accepted

Solution code:
#E
#greedy 
n = input()
n = n[::-1] + "0"
l = len(n)

ans = 0

kuriagari=0

for i,v in enumerate(n):
    v = int(v)
    if kuriagari:
        v += 1
    
    if v<5:
        ans += v
        kuriagari = 0
    if v>5:
        ans += 10 - v
        kuriagari = 1
    if v==5:
        if int(n[i+1])<5:
            #delete is better
            ans += v
            kuriagari = 0
        if int(n[i+1])>=5:
            #kuriagari is promising
            ans += 10 - v
            kuriagari = 1
        
print(ans)

Submission status: Accepted

Solution code:
def main():
  N = input()
  N = '0'+N
  dp= [[float('inf') for _ in range(2)] for _ in range(len(N)+1)]
  dp[0][0] = 0
  for i in range(len(N)):
    n = int(N[len(N)-1-i])
    for j in range(2):
      # jが1のときは繰り下がりあり。
      # 引かれる数から1を引く代わりに、引く数xに1を足す。
      x = n+j
      # xが10のとき、必ず繰り下がりが起こる。
      if x < 10:
        dp[i+1][0] = min(dp[i+1][0],dp[i][j]+x)
      # xが0のとき、繰り下がりは起こせない。
      if x > 0:
        dp[i+1][1] = min(dp[i+1][1],dp[i][j]+10-x)
  print(dp[len(N)][0])  
  # print(dp)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n = list(input())
inf = 10**9
dp = [[inf for i in range(2)] for j in range(len(n) + 2)]
#dp[i][j] := 下からi桁目まで決めたときの、繰り下がりがjである。(true, false)
#ときの、最小紙幣数
n.reverse()
n += ['0']
#繰り下がりがない
dp[0][0] = 0
#配るDP
for i in range(len(n)):
    for j in range(2):
        x = int(n[i])
        #さっきの桁に繰り下がりをしている場合は、今回の数字が一つ減る。
        #んだけど、実際に払う数字は後で決めるから、今回は、引く側の数字を1大きく
        #することで、同じ操作を実現している
        x += j
        for a in range(10):
            #今回払う数字を決める
            if a >= x:
                #繰り下がりなし
                dp[i+1][0] = min(dp[i+1][0], dp[i][j] + 2 * a - x)
            else:
                #繰り下がりあり
                dp[i+1][1] = min(dp[i+1][1], dp[i][j] + 2 * a - x + 10)
print(min(dp[len(n)][0], dp[len(n)][1]))

Submission status: Accepted

Solution code:
n = input()

dp1 = [0] * (len(n) + 1)
dp2 = [1] * (len(n) + 1)

for i in range(1, len(n) + 1):
    m = int(n[i - 1])
    dp1[i] = min(dp1[i - 1] + m, dp2[i - 1] + 10 - m)
    dp2[i] = min(dp1[i - 1] + m + 1, dp2[i - 1] + 9 - m)

print(dp1[-1])

Submission status: Accepted

Solution code:
N = [int(_) for _ in list(input())]
a, b = 0, 1
for n in N:
    a, b = min(a+n, b+10-n), min(a+(n+1), b+10-(n+1))
print(a)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = list(map(int, "0"+input()))[::-1]
    l = len(n)
    dp = [n[0],10-n[0]]
    for i in range(1,l):
        ndp = [float("inf")]*2
        x = n[i]
        for j in range(2):
            x += j
            if x < 10:
                nd = dp[j]+x
                if nd < ndp[0]:
                    ndp[0] = nd
            if x > 0:
                nd = dp[j]+(10-x)
                if nd < ndp[1]:
                    ndp[1] = nd
        dp = [i for i in ndp]
    print(dp[0])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = [int(_) for _ in list(input())]
a, b = 0, 1
for n in N:
    a, b = min(a + n, b + 10 - n), min(a + (n + 1), b + 10 - (n + 1))
print(a)

Submission status: Accepted

Solution code:
string_n = input()
string_n = '0' + string_n
len_n = len(string_n)
dp = [[0, 0] for _ in range(len_n + 1)]

for i in range(len_n):
    for j in range(2):
        if j == 0:
            dp[i + 1][j] = min(dp[i]) + int(string_n[i])
        else:
            dp[i + 1][j] = min(dp[i][0] + 1 + 10 - int(string_n[i]), dp[i][1] + 9 - int(string_n[i]))

print(min(dp[len_n]))

Submission status: Accepted

Solution code:
S = input()
N = list(map(int,S))
L = len(N)

dp = [[0]*2 for i in [0]*(L+1)]
dp[0][1] = 1

for i in range(L):
    n = N[i]
    dp[i+1][0] = min(dp[i][0] + n, dp[i][1] + 10-n)
    if n == 9:
        dp[i+1][1] = dp[i][1]
    else:
        dp[i+1][1] = min(dp[i][0] + n + 1, dp[i][1] + 10 - (n+1))

print(dp[L][0])

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    N = list(map(int, args[0]))

    a, b = 0, 1
    for n in N:
        a, b = min(b+(10-n), a+n), min(b+(9-n), a+n+1)
    return str(a)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

N = input()

# TLE ()

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    for j in range(2):
        # 繰り下がりも加味
        n = int(N[i])
        n += j

        # 更新後のdp
        ni = i + 1

        # 同じだけ払う
        if n < 10:
            dp[ni][0] = min(dp[ni][0], dp[i][j] + n)
        else:
            dp[ni][1] = min(dp[ni][1], dp[i][j])

        # 繰り下がりあり
        if n > 0:
            dp[ni][1] = min(dp[ni][1], dp[i][j] + (10 - n))
        else:
            dp[ni][0] = min(dp[ni][0], dp[i][j])


ans = min(dp[L+1][0], dp[L+1][1])

print(ans)

Submission status: Accepted

Solution code:
"""
N = 3456の場合を例に取る。
支払い額もしくはお釣りの一方の1円玉の枚数は0が最適。
支払い枚数をf(N)で書くことにする。

(pay, change) = (...6, ...0)が最適の場合
10円以上で支払額とお釣り金額の差は3450円より、
    f(3456) = f(345) + 6
(pay, change) = (...0, ...4)が最適の場合
10円以上で支払額とお釣り金額の差は3460円より、
    f(3456) = f(346) + 4

つまり一般に
    f(3456) = min(f(345) + 6, f(346) + 4)
今回は再帰は10^6回で重いのでdpを行う。具体的には
    [f(3), f(4)]
    [f(34), f(35)] = [min(f(3)+4, f(4)+7), min(f(3)+5, f(4)+5)]
    [f(345), f(346)] = [min(f(34)+5, f(35)+5), min(f(34)+6, f(35)+4)]
の２ペアずつ値を保持して小さい方から計算すれば良い。
"""

strN = input()

# dp最初
n = int(strN[0])
dp = [min(n, 11 - n), min(n + 1, 11 - (n + 1))] # n == 9の場合も成立

for s in strN[1:]:
    n = int(s)
    dp = [min(dp[0] + n, dp[1] + (10 - n)), min(dp[0] + (n + 1), dp[1] + (10 - (n + 1)))]
    # 偶然、n == 0 or 9の場合もカバーできてる

print(dp[0])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = S()
dp = [[0] * 2 for _ in range(len(n))]
dp[0] = [int(n[-1]), 11 - int(n[-1])]
for i in range(1, len(n)):
    s = int(n[-i-1])
    dp[i][0] = s + min(dp[i - 1][0], dp[i - 1][1])
    dp[i][1] = min(11 - s + dp[i - 1][0], 9 - s + dp[i - 1][1])


print(min(dp[-1]))

Submission status: Accepted

Solution code:
#解説参照
#i桁目で10^i円多くはらうか否か

n_ =list(input())
n = [int(i) for i in n_]
ans = 0
if len(n_)==1:
    print(min(n[0],11-n[0]))
    exit()
dp1 = 0
dp2 = 1

for i in range(len(n)):
    dp_1 = min(dp1+n[i],dp2+10-n[i])
    dp_2 = min(dp1+n[i]+1,dp2+9-n[i])
    dp1 = dp_1
    dp2 = dp_2
print(dp1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 無限 #####
# inf = float('inf')

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')

def main():
	N = input()
	N = N[:-1]
	N = "0" + N
	N = N[::-1]

	dp = [[inf,inf] for i in range(len(N)+2)]
	dp[0][0] = 0
	#print(dp)

	cnt = 0
	for ii in N:
		i = int(ii)
		cnt += 1
		#print(dp)
		for j in range(10):
			if i > j:
				tmp = j + 10 - i
				dp[cnt][1] = min(dp[cnt][1], dp[cnt-1][0] + tmp + j)
			else:
				tmp = j - i
				dp[cnt][0] = min(dp[cnt][0], dp[cnt-1][0] + tmp + j)

			tmptmp = j-1
			if i > tmptmp:
				tmp = tmptmp + 10 - i
				dp[cnt][1] = min(dp[cnt][1], dp[cnt-1][1] + tmp + j)
			else:
				tmp = tmptmp - i
				dp[cnt][0] = min(dp[cnt][0], dp[cnt-1][1] + tmp + j)

	#print(dp)
	print(dp[len(N)][0])

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = input()
len_n = len(n)

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

for i in range(1, len_n+1):
    tmp = int(n[i-1])

    dp[i][0] = min(dp[i-1][0] + tmp, dp[i-1][1] + (10-tmp))
    dp[i][1] = dp[i-1][1] + (9-tmp)
    if(tmp != 9):
        dp[i][1] = min(dp[i][1], dp[i-1][0] + tmp + 1)

ans = min(dp[-1][0], dp[-1][1] + 1)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N="0"+raw_input()
l=len(N)

F=[ 0 for _ in range(l) ] #繰り上がりなし
T=[ 0 for _ in range(l) ] #繰り上がりあり
#初期化
x=int(N[l-1])
F[l-1]=x
T[l-1]=10-x

for i in range(l-1,0,-1):
    next_x=int(N[i-1])
    #繰上なしへの遷移。前の桁が繰上なしの場合は単に該当桁の数字を足す、
    #前の桁が繰上ありの場合は、今の桁の数字が1増える
    F[i-1]=min(F[i]+next_x, T[i]+next_x+1) 
    #繰上ありへの遷移。前の桁が繰上なしの場合は(10-該当桁の数字)を足す、
    #前の桁が繰上ありの場合は今の桁の数字が1増えているので(10-該当桁の数字+1)
    T[i-1]=min(F[i]+10-next_x, T[i]+10-(next_x+1))

print F[0]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N="0"+raw_input()
l=len(N)

F=[ 0 for _ in range(l) ] #繰り上がりなし
T=[ 0 for _ in range(l) ] #繰り上がりあり
#初期化
T[0]="N"
x=int(N[l-1])
F[l-1]=x
T[l-1]=10-x

for i in range(l-1,0,-1):
    next_x=int(N[i-1])
    F[i-1]=min(F[i]+next_x, T[i]+next_x+1)
    T[i-1]=min(F[i]+10-next_x, T[i]+10-(next_x+1))

print F[0]

Submission status: Accepted

Solution code:
N_list = [int(i) for i in list(input())]
N_list = N_list[::-1] + [0]

for index in range(0, len(N_list)):
  if N_list[index] >= 6 or (N_list[index] == 5 and N_list[index+1] >= 5) :
    N_list[index] = 10 - N_list[index]
    N_list[index+1] += 1

print(sum(N_list))

Submission status: Accepted

Solution code:
# e 数位dp 还可以从右到左
# 参考 https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2019-02-16abc-155
# https://atcoder.jp/contests/abc155/submissions/10155415
# in your code
import numpy as np
DBG=0
def p(*args, **kargs):
    if DBG:print(*args, **kargs)
read = input 
rn = lambda :list(map(int, read().split()))

def sol(s):
    dp = 0, 1 # n, n + 1
    for x in map(int, s):
        c, d = dp
    #                     为什么这里x = 0的时候不受影响 c+0 << d+10，因为abs(c-d) < 1
        
        #    前一位没借位  前一位借位
        a = min(c + x,    d + 10 - x)# for ...n
        #    这里x=9为什么不受影响, c+10 >> d，因为abs(c-d) < 1
        b = min(c + x + 1,d + 10 - 1 - x )# for ...(n+1)
        
        # 因为a,b相差小于1。f(n), f(n+1)相差总是小于1，多给1元即可
        dp = a,b
        p(dp)
    return dp[0]
if DBG:
    pass
#     sol("100")
#     assert 8 == sol("36")
#     assert sol("91") == 3
#     assert 243 == sol("314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170")
print(sol(read()))

Submission status: Accepted

Solution code:
#それぞれの桁を考えた時にその桁を一つ多めに払うのかちょうどで払うのかで場合分けする

n=[int(x) for x in list(input())]#それぞれの桁にアクセスするためにイテラブルにする
k=len(n)

#それぞれの桁を見ていくが、そのままと一つ多い状態から引く場合と二つあることに注意
dp=[[-1,-1] for _ in range(k)]
dp[0]=[min(1+(10-n[0]),n[0]),min(1+(10-n[0]-1),n[0]+1)]
for i in range(1,k):
    dp[i]=[min(dp[i-1][1]+(10-n[i]),dp[i-1][0]+n[i]),min(dp[i-1][1]+(10-n[i]-1),dp[i-1][0]+n[i]+1)]
print(dp[k-1][0])

Submission status: Accepted

Solution code:
N = input()[::-1]
L = len(N)
dp = [[0]*2 for _ in range(L+1)]
dp[0][1] = 10**18

for i in range(L):
    n = int(N[i])
    dp[i+1][0] = min(dp[i][0]+n, dp[i][1]+n+1)
    dp[i+1][1] = min(dp[i][0]+10-n, dp[i][1]+10-n-1)

print(min(dp[L][0], dp[L][1]+1))

Submission status: Accepted

Solution code:
S = input()
kuri = False
ans = 0
for i in range(len(S)-1, -1, -1):
    K = int(S[i])
    if kuri:
        K += 1
    kuri = False
    if K < 5:
        ans += K
    elif K > 5:
        ans += (10-K)
        kuri = True
    elif K == 5:
        if i > 0:
            M = int(S[i-1])
            if i != 0 and M >= 5:
                kuri = True
        ans += 5
    if i == 0 and kuri:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def get_result(data):
  N = data[0]
  # n円の場合、n+1円の場合
  dp = 0, 1
  for n in N:
      n = int(n)
      # N=123の1を考える
      # 100円を払うケース (1枚)
      # or 1000円払っていて + お釣り分の900円を払うケース (9枚)
      a = min(dp[0] + n, dp[1] + 10 - n)
      # 200円を払うケース (2枚) 
      # or 1000円払っていて + お釣り分の800円を払うケース (8枚, 下の桁によって減るケース)
      b = min(dp[0] + n + 1, dp[1] + 10 - (n + 1))
      dp = a, b
  return dp[0]

if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip('\n').split(' ')))
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
N = [int(i) for i in input()]
n = N[::-1]+[0]
for i in range(len(n)-1):
    if n[i] >= 6 or (n[i] == 5 and n[i+1] >= 5):
        n[i] = 10 - n[i]
        n[i+1] += 1
print(sum(n))

Submission status: Accepted

Solution code:
N = [int(i) for i in input()]
n = N[::-1]+[0]
for i in range(len(n)-1):
    if n[i] >= 6 or (n[i] == 5 and n[i+1] >= 5):
        n[i] = 10 - n[i]
        n[i+1] += 1
print(sum(n))

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))[::-1]
dp0 = [float('inf')] * (len(N)+1)
dp1 = [float('inf')] * (len(N)+1)
dp0[0] = 0
dp1[0] = 1
for i in range(len(N)):
    dp0[i+1] = min(dp0[i] + N[i], dp1[i] + 10 - N[i])
    dp1[i+1] = min(dp0[i] + N[i] + 1, dp1[i] + 9 - N[i])
print(dp0[-1])

Submission status: Accepted

Solution code:
N = [int(i) for i in input()]
n = N[::-1]+[0]

for i in range(len(n)-1):
    if n[i] >= 6 or (n[i] == 5 and n[i+1] >= 5):
        n[i] = 10 - n[i]
        n[i+1] += 1

    
print(sum(n))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 引かれる数の左からi桁目に+10 & 引く数のi-1桁目に+1 を適宜行う

def calc(x):
    if 0 <= x <= 5:
        return x
    else:
        return 10-x+1

S = list(input())
L = len(S)

dp0 = [0]*L
dp1 = [0]*L
dp0[0] = calc(int(S[0]))
dp1[0] = calc(int(S[0])+1)

for i in range(1,L):
    n = int(S[i])
    if n == 0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = min(dp0[i-1]+n, dp1[i-1]+10-n)
    if n == 9:
        dp1[i] = dp1[i-1]
    else:
        dp1[i] = min(dp0[i-1]+n+1, dp1[i-1]+9-n)

print(dp0[-1])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    N = S()[::-1] + '0'
    dp = [[0 for _ in range(2)] for _ in range(len(N)+1)]
    dp[0][1] = inf
    for d_i in range(len(N)):
        digit = int(N[d_i])
        i = d_i + 1
        dp[i][0] = min(
            dp[i-1][0] + digit,
            dp[i-1][1] + digit + 1,
        )
        dp[i][1] = min(
            dp[i-1][0] + (10 - digit),
            dp[i-1][1] + (10 - (digit + 1))
        )
    print(dp[len(N)][0])

main()

Submission status: Accepted

Solution code:
def e_payment_greedy():
    N = [int(i) for i in list(input())]
    s = N[::-1] + [0]  # [-d-1]: 最終的に 10**d 円札を何枚受渡ししたかが格納される

    for i in range(len(N)):
        if s[i] >= 6 or (s[i] == 5 and s[i + 1] >= 5):
            s[i] = 10 - s[i]
            s[i + 1] += 1
    return sum(s)

print(e_payment_greedy())

Submission status: Accepted

Solution code:
def e_payment():
    N = input()

    dp = (0, 1)  # 「最下位桁の 1 つ下の桁」を仮想した場合分けを省くための初期化
    for k, ch in enumerate(N[::-1]):  # 最下位の桁から見る
        n = int(ch)
        t1, t2 = dp
        a = min(t1 + n, t2 + n + 1)
        b = min(t1 + (10 - n), t2 + (10 - (n + 1)))
        dp = (a, b)
    return min(dp[0], dp[1] + 1)

print(e_payment())

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
inf = 10 **9 + 5
def main():
    s = str(input())
    s = s[::-1]
    dp1 = [inf] *(10 ** 6 +3)
    dp2 = [inf] *(10 ** 6 +3)
    dp1[0] = int(s[0])
    dp2[0] =  10 -int(s[0])
    for i in range(1,len(s)):
        dp1[i] = min(dp2[i-1] + int(s[i]) + 1,dp1[i-1] + int(s[i]))
        dp2[i] = min(dp2[i-1] + 9 - int(s[i]),dp1[i-1] + 10 - int(s[i]))
    print(min(dp1[len(s)-1],dp2[len(s)-1] + 1))

main()

Submission status: Accepted

Solution code:
N = reversed("0" + input())
digit = next(N)
total = 0
carry = 0
for nextdigit in N:
    digit = int(digit) + carry
    if digit < 5:
        total += digit
        carry = 0
    elif digit == 5:
        if int(nextdigit) < 5:
            total += digit
            carry = 0
        else:
            total += 10 - digit
            carry = 1
    else:
        total += 10 - digit
        carry = 1
    digit = nextdigit

print(total + carry)

Submission status: Accepted

Solution code:
def solve():
    def min2(x, y): return x if x <= y else y

    strN = '0' + input()

    Ns = list(map(int, strN))

    dp = [0, float('inf')]
    for Ni in reversed(Ns):
        dp2 = [0, 0]
        if Ni == 9:
            dp2[0] = dp[0] + Ni
        else:
            dp2[0] = min2(dp[0] + Ni, dp[1] + Ni + 1)
        dp2[1] = min2(dp[0] + 10 - Ni, dp[1] + 9 - Ni)
        dp = dp2

    print(dp[0])


solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = [int(x) for x in input().rstrip()][::-1] + [0]
L = len(N)

dp = [[10 ** 18, 10 ** 18] for _ in range(L + 1)]
dp[0] = [0, 0]
dp[1] = [N[0], 10 - N[0]]

for i in range(2, L + 1):
    n = N[i - 1]
    dp[i][0] = min(dp[i - 1][0] + n, dp[i - 1][1] + (n + 1))
    dp[i][1] = min(dp[i - 1][0] + (10 - n), dp[i - 1][1] + (10 - (n + 1)))

print(dp[-1][0])

Submission status: Accepted

Solution code:
n=list(input())
lis=[]
for k in range(len(n)):
  lis.append(int(n[len(n)-1-k]))
             
t=0

for k in range(len(lis)):
  if lis[k]==10:
    if k==len(lis)-1:
      t+=1
      break
    else:
      lis[k]=0
      lis[k+1]+=1
  if lis[k]<5:
    t+=lis[k]
  elif lis[k]>5:
    t=t+10-lis[k]
    if k==len(lis)-1:
        t+=1
        break
    else:
        
      lis[k+1]+=1
  elif lis[k]==5:
    if k==len(lis)-1:
      t+=5
    else:
      t+=5
      if lis[k+1]<5:
        pass
      else:
        lis[k+1]+=1
print(t)

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))

dp=[[-1,-1] for i in range(len(N)+1)]
dp[0]=[0,1]
b=0
N.insert(0,0)

for i in range(1,len(N)):
    up = 10-N[i]
    dp[i][0]=min(dp[i-1][0]+N[i],dp[i-1][1]+up)
    dp[i][1] = min(dp[i-1][0]+N[i]+1, dp[i-1][1]+up-1)
   

print(dp[-1][0])

Submission status: Accepted

Solution code:
s = input()

ans = 0
carry = 0
for i in range(len(s) - 1, -1, -1):
    c = int(s[i])
    if c + carry < 5:
        ans += c + carry
        carry = 0
    elif c + carry == 5:
        if i > 0 and int(s[i - 1]) >= 5:
            ans += 5
            carry = 1
        else:
            ans += 5
            carry = 0
    else:
        ans += 10 - c - carry
        carry = 1
if carry:
    ans += 1
print(ans)