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












'''
def F(n: int):
    if n < 5:
        
        return n
    a, b = divmod(n, 10)
    ret = min(F(a) + b, F(a + 1) + (10 - b))
    
    return ret


print(F(int(input())))
'''






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)

Solution (Python):












'''
def F(n: int):
    if n < 5:
        
        return n
    a, b = divmod(n, 10)
    ret = min(F(a) + b, F(a + 1) + (10 - b))
    
    return ret


print(F(int(input())))
'''






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)

Solution (Python):
def solve(n):
    n = list(map(int, n))
    a, b = 0, 9
    for d in n:
        a, b = min(d+a, d+b), min(11-d+a, 9-d+b)
    return min(a, b)

assert solve("36") == 8
assert solve("91") == 3
assert solve("314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170") == 243

n = input()
print(solve(n))

Solution (Python):


S = input()
N = len(S)


dp = [0]
dp_plus1 = [1]

for i in range(N):
    x = int(S[i])
    dp.append(min(dp[i] + x, dp_plus1[i] + (10 - x)))
    dp_plus1.append(min(dp[i] +  (x + 1), dp_plus1[i] + (10 -  (x + 1))))

print(dp[-1])

Solution (Python):
INF = 10**18

S = '0'+input()
N = len(S)

dp = [[INF,INF] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(2):
        s = int(S[-1-i])
        s += j

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

print(dp[N][0])

Solution (Python):
list_n=[0]+list(map(int,input()))
l = len(list_n)

pay=0
back=0
for i in range(l-1,-1,-1):
    
    now = list_n[i]
    if now in [0,1,2,3,4] or (now == 5 and list_n[i-1]<5):
        pay+=now
        list_n[i]=0
    elif now in [6,7,8,9] or (now == 5 and list_n[i-1]>=5):
        back+=10-now
        list_n[i]=0
        list_n[i-1] +=1
    elif now==10:
        list_n[i]=0
        list_n[i-1] +=1
print(pay+back)

Solution (Python):
import sys

n=sys.stdin.readline().rstrip()[::-1]
to=0

m=0
n+="0"
num=len(n)

for i in range(num):
    k=int(n[i])
    k+=m
    if k==5:
        if int(n[i+1])>=5:
            to+=10-k
            m=1
        else:
            to+=k
            m=0
    if k<5:
        to+=k
        m=0
    elif k>5:
        to+=10-k
        m=1
        
print(to+m)

Solution (Python):
n = list(map(int, list(input())))
n.reverse()
n.append(0)
ans = 0

for i in range(len(n)):
    
    
    
    if n[i] <= 4:
        ans += n[i]
    elif n[i] == 5:
        if n[i + 1] <= 4:
            ans += n[i] 
        else:
            ans += n[i]
            n[i + 1] += 1
    else:
        ans += 10 - n[i]
        n[i + 1] += 1
print(ans)

Solution (Python):
N=input()
L=[int(N[i]) for i in range(len(N))]

P=0
OT=0

for i in range(len(L)-1):
    if 0 <= L[i] <= 3:
        P += L[i] + OT
        OT = 0

    elif L[i] == 4:
        if OT == 1 and L[i+1]>=5:
            P += 5
        else:
            P += OT+L[i]
            OT = 0

    elif L[i] == 5:
        if OT == 1:
            P += 4

        else:
            if L[i+1] >= 5:
                P += 1 + 4
                OT = 1
            else:
                P += 5

    else:
        if OT == 1:
            P += 9-L[i]
            OT = 1
        else:
            P += 10 - L[i]
            OT = 1

Pone = 0
if OT==0:
    Pone = min(L[-1],11-L[-1])
elif OT==1 and L[-1]<=4:
    Pone = 1+L[-1]
else:
    Pone = 10-L[-1]

print(P+Pone)

Solution (Python):
def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = s_in()[::-1]
n = len(N)

dp1 = [0 for _ in range(n)]
dp1[0] = int(N[0])

dp2 = [0 for _ in range(n)]
dp2[0] = 10 - int(N[0])


for i, s in enumerate(N[1:]):
    i += 1

    m = int(s)
    dp1[i] = min(dp1[i-1] + m,      dp2[i-1] + (m+1))
    dp2[i] = min(dp1[i-1] + (10-m), dp2[i-1] + (10-m-1))



print(min(dp1[n-1], dp2[n-1]+1))

Solution (Python):
N = input()[::-1]
l = len(N)

n0 = int(N[0])
dp = [[0, 0] for i in range(l)]
dp[0] = [n0, 11-n0]

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


print(min(dp[-1]))

Solution (Python):
N = input()[::-1]
l = len(N)

n0 = int(N[0])
dp = [[0, 0] for i in range(l)]
dp[0] = [n0, 11-n0]

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


print(min(dp[-1]))

Solution (Python):
def read():
    N = input().strip()
    return N,


def solve(N, INF=1000000):
    L = len(N)
    N = list(reversed("0" + N))
    dp0 = [0 for i in range(L + 1)]
    dp1 = [0 for i in range(L + 1)]
    dp1[0] = INF
    for i in range(L):
        x = int(N[i])
        dp0[i + 1] = min(dp0[i] + x, dp1[i] + x)
        dp1[i + 1] = min(dp0[i] + 1 + (10 - x), dp1[i] + 1 + (10 - x) - 2)
    return min(dp0[-1], dp1[-1])


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Solution (Python):
N = list(input())
M = [ int(i) for i in N[::-1] ]
M.append(0)
c = 0

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

print(c)

Solution (Python):



def main():
  n = input().strip()[::-1]
  dp = [[0, 0] for _ in range(len(n))]
  dp[0][0] = int(n[0])
  dp[0][1] = 10 - int(n[0])
  for i, d in enumerate(map(int, n[1:]), 1):
    dp[i][0] = min(dp[i-1][0] + d,      dp[i-1][1] + 1 + d)
    dp[i][1] = min(dp[i-1][0] + 10 - d, dp[i-1][1] + 10 - (d + 1))
  print(min(dp[-1][0], dp[-1][1]+1))  

if __name__=='__main__':
  main()

Solution (Python):



"""
コンテスト後に解説記事を見てAC
Python 3だとTLE
"""

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N_str):
    """
    https://betrue12.hateblo.jp/ の通り実装

    上の桁から順番に見ていく
    dp[i][j] =
      上から i 桁目までの硬貨の支払いとお釣りを処理し終わって、
      N の i 桁目までの金額よりも j 枚分多く支払っているときの、
      これまでの支払い・お釣り硬貨の最小合計枚数
    """
    N_str = '0' + N_str
    dp = [[0] * 2 for _ in range(len(N_str))]

    

    
    
    
    
    
    
    
    
    
    
    

    for i, ch in enumerate(N_str):
        if i == 0:
            dp[0][0] = 0
            dp[0][1] = 1
        else:
            dp[i][0] = min(dp[i - 1][0] + int(ch),
                           dp[i - 1][1] + 10 - int(ch))
            dp[i][1] = min(dp[i - 1][0] + int(ch) + 1,
                           dp[i - 1][1] + 9 - int(ch))

    return dp[len(N_str) - 1][0]


def wrong(N_str):
    """最初に間違って書いた貪欲
    1の位から見ていき、0~4なら支払い、5~9なら10払ってお釣りをもらう

    N = 65のとき、
    この関数だと70払って5お釣りをもらうことになるが
    実際は100払って35お釣りをもらうべきなので誤り
    """
    N_str = N_str[::-1]
    ans = 0
    prev = 0
    for ch in N_str:
        n = int(ch)
        n += prev
        if n <= 5:
            ans += n
            prev = 0
        else:
            ans += 10 - n
            prev = 1
    ans += prev    
    return ans









N_str = input()
print(solve(N_str))

Solution (Python):
n = input()
precise = 0
over = 1
for d in n:
    d = int(d)
    new_over = min(precise + d + 1, over + d + 2, over + 9 - d)
    precise = min(over + d + 1, precise + d)
    over = new_over
over += 1
print(min(precise, over))

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

Solution (Python):
def main():
    N = [int(x) for x in input()]
    dp0 = 0
    dp1 = 1
    for n in N:
        
        a = min(dp0 + n, dp1 + 10 - n)
        
        b = min(dp0 + n + 1, dp1 + 10 - (n+1))
        dp0, dp1 = a, b
        
    print(dp0)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
S=input()
INF=10**12


dp=[[INF for _ in range(2)] for _ in range(10**6+5)]
S=S[::-1]
S+="0"
N=len(S)
dp[0][0]=0

for i in range(N):
    for j in range(2):
        
        x=int(S[i])
        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)
print(dp[N][0])

Solution (Python):
n = list(map(int,input()))[::-1]
n.append(0)
for i in range(len(n)):
    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))

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

for i in range(len(n)):
    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))

Solution (Python):
"""
f(n) , f(n+1)の値を求める
f(3456)を求める時

f(0) = 0, f(1) = 1 とする

f(3) = min
(
    f(0) + 3
    f(1) + 7
)
f(4) = min
(
    f(0) + 4
    f(1) + 6
)

f(34) = min
(
    f(3) + 4
    f(4) + 6
)
f(35) = min
(
    f(3) + 5
    f(4) + 5
)

f(345) = min
(
    f(34) + 5
    f(35) + 5
)
f(346) = min
(
    f(34) + 4
    f(35) + 6
)
f(3456) = min
(
    f(345) + 6
    f(346) + 4
)
"""
N = input()
n = [int(i) for i in N]

f0 = 0
f1 = 1

dp = f0, f1


for i in n:
    
    fn_0 = min(dp[0] + i, dp[1] + 10 - i)
    fn_1 = min(dp[0] + (i+1), dp[1] + 10 - (i+1))
    dp = fn_0, fn_1

print(dp[0])

Solution (Python):
nn = '0' + input()
ans = 0
dp = [[0 for i in range(2)] for j in range(len(nn))]
dp[0][1] = 1

for i,c in enumerate(nn[1:]):
    cc = int(c)
    zero = dp[i][0] + cc
    one = dp[i][1] + 10 - cc
    dp[i+1][0] = min(zero, one)
    dp[i+1][1] = min(zero + 1, one - (1 if i < len(nn) - 2 else 0))
print(min(dp[len(nn)-1]))

Solution (Python):
N = input().replace("\n", "")
L = len(N)
dp = [[0 for _ in range(2)] for i in range(L+1)]
dp[0][1] = 1
for i in range(L):
    n = int(N[i])
    dp[i+1][0] = min(dp[i][0]+n, dp[i][1]+(10-n))
    dp[i+1][1] = min(dp[i][0]+n+1, dp[i][1]+(9-n))
print(dp[L][0])

Solution (Python):

N = [int(x) for x in input()]
dp = 0,1
for item in N:
    a = min(dp[0] + item, dp[1] + 10 - item)
    b = min(dp[0] + item + 1, dp[1] + 10 - (item + 1))
    dp = a, b
    
print(dp[0])

Solution (Python):
import sys
input =sys.stdin.readline
def solve():
  s = input().rstrip()
  n = len(s)
  dp = [[float("Inf")]*2 for _ in range(n+1)]
  dp[0][0] = 0
  dp[0][1] = 1

  for i in range(0,n):
    number = int(s[i])

    dp[i+1][0] = min([dp[i][0]+number,dp[i][0]+(10-number)+1,dp[i+1][0]])
    if number != 9:
      dp[i+1][1] = min([dp[i][0]+number+1,dp[i][0]+(10-number),dp[i+1][1]])
     
    dp[i+1][0] = min(dp[i][1] +(10-number),dp[i+1][0])
    dp[i+1][1] = min(dp[i][1] + (10-number-1),dp[i+1][1])
        
  
  print(min(dp[n][0],dp[n][1]+1))
solve()

Solution (Python):

def solve():
  s = input()
  n = len(s)
  dp = [[float("Inf")]*2 for _ in range(n+1)]
  dp[0][0] = 0
  dp[0][1] = 1

  for i in range(0,n):
    number = int(s[i])
    for j in range(2):
      if j==0:
        dp[i+1][0] = min([dp[i][0]+number,dp[i][0]+(10-number)+1,dp[i+1][0]])
        if number != 9:
          dp[i+1][1] = min([dp[i][0]+number+1,dp[i][0]+(10-number),dp[i+1][1]])
      else:
        dp[i+1][0] = min(dp[i][1] +(10-number),dp[i+1][0])
        dp[i+1][1] = min(dp[i][1] + (10-number-1),dp[i+1][1])
        
  
  print(min(dp[n][0],dp[n][1]+1))
solve()

Solution (Python):
s = list(list(map(int,input())))
n = len(s)
dp = [ [0,0] for i in range(n) ]
dp[0][0] = s[0]
dp[0][1] = 11-(s[0]-0)
for i in range(n-1):
  d = s[i+1]
  dp[i+1][0] = min(dp[i][0], dp[i][1]) + d
  dp[i+1][1] = min(dp[i][0]+11-d, dp[i][1]+9-d)
print(min(dp[n-1][0],dp[n-1][1]))

Solution (Python):
N = input()

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

print(dp[0])

Solution (Python):
n = input()
a = int(n[-1])
b = 10 - int(n[-1])

for i in range(len(n)-2,-1,-1):
    a,b = min(a+int(n[i]), b + int(n[i]) + 1), min(a + 10-int(n[i]), b + 9 -int(n[i]))

print(min(a,b+1))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    just, less = 0, INF
    for d in input()[::-1]:
        d = int(d)
        njust = min(just + d, less + d + 1)
        nless = min(just + (10-d), less + (9-d))
        just, less = njust, nless
    print(min(just, less + 1))
resolve()

Solution (Python):
import os
import sys

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

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


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)


dp0 = [INF] * (N + 1)

dp1 = [INF] * (N + 1)

dp0[0] = 0
dp1[0] = 1
for i, c in enumerate(S):
    dp0[i + 1] = min(dp0[i] + int(c), dp1[i] + 10 - int(c))
    dp1[i + 1] = min(dp0[i] + int(c) + 1, dp1[i] + 10 - int(c) - 1)


print(dp0[-1])

Solution (Python):





s = input()[::-1]  
length = len(s)
dp = [[0]*2 for _ in range(length+1)]  
for i in range(length):
    
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+int(s[i])+1)

    
    if i != 0:
        
        dp[i+1][1] = min(dp[i][0]+10-int(s[i]), dp[i][1]+(10-1)-int(s[i]))
    else:
        dp[i+1][1] = dp[i][0]+10-int(s[i])  

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

Solution (Python):
N = list(input())
Y = [0]
for i in N:
    Y.append(int(i))
dp = [0 for i in range(len(N)+1)]
dp2 = [10 for i in range(len(N)+1)]
for i in range(1,len(N)+1):
    dp[i] = min(dp[i-1] + Y[i],dp2[i-1] + Y[i])
    dp2[i] = min(dp[i-1] + 1 + 10 - Y[i],dp2[i-1] - 1 + 10 - Y[i])
    
ans = min(dp[-1],dp2[-1])

print(ans)

Solution (Python):
S="0"+input()
dig=len(S)




inf=10**10
dp=[[inf,inf] for _ in range(dig+1)]
dp[0]=[0,0]

for i in range(dig):
    for j in range(2):
        if i==0 and j==1:
            break
        x=int(S[dig-i-1])
        for a in range(10):
            jj=0
            b=(a-j)-x
            if b<0:
                b+=10
                jj=1
            dp[i+1][jj]=min(dp[i+1][jj] , dp[i][j]+a+b)
            
print(dp[-1][0])

Solution (Python):

N = list(input())
N = [int(n) for n in N]
N.insert(0, 0)
len_N = len(N)
ans = 0

for i in reversed(range(len_N)):
    num = int(N[i])
    if num == 10:
        N[i-1] += 1
    
    elif num==5:
        if int(N[i-1])>=5:
            ans += 5
            N[i-1] += 1
        else:
            ans += 5
    
    elif num >5:
        ans += (10-num)
        N[i-1] += 1
    else:
        ans += num

print(ans)

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

Solution (Python):
import sys

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

N = list(map(int, input()))

def solve(N):
    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)
    return dp[0]

print(solve(N))

Solution (Python):
import sys

n = sys.stdin.readline().rstrip()

def main():
    dp = [0, 1]
    for d in n:
        d = int(d)
        dp[0], dp[1] = min(dp[0]+d, dp[1]+10-d), min(dp[0]+d+1, dp[1]+10-d-1)

    return dp[0]

if __name__ == '__main__':
    ans = main()
    print(ans)

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

Solution (Python):
import sys

n = sys.stdin.readline().rstrip()
l = len(n)

def main():
    dp0 = [None] * (l + 1)
    dp1 = [None] * (l + 1)
    dp0[0] = 0
    dp1[0] = 1

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
N = input()

a = 0  
b = 0  

t = int(N[-1])
a, b = a + t, a + (10 - t)

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

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


b0 = [0]*len(n)
b1 = [0]*len(n)
b1[0] = 1
for i in range(1, len(n)):
  num = n[i]
  b0[i] = min(b0[i-1]+num, b1[i-1]+num+1)
  b1[i] = min(b0[i-1]+10-num, b1[i-1]+10-(num+1))

print(min(b0[-1], b1[-1]))

Solution (Python):
N = input()

a = 0  
b = 0  
t = int(N[-1])
a, b = a + t, a + (10 - t)

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

Solution (Python):
s = input(); n = len(s)
dp = [ [0,1<<32] for i in range(2) ]
for i in range(n):
  d = ord(s[i])-ord('0')
  dp[(i+1)%2][0] = min(dp[i%2][0], dp[i%2][1])+d
  dp[(i+1)%2][1] = min(dp[i%2][0], dp[i%2][1]-2)+11-d
print(min(dp[n%2][0],dp[n%2][1]))

Solution (Python):
dp = [0, 1]

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

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

print(min(dp))

Solution (Python):
N = '0' + input()
INF = float('inf')
dp = [[INF] * 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):
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - n - j
            if b < 0:
                b += 10
                nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)
            a == b

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

Solution (Python):
s=list(map(int,input()[::-1]))
t=[[0,0]for i in range(len(s)+1)]
t[0]=[0,9]
for i in range(len(s)):
    t[i+1][0]=min(t[i][0],t[i][1])+s[i]
    t[i+1][1]=min(11-s[i]+t[i][0],9-s[i]+t[i][1])
print(min(t[-1]))

Solution (Python):
s=list(map(int,input()[::-1]))
t=[[0,0]for i in range(len(s)+1)]
t[0]=[0,9]
for i in range(len(s)):
    t[i+1][0]=min(t[i][0],t[i][1])+s[i]
    t[i+1][1]=min(11-s[i]+t[i][0],9-s[i]+t[i][1])
print(min(t[-1]))

Solution (Python):
def y_solver(tmp):
    l=len(tmp)
    rev=[int(i) for i in tmp[::-1]+"0"]
    ans=0
    for i in range(l):
        num=rev[i]
        next_num=rev[i+1]
        if (num>5) or (num==5 and next_num>=5):
            rev[i+1]+=1
        ans+=min(num,10-num)  
    last=rev[l]
    ans+=min(last,10-last)
    return ans
s=input()
ans=y_solver(s)
print(ans)

Solution (Python):

def y_solver(tmp):
    l=len(tmp)
    rev=[int(i) for i in tmp[::-1]+"0"]
    ans=0
    for i in range(l):
        num=rev[i]
        next_num=rev[i+1]
        if (num>5) or (num==5 and next_num>=5):
            rev[i+1]+=1
        ans+=min(num,10-num)  
    last=rev[l]
    ans+=min(last,10-last)
    return ans
  
s=input()
ans=y_solver(s)
print(ans)

Solution (Python):
def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    
    
    return(dp[l+1])

s=input()
ans=dp_solver(s)
print(ans[0])

Solution (Python):

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if (num<5) or (num==5 and next_num<5):
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
        else:
            kuri_cal+=10-num
            next_bit=1 
    
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=y_solver(n)
print(ans)

Solution (Python):
def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    import numpy as np
    dp=np.array(dp)
    return(dp[l+1])

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    seq_flag=False
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if not seq_flag:
            if (num<5) or (num==5 and next_num<5):
                ans+=num
                next_bit=0
                kuri_cal=0
                continue
            seq_s=i
            seq_flag=True
            kuri_cal=10-num
            next_bit+=1
            continue
        
        if num<5:
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
            seq_flag=False
        elif num>5:
            kuri_cal+=10-num
        else:
            if next_num<5:
                ans+=(kuri_cal+num)
                next_bit=0
                kuri_cal=0
                seq_flag=False
            else:
                kuri_cal+=10-num
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=y_solver(n)
print(ans)

Solution (Python):
N = input()

N = '0' + N
result = 0
carry = 0
for i in range(len(N) - 1, 0, -1):
    c = int(N[i]) + carry
    n = int(N[i - 1])
    if c < 5 or (c == 5 and n < 5):
        result += c
        carry = 0
    else:
        result += 10 - c
        carry = 1
result += carry
print(result)

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

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

for i, n in enumerate(N):
    dp[i + 1][0] = min(dp[i][0] + n, dp[i][1] + (10 - n))
    dp[i + 1][1] = min(dp[i][0] + (n + 1), dp[i][1] + (10 - (n + 1)))
    
print(dp[-1][0])

Solution (Python):
def main():
    S = map(int, input())

    a, b = 0, 1
    for s in S:
        a, b = a + s if a + s < b + 10 - s else b + 10 - s, a + (s + 1) if a + (s + 1) < b + 10 - (s + 1) else b + 10 - (s + 1)

    print(a)


main()

Solution (Python):
S = map(int, input())

a, b = 0, 1
for s in S:
    a, b = a + s if a + s < b + 10 - s else b + 10 - s, a + (s + 1) if a + (s + 1) < b + 10 - (s + 1) else b + 10 - (s + 1)

print(a)

Solution (Python):
def main():
    S = map(int, input())

    a, b = 0, 1
    for s in S:
        a, b = min(a + s, b + 10 - s), min(a + (s + 1), b + 10 - (s + 1))

    print(a)


main()

Solution (Python):
S = map(int, input())

a, b = 0, 1
for s in S:
    a, b = min(a + s, b + 10 - s), min(a + (s + 1), b + 10 - (s + 1))

print(a)

Solution (Python):
import sys
read = sys.stdin.readline













N = '00' + read()[:-1]

N = N[::-1]
ans = 0
i = 0

lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    if lo == 5:  
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:
        
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  
    lo = hi  
    i += 1


print(ans)

Solution (Python):
import sys
read = sys.stdin.readline













N = '00' + read()[:-1]

N = N[::-1]
ans = 0
i = 0

lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    if lo == 5:  
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:
        
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  
    lo = hi  
    i += 1


print(ans)

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

Solution (Python):
import sys
read = sys.stdin.readline













N = '00' + read()[:-1]

N = N[::-1]
ans = 0

i = 0
lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    
    if lo == 5:
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:  
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  
    lo = hi  
    i += 1


print(ans)

Solution (Python):
import sys
read = sys.stdin.readline













N = '00' + read()[:-1]

N = N[::-1]
ans = 0

































i = 0
lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    
    if lo == 5 and hi == 5:
        
        
        
        ans += 5
        i += 1
        while i < len(N) - 1 and N[i + 1] == '5':
            ans += 4
            
            i += 1
        ans += 4
        
        hi = int(N[i + 1]) + 1
        

        
    elif lo == 5:
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:  
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  
    lo = hi  
    i += 1


print(ans)

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

s = s[::-1]
s = s + [0]
cnt = 0
kuri = 0

for i in range(len(s)):
  n = s[i]
  if n < 5:
    cnt += n
  elif n > 5:
    cnt += 10 - n
    s[i+1] += 1
  else:
    if s[i+1] >= 5:
      s[i+1] += 1
    cnt += 10 - n
print(cnt)

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

Solution (Python):
n = input()
a, b = 0, 100
for i in n:
  j = int(i)
  a, b = min(a+j,b+j), min(a+11-j,b+9-j)
  if j == 0:
    b = a+100
print(min(a,b))

Solution (Python):
def main():
    N=[int(x) for x in input()]
    l=len(N)+1
    DP=[[0]*2 for _ in range(l)]
    DP[0][1]=1
    for i,n in enumerate(N):
        DP[i+1][0]=min(DP[i][0]+n,DP[i][1]+(10-n))
        DP[i+1][1]=min(DP[i][0]+(n+1),DP[i][1]+(10-(n+1)))
    print(DP[-1][0])
    
if __name__=='__main__':
    main()

Solution (Python):
N = list(input())
Y = [0]
for i in N:
    Y.append(int(i))
dp = [0 for i in range(len(N)+1)]
dp2 = [10 for i in range(len(N)+1)]
for i in range(1,len(N)+1):
    dp[i] = min(dp[i-1] + Y[i],dp2[i-1] + Y[i])
    dp2[i] = min(dp[i-1] + 1 + 10 - Y[i],dp2[i-1] - 1 + 10 - Y[i])
ans = min(dp[-1],dp2[-1])

print(ans)

Solution (Python):
Z = [0,1,2,3,4,5,5,4,3,2,1,1]
X=[0,1,2,3,4,5,6,7,8,9]
def solve_dp(s):
    n = len(s)
    s = [int(c) for c in s]
    inf = 10**9

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

    d0 = s[0]
    dp[0][0] = Z[d0]
    dp[0][1] = Z[d0+1]

    for i in range(1, n):
        for j in range(2):
            d = s[i] + j
            for k in range(10):
                if d + X[k] >= 10:
                    dp[i][j] = min(dp[i][j], dp[i-1][1] + X[k] + Z[d + X[k] - 10])
                else:
                    dp[i][j] = min(dp[i][j], dp[i-1][0] + X[k] + Z[d + X[k]])

    return dp[n-1][0]

if __name__ == '__main__':
    s = input()
    print(solve_dp(s))

Solution (Python):
kuri_now = False
cost = [0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
kuri = [0, 0, 0, 0, 0, 0.5, 1, 1, 1, 1, 1]
result = 0
for digit in reversed(input()):
    digit = int(digit)
    if kuri_now == 0:
        result += cost[digit]
        kuri_now = kuri[digit]
    elif kuri_now == 1:
        result += cost[digit + 1]
        kuri_now = kuri[digit + 1]
    else:
        if cost[digit] <= cost[digit + 1]:
            result += cost[digit]
            kuri_now = kuri[digit]
        else:
            result += cost[digit + 1]
            kuri_now = kuri[digit + 1]
if kuri_now == 1:
    result += 1
print(result)

Solution (Python):
def main():
    a = list(map(int, list(input())))
    n = len(a)
    dp = [[0, 0] for _ in [0]*(n+1)]
    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]+9-a[i])
    print(dp[n][0])

main()

Solution (Python):
def main():
    N = input()
    len_N = len(N)
    ans = 0
    pre = 0
    for i in range(len_N-1,-1,-1):
        int_N = int(N[i]) + pre
        if int_N <= 4:
            ans += int_N
            pre = 0
        elif int_N >= 6:
            ans += 10 - int_N
            pre = 1
        elif int_N == 5:
            if i == 0:
                ans += int_N
                pre = 0
            else:
                if int(N[i-1]) <= 4:
                    ans += int_N
                    pre = 0
                else:
                    ans += int_N
                    pre = 1
    else:
        ans += pre
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

import sys



def solve(N: "List[int]"):
    
    
    dp = 0,1
    for i in N:
        
        a = min(dp[0]+i, dp[1]+10-i)
        
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



def main():
    stdin = open(0)
    N = [int(x) for x in stdin.read().rstrip()]
    solve(N)

if __name__ == '__main__':
    main()

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