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().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)

Solution (Python):


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)

Solution (Python):
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()


    ans = 0
    print(ans)
    return

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    for i in range(N-1,-1,-1):
        
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    
    ans = min(dp[-1][0],dp[-1][1])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE2()

"""
4396817
"""

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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])
    
    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)))
    



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

Solution (Python):
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))

Solution (Python):

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


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



if __name__ == '__main__':
    solve()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):


n = input()
l = len(n)



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
    
    
    
    

print(a)

Solution (Python):


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:
            
            ans += v
            kuriagari = 0
        if int(n[i+1])>=5:
            
            ans += 10 - v
            kuriagari = 1
        
print(ans)

Solution (Python):
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):
      
      
      x = n+j
      
      if x < 10:
        dp[i+1][0] = min(dp[i+1][0],dp[i][j]+x)
      
      if x > 0:
        dp[i+1][1] = min(dp[i+1][1],dp[i][j]+10-x)
  print(dp[len(N)][0])  
  
  
if __name__ == '__main__':
  main()

Solution (Python):
n = list(input())
inf = 10**9
dp = [[inf for i in range(2)] for j in range(len(n) + 2)]


n.reverse()
n += ['0']

dp[0][0] = 0

for i in range(len(n)):
    for j in range(2):
        x = int(n[i])
        
        
        
        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]))

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):

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


if __name__ == "__main__":
    solve()

Solution (Python):
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)

Solution (Python):
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]))

Solution (Python):
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])

Solution (Python):



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

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

N = input()





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


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


for i in range(L+1):
    n = int(N[i])

    
    ni = i + 1

    
    
    dp[ni][0] = min(dp[ni][0], dp[i][0] + n)

    
    if n > 0:
        dp[ni][1] = min(dp[ni][1], dp[i][0] + (10 - n))
    else:
        dp[ni][0] = min(dp[ni][0], dp[i][0])

    
    n += 1

    
    if n == 10:
        dp[ni][1] = min(dp[ni][1], dp[i][1])
    else:
        dp[ni][0] = min(dp[ni][0], dp[i][1] + n)

    
    dp[ni][1] = min(dp[ni][1], dp[i][1] + (10 - n))


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

print(ans)

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

N = input()




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


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


for i in range(L+1):
    for j in range(2):
        
        n = int(N[i])
        n += j

        
        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)

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

N = input()


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


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


for i in range(L+1):
    for j in range(2):
        
        n = int(N[i])
        n += j

        
        ni = i + 1

        
        for a in range(10):
            nj = 0
            b = a - n

            
            if b < 0:
                b += 10
                nj = 1

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

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

print(ans)

Solution (Python):
"""
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()


n = int(strN[0])
dp = [min(n, 11 - n), min(n + 1, 11 - (n + 1))] 

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

print(dp[0])

Solution (Python):
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]))

Solution (Python):



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)

Solution (Python):

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

























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
	

	cnt = 0
	for ii in N:
		i = int(ii)
		cnt += 1
		
		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[len(N)][0])

if __name__ == "__main__":
	main()

Solution (Python):
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)

Solution (Python):

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

Solution (Python):

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]

Solution (Python):
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))

Solution (Python):




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 
    for x in map(int, s):
        c, d = dp
    
        
        
        a = min(c + x,    d + 10 - x)
        
        b = min(c + x + 1,d + 10 - 1 - x )
        
        
        dp = a,b
        p(dp)
    return dp[0]
if DBG:
    pass




print(sol(read()))

Solution (Python):


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

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
from sys import stdin

def get_result(data):
  N = data[0]
  
  dp = 0, 1
  for n in N:
      n = int(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]

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

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
n = input()


dp = [[0 for i in range(len(n))] for j in range(2)]

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

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

print(min(dp[0][len(n)-1], dp[1][len(n)-1]))

Solution (Python):
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))





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

Solution (Python):
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()

Solution (Python):
def e_payment_greedy():
    N = [int(i) for i in list(input())]
    s = N[::-1] + [0]  

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

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

    dp = (0, 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())

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)]
dp[0] = [N[0], 10 - N[0]]

for i in range(1, L):
    n = N[i]
    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])

Solution (Python):
s = list(input())
s.reverse()
s.append('0')

dp = [[1000000000] * 2 for _ in range(1000005)]
dp[0][0] = 0
n = len(s)
for i in range(n):
    for j in range(2):
        x = int(s[i])
        x += j
        if x < 10:
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)
        if x > 0:
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))

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

Solution (Python):
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()

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):

n=input()

dp0=[0 for i in range(1000002)]
dp1=[0 for i in range(1000002)]
nums=int(n[-1])

dp0[1]=nums
dp1[1]=11-nums

for i in range(1,len(n)):
    s=int(n[-(i+1)])
    dp0[i+1]=s+min(dp0[i],dp1[i])
    dp1[i+1]=min(9-s+dp1[i],11-s+dp0[i])
print(min(dp0[len(n)],dp1[len(n)]))

Solution (Python):
n=input()
l=len(n)
pre=[0,1]
for i in range(l):
    c=[0,0]
    d=int(n[i])
    c[0]=min(pre[0]+d,pre[1]+10-d)
    c[1]=min(pre[0]+d+1,pre[1]+10-d-1)
    pre=c
print(pre[0])

Solution (Python):
import sys
def main():
    input=sys.stdin.readline
    S=input().strip()
    dp=[[0,0] for i in range(len(S)+1)]
    dp[0][1]=1
    for i in range(1,len(S)+1):
        for j in (0,1):
            if j==0:
                dp[i][0]=min(dp[i-1][0]+int(S[i-1]),dp[i-1][1]+10-int(S[i-1]))
            elif j==1:
                dp[i][1]=min(dp[i-1][0]+int(S[i-1])+1,dp[i-1][1]+10-int(S[i-1])-1)

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

if __name__=="__main__":
    main()

Solution (Python):
N=input()
a=[]
s=len(N)

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


p=sum(a)
t=0
f=0
c=0
for i in range(len(a)-1):
    if a[i] <= 5:
        t+=a[i]
        if a[i] == 5 and a[i+1]>=5:a[i+1]+=1
        f=0
        
    else:
        c+=10-a[i]
        a[i+1] += 1
        f=1
        
print(t+f+c)

Solution (Python):
def main():
    n = list(map(int, input()[::-1])) + [0]
    s = 0
    res = 0
    for i, ni in enumerate(n[:-1]):
        k = ni + s
        if k < 5 or (k == 5 and n[i + 1] < 5):
            res += k
            s = 0
        else:
            res += 10 - k
            s = 1
    res += s
    print(res)


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


def main():
    n = list(map(int, input()[::-1])) + [0]
    s = 0
    res = 0
    for i, ni in enumerate(n[:-1]):
        k = ni + s
        if k < 5 or (k == 5 and int(n[i + 1]) < 5):
            res += k
            s = 0
        else:
            res += 10 - k
            s = 1
    res += s
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
n = list(map(int, input()[::-1])) + [0]
s = 0
res = 0
for i, ni in enumerate(n[:-1]):
    k = ni + s
    if k < 5 or (k == 5 and int(n[i + 1]) < 5):
        res += k
        s = 0
    else:
        res += 10 - k
        s = 1
res += s
print(res)

Solution (Python):
a,b=1,0
for c in map(int,input()):a,b=min(a+10-c-1,b+c+1),min(a+10-c,b+c)
print(b)