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

Solution (Python):
N = input()
dp = [[0]*2 for _ in range(1001000)]
dp[0][1] = 1
for i in range(len(N)):
    d = int(N[i])
    dp[i+1][0] = min(dp[i][0] + d, dp[i][1] + 10-d)
    dp[i+1][1] = min(dp[i][0] + d + 1, dp[i][1] + 10-d-1)  
ans = dp[len(N)][0]
print(ans)

Solution (Python):
N = input()
dp = [[0]*2 for _ in range(1001000)]
dp[0][1] = 1
for i in range(len(N)):
    d = int(N[i])
    dp[i+1][0] = min(dp[i][0] + d, dp[i][1] + 10-d)
    dp[i+1][1] = min(dp[i][0] + d + 1, dp[i][1] + 10-d-1)  
ans = dp[len(N)][0]
print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    NS=(input().strip("\n"))[::-1]
    dp=[[0]*2 for i in range(len(NS))]
    
    dp[0][0]=int(NS[0])
    dp[0][1]=10-int(NS[0])
    for i in range(1,len(NS)):
        d=int(NS[i])
        dp[i][0]=min(dp[i-1][0]+d,dp[i-1][1]+d+1)
        dp[i][1]=min(dp[i-1][0]+10-d,dp[i-1][1]-1+10-d)
    dp[-1][1]+=1
    print(min(dp[-1]))
    
if __name__=="__main__":
    main()

Solution (Python):

def resolve():
    S = input()
    n = len(S)
    dp = [[0] * 2 for _ in range(n + 1)]
    dp[0][1] = 1
    for i in range(1, n + 1):
        d = int(S[i - 1])
        dp[i][0] = min(dp[i - 1][0] + d, dp[i - 1][1] + (10 - d))
        dp[i][1] = min(dp[i - 1][0] + (d + 1), dp[i - 1][1] + (10 - 1 - d))
    print(dp[n][0])


if __name__ == "__main__":
    resolve()

Solution (Python):
N=[int(c) for c in input()][::-1]

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

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

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

Solution (Python):
def main():
    N = "0" + input()
    N = list(map(int, N[::-1]))
    ans = 0
    up = 0
    for i, n in enumerate(N):
        d = n + up
        
        if d > 5 or (i < len(N) - 1 and d == 5 and N[i + 1] >= 5):
            ans += 10 - d  
            up = 1
        
        else:
            ans += d  
            up = 0
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N=input()
N=N[::-1]+"0"
ans=0
up=0
for i,n in enumerate(N):
  d=int(n)+up
  if d>5 or (d==5 and i<len(N)-1 and int(N[i+1])>=5):
    ans+=(10-d)
    up=1
  else:
    ans+=d
    up=0
print(ans)

Solution (Python):
n = input()
n = n[::-1] + '0'
inf = 10 ** 9
dp = [[inf for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0] = 0
dp[0][1] = 2
for i in range(len(n)):
        n_i = int(n[i])
        dp[i + 1][0] = min(dp[i][0] + n_i, dp[i][1] + n_i)
        dp[i + 1][1] = min(dp[i][0] + 11 - n_i, dp[i][1] + 9 - n_i)
print(min(dp[-1][0], dp[-1][1]))

Solution (Python):
def main():
    S = list( map( int, list( input())))
    N = len(S)
    dp = [[0,0] for _ in range(N+1)]
    dp[0][1] = 2
    for i in range(N):
        s = S[i]
        dp[i+1][0] = min(dp[i][0] + s, dp[i][1]+s)
        dp[i+1][1] = min(dp[i][0] + 11-s, dp[i][1]+9-s)
        
        
        
    print( min(dp[N][0], dp[N][1]))
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    S = list( map( int, list( input())))
    N = len(S)
    dp = [[0,0] for _ in range(N+1)]
    dp[0][1] = 2
    for i in range(N):
        s = S[i]
        dp[i+1][0] = min(dp[i][0] + s, dp[i][1]+s)
        dp[i+1][1] = min(dp[i][0] + 11-s, dp[i][1]+9-s)
        
        
        
    print( min(dp[N][0], dp[N][1]))
if __name__ == '__main__':
    main()

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    L = list(map(int, reversed(li())))
    n = len(L)
    payment = L[:]
    payment.append(0)

    ans = 0
    carry = False
    for i in range(n):
        if 5 < payment[i] or (5 == payment[i] and 5 <= payment[i+1]):
            ans += 9 - L[i] if carry else 10 - L[i]
            payment[i] = 0
            payment[i+1] += 1
            carry = True
        else:
            carry = False
    
    
    
    ans += sum(payment)
    

    
    

    
    
    
    

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
N = input()
N = N[::-1]+"0"
ans = 0
up = 0
for i,n in enumerate(N):
    d = int(n)+up
    if 5 < d or (d == 5 and i < len(N)-1 and int(N[i+1]) >= 5):
        ans += (10-d)
        up = 1
    else:
        ans += d
        up = 0
print(ans)

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().rstrip()  


N = ns()

ans = [0, 1000000000]
kuri = [0, 0]
five = 0
for n in N[::-1]:
    n = int(n)
    
    ans_old = [ans[0], ans[1]]
    ans[0] = min(ans_old[0] + n, ans_old[1] + n + 1)
    ans[1] = min(ans_old[0] + 10 - n, ans_old[1] + 9 - n)
print(min(ans[0], ans[1] + 1))

Solution (Python):
N=input()
N='0'+N
M=len(N)
INF=10**12
DP1=[INF]*(M+1)
DP2=[INF]*(M+1)
DP1[0]=0
for i in range(M):
  DP1[i+1]=min(DP1[i]+int(N[i]),DP2[i]+10-int(N[i]))
  DP2[i+1]=min(DP1[i]+int(N[i])+1,DP2[i]+9-int(N[i]))
print(min(DP1[M],DP2[M]+1))

Solution (Python):
s = "0"+input()
ans = 0
n = len(s)
f = 0
p = 0
for i in range(1,n+1):
    n = int(s[-i])
    
    if p+(n>4) > 5:
        f = 1
    else:
        
        f = 0
    n += f
    ans += min(n,10-n)
    p = n

print(ans)

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

ans = 0
carry = 0   
for i in range(len(N) - 1, -1, -1):
    if carry == 2:
        if N[i] >= 5:
            digit = N[i] + 1
            carry = 1
            ans += (10 - digit)
        else:
            digit = N[i]
            carry = 0
            ans += digit
    else:
        digit = N[i] + carry
        if digit >= 6:
            carry = 1
            ans += (10 - digit)
        elif digit <= 4:
            carry = 0
            ans += digit
        else:
            carry = 2
            ans += digit
        

if carry == 1:
    ans += carry

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)

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

ans = 0
dp1 = [0]*(n+1)
dp0 = [0]*(n+1)

dp1[0] = 1

for i in range(n):
  k = int(s[i])
  if k < 5:
    dp0[i+1] = dp0[i] + k
  elif k > 5:
    dp0[i+1] = dp1[i] + 10-k
  else:
    if i == 0:
      dp0[i+1] = dp0[i] + k
    elif int(s[i-1]) < 5:
      dp0[i+1] = dp0[i] + k
    else:
      dp0[i+1] = dp1[i] + 10-k
  k += 1
  if k == 10:
    dp1[i+1] = dp1[i]
  elif k < 5:
    dp1[i+1] = dp0[i] + k
  elif k > 5:
    dp1[i+1] = dp1[i] + 10-k
  else:
    if i == 0:
      dp1[i+1] = dp0[i] + k
    elif int(s[i-1]) < 5:
      dp1[i+1] = dp0[i] + k
    else:
      dp1[i+1] = dp1[i] + 10-k

print(dp0[n])

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

ans = 0

sub = 0
judge = False
for i in range(n-1, -1, -1):
  key = int(s[i])+sub
  if key <= 4:
    ans += key
    sub = 0
  elif key == 5:
    ans += 5
    if i == 0:
      sub = 0
    elif int(s[i-1]) <= 4:
      sub = 0
    else:
      sub = 1
  else:
    ans += 10-key
    sub = 1
ans += sub
print(ans)

Solution (Python):

import sys
INF = float("inf")


def solve(N: str):
    
    N = "0" + N
    ans = 0
    kuriagari = 0
    for i in reversed(range(len(N))):
        n = int(N[i])
        if kuriagari == 1:
            kuriagari = 0
            n += 1
        if 0 <= n <= 4:
            ans += n
        elif n == 5:
            
            k = i-1
            if 0 <= int(N[k]) <= 4:
                
                ans += 5
            else:
                
                ans += 5
                kuriagari = 1
        else:
            ans += 10 - n
            kuriagari = 1
        
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)
    N = str(a)  
    solve(N)


if __name__ == '__main__':
    main()

Solution (Python):
s = input()
s = "".join([ i for i in reversed(s)]) + "0"
 
INF = 10 ** 32
n = len(s)
dp = [ [INF]*2 for _ in range(n)]
 
dp[0][0] = 0
 
for i in range(n-1):
    x = int(s[i])
    dp[i+1][0] = min( dp[i][0]+x, dp[i][1]+x )
    dp[i+1][1] = min( dp[i][0]+1+(10-x), dp[i][1]+(9-x) )
 
print(min(dp[n-1][0], dp[n-1][1]))

Solution (Python):
import sys

def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  

N = [0] + LI2()
n = len(N)

dp1 = [0]*(n)
dp2 = [0]*(n)






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

print(dp1[n-1])

Solution (Python):
s = input()[::-1]
size = len(s)
s += "4"

a, b = 0, 0

for i in range(size):
    v1, v2 = int(s[i]), int(s[i+1])
    if v1+b>=6 or (v1+b>=5 and v2>=5):
        a += 10-v1-b
        b = 1
    else:
        a += v1+b
        b = 0

print(a+b)

Solution (Python):
s = input()[::-1]
size = len(s)
s += "4"

ans = 0
bef = 0

for i in range(size):
    v1 = int(s[i])
    v2 = int(s[i+1])
    if v1+bef>=6 or (v1+bef>=5 and v2>=5):
        ans += 10-(v1+bef)
        bef = 1
    else:
        ans += (v1+bef)
        bef = 0

ans += bef
print(ans)

Solution (Python):
s = input()[::-1]
size = len(s)
s += "4"

ans = 0
bef = 0

for i in range(size):
    v1 = int(s[i])
    v2 = int(s[i+1])
    if v1+bef>=6 or (v1+bef>=5 and v2>=5):
        ans += 10-(v1+bef)
        bef = 1
    else:
        ans += (v1+bef)
        bef = 0

ans += bef
print(ans)

Solution (Python):
s = str(input())
n = len(s)
dp = [[0]*2 for _ in range(n+1)]
dp[0][1] = 1
for i in range(n):
    p = int(s[i])
    dp[i+1][0] = min(dp[i][1]+10-p,dp[i][0]+p)
    dp[i+1][1] = min(dp[i][1]+10-p-1,dp[i][0]+p+1)
print(dp[-1][0])

Solution (Python):
s = str(input())
n = len(s)
dp = [[0]*2 for _ in range(n+1)]
dp[0][1] = 1
for i in range(n):
    p = int(s[i])
    dp[i+1][0] = min(dp[i][1]+10-p,dp[i][0]+p)
    dp[i+1][1] = min(dp[i][1]+10-p-1,dp[i][0]+p+1)
print(dp[-1][0])

Solution (Python):
n=list(map(int,list(input())))


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

nrev=n[::-1]
nrev.append(0)
dp[0][0]=nrev[0]
dp[0][1]=10-nrev[0]

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

print(min(dp[-1]))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = S()
    a = [int(c) for c in s]

    dp = [0, 1]
    for c in a:
        np = [dp[0] + c, dp[0] + c + 1]
        if np[0] > dp[1] + (10 - c):
            np[0] = dp[1] + (10 - c)
        if np[1] > dp[1] + (9 - c):
            np[1] = dp[1] + (9 - c)
        dp = np

    return dp[0]

print(main())

Solution (Python):
def main():
    N = list(map(int, list(input())))
    N = N[::-1] + [0]

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

    print(ans + N[len(N)-1])

main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[:-1])))
    N = N[::-1] + [0]

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

    print(ans + N[len(N)-1])

main()

Solution (Python):
s=input()[::-1]+'0'
d=[0,1]
for c in s:
    x=int(c)
    d=[x+min(d[0],1+d[1]),min(1+d[0],d[1])+9-x]
print(min(d))

Solution (Python):
N = [0] + list(map(int, list(input())))
L = len(N)
ans = 0
for i in range(L-1, -1, -1):
    if N[i] == 10:
        if i == 0:
            ans += 1
        else:
            N[i-1] += 1
            N[i] = 0
    if N[i] < 5:
        ans += N[i]
    elif N[i] > 5:
        ans += 10 - N[i]
        N[i-1] += 1
    else:
        if i == 0:
            ans += N[i]
        else:
            if N[i-1] >= 5:
                N[i-1] += 1
                ans += 5
            else:
                ans += N[i]

print(ans)

Solution (Python):
n = input()
x = len(n)
inf = 10 ** 9

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

print(dp[x][0])

Solution (Python):
n = input()
l = list(map(int, str(n)))

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

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

print(dp[-1][0])

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = LSI()
dp = [[INF]*2 for _ in range(len(N)+1)] 
dp[0][0] = 0
for i in range(len(N)):
    d = N[-(i+1)]
    dp[i+1][0] = min(dp[i][0] + d, dp[i][1] + d + 1)
    dp[i+1][1] = min(dp[i][0] + (10-d), dp[i][1] + (10-d) - 1)
print(min(dp[-1][0], dp[-1][1]+1))

Solution (Python):
s = input()
keta = len(s)
infi = 10 ** 10
dp = [[infi] * (2) for _ in range(keta + 1)]
dp[0][0] = 0
s = s[::-1]
for i in range(keta):
    for j in range(2):
        num = int(s[i])
        if j == 1:
            num += 1
        ni = i + 1
        if num == 10:
            nj = 1
            num = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num < 5:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num > 5:
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
        else:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
print(min(dp[keta][0], dp[keta][1] + 1))

Solution (Python):
s = "0" + input()
keta = len(s)
dp = [0] * (keta + 1)
kuri = 0
for i in range(keta):
    ni = i + 1
    num = int(s[-i - 1])
    if kuri:
        num += 1
        kuri = 0
    if num == 10:
        kuri = 1
        dp[ni] = dp[i]
    elif num < 5:
        dp[ni] = dp[i] + num
    elif num > 5:
        num %= 10
        kuri = 1
        dp[ni] = dp[i] + 10 - num
    else:
        nn = int(s[-ni - 1])
        if nn < 5:
            dp[ni] = dp[i] + num
        else:
            kuri = 1
            dp[ni] = dp[i] + 10 - num
print(dp[keta] + kuri)

Solution (Python):

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

Solution (Python):
S = input()
L = len(S)

dp = [[0 for _ in range(L + 1)] for over in range(2)]
dp[0][0] = 0
dp[1][0] = 1

for j, s in enumerate(S, 1):
    n = int(s)
    dp[0][j] = min(dp[0][j - 1] + n, dp[1][j - 1] + (10 - n))
    dp[1][j] = min(dp[0][j - 1] + (n + 1), dp[1][j - 1] + (10 - n - 1))
    
print(dp[0][-1])

Solution (Python):
N = input()
INF = 10 ** 9
N = N[::-1] + '0'
dp = [[INF for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0] = 0

for i in range(len(N)):
    for j in range(2):
        x = int(N[i])
        x += j
        for k in range(10):
            nexti = i + 1
            nextj = 0
            b = k - x
            if b < 0:
                nextj = 1
                b += 10
            dp[nexti][nextj] = min(dp[nexti][nextj], dp[i][j] + k + b)
print(dp[len(N)][0])

Solution (Python):
import collections
s = map(int,list(raw_input()))
qa = collections.deque([0])
qb = collections.deque([1])
for i in range(len(s)):
	qa.append(min(qa[0] + s[i], qb[0] + 10 - s[i]))
	qb.append(min(qa[0] + s[i] + 1, qb[0] + 10 - s[i] - 1))
	qa.popleft()
	qb.popleft()

print qa[-1]

Solution (Python):
s = map(int,list(raw_input()))
dp = [[0,0] for _ in range(len(s))]
for i in range(len(dp)):
	a = (dp[i - 1][0] if i - 1 >= 0 else 0) + s[i]
	b = (dp[i - 1][1] if i - 1 >= 0 else 1) + 10 - s[i]
	dp[i][0] = min(a,b)

	a = (dp[i - 1][0] if i - 1 >= 0 else 0) + s[i] + 1
	b = (dp[i - 1][1] if i - 1 >= 0 else 1) + 10 - s[i] - 1
	dp[i][1] = min(a,b)
print dp[-1][0]

Solution (Python):
n=list(map(int,input()))
keta=len(n)
satsu=0

for i in range(keta):
    tmp = n.pop()
    if i == keta-1:
        n.append(0)
    
    if tmp == 10:
        tmp=0
        n[-1]=n[-1]+1
    if tmp > 5 or (tmp==5 and n[-1] >= 5):
        satsu += 10 - tmp
        n[-1] = n[-1] + 1
    else:
        satsu += tmp

print(satsu+n[0])

Solution (Python):
N="0"+input()
N=N[::-1]
DP=[[0,0]for i in range(len(N))]

DP[0][0]=int(N[0])
DP[0][1]=10-int(N[0])



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

print(min(DP[-1]))

Solution (Python):
N = [int(c) for c in input()]
dp = 0,1
for n in N:
  a = min(dp[0]+n,dp[1]+10-n)
  b = min(dp[0]+n+1,dp[1]+10-(n+1))
  dp = a,b
print(dp[0])

Solution (Python):
'''
提出
'''

L = list(map(int,list(input())))
L = [0] + L
N = len(L)
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]

for i in range(N):
    dp1[i+1] = min(dp1[i] + L[i], dp2[i] + 10 - L[i])
    dp2[i+1] = min(dp2[i] + 10 - L[i] - 1, dp1[i] + L[i] + 1)

print(dp1[-1])

Solution (Python):

import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**7)

def run():
    N = list(map(int, list(input())))
    N = N[::-1] + [0]
    count = 0
    seq = 0
    for idx, n in enumerate(N[:]):
        if seq == 1 and (n >= 5 or (n == 4 and N[idx+1] >= 5)):
            count += 9 - n
        elif seq == 0 and (n >= 6 or (n == 5 and N[idx+1] >= 5)):
            count += 10 - n
            seq = 1
        else:
            count += n + seq
            seq = 0
    print(count)

if __name__ == "__main__":
    run()

Solution (Python):


s = input()
d0 = [0,1,2,3,4,5,6,7,8,9]
d1 = [0,1,2,3,4,5,5,4,3,2] 

a0 = d1[int(s[0])]
a1 = d1[int(s[0]) + 1] if int(s[0])<=8 else 1

for c in s[1:]:
    c = int(c)
    b0 = min(a0 + c, a1 + (10 - c))
    b1 = min(a0 + c + 1, a1 + (9 - c)) if c <=8 else a1
    a0, a1 = b0, b1
    
print(a0)

Solution (Python):
N=input()
L=len(N)
ans=[[0 for e in range(2)] for f in range(L)]
ans[0][0]=int(N[L-1])
ans[0][1]=10-int(N[L-1])
if L>1:
 for i in range(1,L):
  ans[i][0]=min(ans[i-1][0]+int(N[L-1-i]),ans[i-1][1]+int(N[L-1-i])+1)
  ans[i][1]=min(ans[i-1][0]+10-int(N[L-1-i]),ans[i-1][1]+10-int(N[L-1-i])-1)
print(min(ans[L-1][0],ans[L-1][1]+1))

Solution (Python):
N=input()
L=len(N)
ans=[[0 for e in range(2)] for f in range(L)]
k=int(N[L-1])
ans[0][0]=k
ans[0][1]=10-k
if L>1:
 for i in range(1,L):
  k=int(N[L-1-i])
  ans[i][0]=min(ans[i-1][0]+k,ans[i-1][1]+k+1)
  ans[i][1]=min(ans[i-1][0]+10-k,ans[i-1][1]+10-k-1)
print(min(ans[L-1][0],ans[L-1][1]+1))

Solution (Python):
N = input()
L=len(N)

DP=[[N]*2 for _ in range(L+1)]
DP[0][0]=0
DP[0][1]=1

for i,n in enumerate(N,1):
    DP[i][0]= min(DP[i-1][0]+int(n),DP[i-1][1]+10-int(n))
    DP[i][1] = min(DP[i-1][0]+int(n)+1,DP[i-1][1]+9-int(n))

print(DP[L][0])

Solution (Python):
L = list(map(int,list(input())))
L = [0] + L
N = len(L)
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]

for i in range(N):
    dp1[i+1] = min(dp1[i] + L[i], dp2[i] + 10 - L[i])
    dp2[i+1] = min(dp2[i] + 10 - L[i] - 1, dp1[i] + L[i] + 1)

print(dp1[-1])

Solution (Python):
N = input()
n = len(N)
dp = [[0,0]for i in range(0,n,1)]

dp[n-1][0] = int(N[n-1])
dp[n-1][1] = int(10 - int(N[n-1]) + 1 )

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

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

Solution (Python):
s = input()

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+10-int(s[i]), dp[i][1]+int(s[i])+1)
    dp[i+1][1] = min(dp[i][0]+int(s[i])+1,dp[i][1]+10-int(s[i])-1)

print(dp[-1][0])

Solution (Python):
s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    n = list(input().rstrip())
    n = [0] + n
    n = n[::-1]
    ln = len(n)
    res = 0
    a = 0
    for i in range(ln):
        s = int(n[i])
        s += a
        if 0<=s<=4:
            res += s
            a = 0
        elif 6<=s:
            res += 10-s
            a = 1
        else:
            if int(n[i+1])>=5:
                res += 10-s
                a = 1
            else:
                res += s
                a = 0
            
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
n=[int(x) for x in input()]

dp=[[100000000000 for i in range(len(n)+1)]for j in range(2)]
dp[0][0]=0
dp[1][0]=1
for i in range(len(n)):
  d=n[i]
  dp[0][i+1]=min(dp[0][i+1],min(d,11-d)+dp[0][i],10-d+dp[1][i])
  dp[1][i+1]=min(dp[1][i+1],d+1+dp[0][i],9-d+dp[1][i])
  
  
print(dp[0][len(n)])

Solution (Python):
n=input()[::-1]
n+="0"
lt=len(n)
dp=[[float('inf') for _ in range(2)] for j in range(lt+1)]
dp[0][0]=0

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

print(dp[lt][0])

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = sr()
dp = [0, 1]  
for x in N:
    x = int(x)
    prev = dp[:]
    dp[0] = min(prev[0]+x, prev[1]+(10-x))
    dp[1] = min(prev[0]+x+1, prev[1]+(10-x-1))

answer = dp[0]
print(answer)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = sr()
dp = [0, 1]  
for x in N:
    x = int(x)
    prev = dp[:]
    dp[0] = min(prev[0]+x, prev[1]+(10-x))
    dp[1] = min(prev[0]+x+1, prev[1]+(10-x-1))

answer = dp[0]
print(answer)

Solution (Python):
s=input()
dp0=[0]*(len(s)+1)
dp1=[0]*(len(s)+1)
dp1[0]=1
for i in range(1,len(s)+1):
  n=int(s[i-1:i])
  dp0[i]=min(dp0[i-1]+n,dp1[i-1]+10-n)
  dp1[i]=min(dp0[i-1]+(1 if n+1==10 else n+1),dp1[i-1]+10-n-1)
print(dp0[-1])

Solution (Python):



def main():
    a = [0]
    a += map(int, input())
    a.reverse()

    n = len(a)
    b = a.copy()

    for i in range(n):
        if b[i] > 5 or (b[i] == 5 and b[i + 1] >= 5):
            b[i] = 0
            b[i + 1] += 1

    cnt = sum(b)
    for i in range(n):
        if a[i] > b[i]:
            b[i] += 10
            b[i + 1] -= 1
        cnt += b[i] - a[i]
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    *e, = map(int, input())
    e.reverse()

    inf = 20 * len(e)

    dp = [0, inf]  

    for x in e:
        ndp = [-1, -1]  

        ndp[0] = min(
            dp[0] + x,
            dp[1] + ((x + 1) if x < 9 else inf)  
        )  

        ndp[1] = min(
            dp[0] + ((10 - x) if x > 0 else inf),  
            dp[1] + (10 - (x + 1))
        )  

        dp = ndp

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


if __name__ == '__main__':
    main()

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


ans = 0
DP = [0] *2
DP[0] = 0
DP[1] = 1
for i in N:
    a, b = DP[0] ,DP[1]
    DP[0] = a + i if a+i < b +(10-i) else b +(10-i)
    DP[1] = a + i+1 if a + i+1 < b + (9-i) else b + (9-i)

    

print(DP[0] if DP[0] <= DP[1]+1 else DP[1] +1)

Solution (Python):
n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    a = c
    ret[0][0] = min(ret[0][0], a)
    b = 10 - c
    if b < 10:
        ret[0][1] = min(ret[0][1], b)
    a = c + 1
    if a < 10:
        ret[1][0] = min(ret[1][0], a)
    b = 9-c
    ret[1][1] = min(ret[1][1], b)

    return ret


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

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

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

Solution (Python):
n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    
    
    
    
    
    
    
    
    
    
    for b in range(10):
        a = c + b
        if 0 <= a < 10:
            ret[0][0] = min(ret[0][0], a+b)
        a = c + b - 10
        if 0 <= a < 10:
            ret[0][1] = min(ret[0][1], a+b)
        a = c + b + 1
        if 0 <= a < 10:
            ret[1][0] = min(ret[1][0], a + b)
        a = c + b - 10 + 1
        if 0 <= a < 10:
            ret[1][1] = min(ret[1][1], a + b)
    return ret


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

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

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

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  









N = '0' + read()[:-1]
pre_is_kuriagari = False
dp1 = int(N[0])
dp2 = dp1 + 1
for i in ra(1, len(N)):
    n = int(N[i])
    
    oturi = dp2 + (10 - n)
    pay = dp1 + n
    dp1_new = min(oturi, pay)

    
    oturi = dp2 + (10 - (n + 1))
    pay = dp1 + n + 1
    dp2_new = min(oturi, pay)
    dp1, dp2 = dp1_new, dp2_new
print(dp1)