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 I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    S="00"+input()
    S=S[::-1]
    N=len(S)-1
    
    def calc(x,nxt):
        
        

        if x<=4:
            return x,0
        elif x>=6:
            return 10-x,1
        else:
            
            if nxt<5:
                return 5,0
            else:
                return 5,1
    
    kuri=0
    ans=0
    for i in range(N):
        now=int(S[i])
        nxt=int(S[i+1])
        now+=kuri
        temp,kuri = calc(now,nxt)
        
        ans+=temp
        
    print(ans)
        

main()

Solution (Python):
N=input()
inf=float("inf")
dp=[[inf]*(len(N)+1) for i in range(2)]
dp[0][0]=0
for i in range(len(N)):
   tmp=int(N[-1-i])
   dp[0][i+1]=min(dp[0][i],dp[1][i])+tmp
   dp[1][i+1]=min(dp[0][i]+11,dp[1][i]+9)-tmp
print(min(dp[0][-1],dp[1][-1]))

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

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

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

Solution (Python):
n = input()
dp = [0, 10000]
for d in map(int, reversed(n)):
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]
print(min(dp[0], 1 + dp[1]))

Solution (Python):
dp = [0, 2]
for d in map(int, reversed(input())):
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

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

Solution (Python):
import sys
import functools

n = input()


















dp = [0, 2]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

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

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

dp = [0, 10000]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

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

Solution (Python):
n = input()
dp = [0, 10000]
for d in reversed('0' + n):
    newdp = []
    newdp.append(min(int(d) + dp[0], int(d) + 1 + dp[1]))
    newdp.append(min(10 - int(d) + dp[0], 10 - int(d) - 1 + dp[1]))
    dp = newdp
print(dp[0])

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N = S()
    N =  N[::-1]
    N += '0'
    cnt = 0
    next = 0
    for i in range(len(N)):
        num = int(N[i])
        num += next
        if num <= 4:
            cnt += num
            next = 0
        elif num >= 6:
            cnt += 10 - num
            next = 1
        else:
            if int(N[i + 1]) <= 4:
                cnt += num
                next = 0
            else:
                cnt += 10 - num
                next = 1

    print(cnt)
if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N = SL()[::-1]
    dp = [0] * (len(N) + 1)

    for i, e in enumerate(N):
        if int(e) + dp[i] >= 6:
            dp[i] = 10 - (int(e) + dp[i])
            dp[i+1] += 1
        elif int(e) + dp[i] == 5 and i < len(N)-1 and int(N[i+1]) >= 5:
            dp[i] = 5
            dp[i+1] += 1
        else:
            dp[i] += int(e)
    print(sum(dp))

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def solve(N):
    dp = [0] * (len(N) + 1)

    for i, e in enumerate(N):
        if int(e) + dp[i] >= 6:
            dp[i] = 10 - (int(e) + dp[i])
            dp[i+1] += 1
        elif int(e) + dp[i] == 5 and i < len(N)-1 and int(N[i+1]) >= 5:
            dp[i] = 5
            dp[i+1] += 1
        else:
            dp[i] += int(e)
    return dp

def digit_sum(n):
    tmp = 0
    while n:
        tmp += n % 10
        n //= 10
    return tmp

def greedy(N):
    ans = INF
    bestp = None
    for p in itertools.product(range(10), repeat=len(N)+1):
        n = 0
        for i in range(len(p)):
            n += p[i] * (10 ** i)
        intN = 0
        for i in range(len(N)):
            intN += int(N[i]) * (10 ** i)
        if n >= intN:
            if ans > digit_sum(n) + digit_sum(n - intN):
                ans = digit_sum(n) + digit_sum(n - intN)
                bestp = p
    return ans, bestp












def main():
    N = SL()[::-1]
    dp = [0] * (len(N) + 1)

    for i, e in enumerate(N):
        if int(e) + dp[i] >= 6:
            dp[i] = 10 - (int(e) + dp[i])
            dp[i+1] += 1
        elif int(e) + dp[i] == 5 and i < len(N)-1 and int(N[i+1]) >= 5:
            dp[i] = 5
            dp[i+1] += 1
        else:
            dp[i] += int(e)
    print(sum(dp))

if __name__ == '__main__':
    main()

Solution (Python):
s=[int(i) for i in input()]
n=len(s)
ans=0
f=0
for i in range(n-1,-1,-1):
  j=s[i]+f
  if j<5:
    ans+=j
    f=0
  elif j>5:
    ans+=10-j
    f=1
  elif i and s[i-1]>=5:
    ans+=10-j
    f=1
  else:
    ans+=j
    f=0
print(ans+f)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = input() + "0"

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

    print(dp[-1][0])


if __name__ == '__main__':
    resolve()

Solution (Python):
S = input()
ans = 0
flag = False 
flag2 = False 
for k in range(len(S)):
  n = int(S[-k-1])
  if flag2:
    if n < 5:
      flag = False
    else:
      flag = True
  if flag:
    n += 1
  if n == 5:
    ans += 5
    flag2 = True
    flag = False
  elif n < 5:
    ans += n
    flag2 = False
    flag = False
  else:
    ans += 10-n
    flag2 = False
    flag = True
if flag:
  ans += 1
print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1


def main():
    ans = 0
    n = input()
    dp = [0,1] 
    for i in n:
        ni = int(i)
        pdp = dp*1
        dp[0] = min(pdp[0]+ni,pdp[1]+(10-ni))
        dp[1] = min(pdp[0]+ni+1,pdp[1]+(10-ni-1))
    print(dp[0])


    return None

if __name__ == '__main__':
    main()

Solution (Python):



N = list(map(int, list(input())))
N.reverse()
N=N+[0]
cnt = 0
for i in range(len(N)):
    n=N[i]
    if n<5:
        cnt+=n
    elif n==5:
        cnt+=n
        if N[i+1]>=5:
            N[i+1]+=1
    else:
        cnt+=10-n
        N[i+1]+=1
print(cnt)

Solution (Python):
n = str(input())
n_list = list(reversed(n))
n_list.append('0')
sum = 0
kuriagari = False
for i in range(len(n_list)):
    num = int(n_list[i])
    if(kuriagari):
        num+=1
        kuriagari=False
    
    if(num==10):
        num=0
        kuriagari=True

    if(num<5):
        sum+=num
    else:
        if(num>5):
            sum+=10-num
            kuriagari=True
        else:
            sum+=5
            if(int(n_list[i+1])>=5):
                kuriagari=True

print(sum)

Solution (Python):
s = "0" + input()
n = len(s)
S = []
for i in range(n-1,-1,-1):
    S.append(int(s[i]))

ans = sum(S)
ans0 = ans
D = [[0] * 3 for i in range(n)]
D[0] = [S[0], S[0]+1, 10-S[0]]
for i in range(1, n):
    D[i][0] = min(D[i-1][0], D[i-1][1]) + S[i]
    D[i][1] = D[i-1][2] + S[i] + 1
    D[i][2] = min(D[i-1][0]+10-S[i], D[i-1][1]+10-S[i], D[i-1][2]+9-S[i])


print(min(D[-1][:2]))

Solution (Python):
import math


def count(N, X):
    cnt = sum(map(int, str(X))) + sum(map(int, str(X - N)))
    return cnt


def solve_naive_first(N):
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive(N), 1+solve_naive(p*10-N))


def solve_naive(N):
    if N < 10:
        return min(N, 10-N+1)
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive((N // p + 1) * p - N) + (N // p + 1), solve_naive(N % p) + N // p)


def solve(N):
    n_0, n_1 = 0, 1  
    for i in N[::-1]:
        i = int(i)
        if i == 9:
            n_0, n_1 = n_0 + i, min(n_0 + 10 - i, n_1 + 10 - i - 1)
        else:
            n_0, n_1 = min(n_0 + i, n_1 + i + 1), min(n_0 +
                                                      10 - i, n_1 + 10 - i - 1)
    return min(n_0, n_1+1)


if __name__ == '__main__':
    N = input()
    ans = solve(N)
    print(ans)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=RD()[::-1]
	N=list(map(int,n))+[0]
	

	ans=0

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

	print(ans)









if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=RD()[::-1]
	N=list(map(int,n))+[0]
	

	ans=0

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

	print(ans)









if __name__ == "__main__":
	main()

Solution (Python):
n=[int(x) for x in list(input()[::-1])]+[0]
ans = 0
step = 0
for i in range(len(n)-1):
  x = n[i]+step
  if x < 5 or (x==5 and n[i+1]<5):
    ans += x
    step = 0
  else:
    ans += 10 - x
    step = 1
print(ans+step)

Solution (Python):
abef=0
bbef=1
s=input()
for i in range(len(s)):
  curr=int(s[len(s)-1-i])
  a=abef+curr
  b=bbef+9-curr
  a=min(a,1+bbef+curr)
  b=min(b,abef+10-curr)
  abef=a
  bbef=b
curr=0
a=abef+curr
b=bbef+9-curr
a=min(a,1+bbef+curr)
b=min(b,abef+10-curr)
print(min(a,b))

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = [0] + list(map(int,SI()))
    ans = 0
    for i in range(len(N)-1,-1,-1):

        if N[i] < 6 and not(N[i] == 5 and (i > 0 and N[i-1] >= 5)):
            ans += N[i]
        else:
            ans += 10 - N[i]
            N[i-1] += 1
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from numba import njit

N = np.array([int(_) for _ in input()])


def solve(N):
    p, q = 0, 1
    for x in N:
        p, q = min(p + x, q + 10 - x), min(p + x + 1, q + 9 - x)
    print(p)


solve(N)

Solution (Python):
p, q = 0, 1
for x in map(int, input()):
    p, q = min(p + x, q + 10 - x), min(p + x + 1, q + 9 - x)
print(p)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = list(map(int,input()))
    count = 0

    S = len(N)
    flag = 0
    for i in range(S):
        temp = flag + N[-1 - i]
        if temp > 5:
            count += 10 - temp
            flag = 1
        elif temp ==5  and i !=S-1 and N[-1-i-1]>=5:
            count+=temp
            flag=1

        else:
            count += temp
            flag = 0

    print(count + flag)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = list(map(int,input()))
    count = 0

    S = len(N)
    flag = 0
    for i in range(S):
        temp = flag + N[-1 - i]
        if temp > 5:
            count += 10 - temp
            flag = 1
        elif temp ==5  and i !=S-1 and N[-1-i-1]>=5:
            count+=temp
            flag=1

        else:
            count += temp
            flag = 0

    print(count + flag)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = input()
    count = 0

    S = len(N)
    flag = 0
    for i in range(S):
        temp = flag + int(N[-1 - i])
        if temp > 5:
            count += 10 - temp
            flag = 1
        elif temp ==5  and i !=S-1 and int(N[-1-i-1])>=5:
            count+=temp
            flag=1

        else:
            count += temp
            flag = 0

    print(count + flag)


if __name__ == "__main__":
    main()

Solution (Python):
A = list(map(int, input()))
while A[-1] == 0:
  A.pop()
n = len(A)
dp = [[0]*2 for _ in range(n)]
dp[0][1] = 1
for i, a in enumerate(A[:-1]):
  if i < n-1:
    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]+9-a)
ans = min(dp[-1][0]+A[-1], dp[-1][1]+10-A[-1])
print(ans)

Solution (Python):
A = list(map(int, input()))
while A[-1] == 0:
  A.pop()
n = len(A)
dp = [[0]*2 for _ in range(n)]
dp[0][1] = 1
for i, a in enumerate(A[:-1]):
  if i < n-1:
    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]+9-a)
ans = min(dp[-1][0]+A[-1], dp[-1][1]+10-A[-1])
print(ans)

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

Solution (Python):
import sys

def resolve(in_):
    dp0 = [1 << 60] * 1000100
    dp1 = [1 << 60] * 1000100
    zero = ord(b'0')
    dp0[0] = 0
    dp1[0] = 2

    for i, v in enumerate(in_.read().rstrip()):
        v -= zero

        
        dp0[i + 1] = min(dp0[i] + v, dp1[i] + v)

        
        
        dp1[i + 1] = min(dp0[i] + 1 + 10 - v, dp1[i] + 9 - v)
    else:
        i += 1


    return min(dp0[i], dp1[i])


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
def solve(N):
    N = [0] + N
    k = 0  
    ans = 0
    for d, d_next in zip(N[::-1], N[-2::-1]):
        d += k
        if d <= 4 or (d==5 and d_next<5):
            k = 0
            ans += d
        else:
            k = 1
            ans += 10 - d
    if k:
        ans += 1
    return ans

def test(N, ans):
    for i in range(N, 10000):
        rem = i - N
        if sum(map(int, str(i))) + sum(map(int, str(rem))) < ans:
            print(f"!!! N={N}, ans={ans}, trueans={i, rem}")
def main():
    N = list(map(int, input()))
    print(solve(N))
    
    
    
main()

Solution (Python):

def resolve():
    S = "0" + input()
    N = len(S)

    dp = [[1<<60]*2 for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        now = int(S[i])
        dp[i+1][0] = min(dp[i][0]+now, dp[i][1]+(10- now))
        dp[i + 1][1] = min(dp[i][0] + now + 1, dp[i][1] + (10 - now - 1))
    print(dp[N][0])


if __name__ == "__main__":
    resolve()

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

for i in range(len(N)):
    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] + 10 - (n + 1))

print(dp[-1][0])

Solution (Python):
S = input()
S = S[::-1]
S += '0'

n = len(S)
dp = [[10**20 for j in range(2)] for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = ord(S[i])-ord('0')
        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):
import sys
input = sys.stdin.readline

n = list(input().strip())
ans = 0

carry = False
for i in range(len(n) - 1, -1, -1):
    p = int(n[i])
    if carry:
        p += 1
        carry = False
    if p == 10:
        carry = True
    elif p >= 6:
        carry = True
        ans += 10 - p
    elif p == 5:
        if i != 0 and int(n[i - 1]) >= 5:
            carry = True
            ans += 5
        else:
            carry = False
            ans += 5
    else:
        ans += p
if carry:
    ans += 1
print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main_b():
	s = input()
	pp=0
	na=0
	for i, c in enumerate(s[::-1]):
		cc=na+int(c)
		na=0
		if cc <= 4:
			pp+=cc
		else:
			na = 1
			if i==len(s)-1:
				pp+=1
			pp+=10-cc
			
	print(pp)
	
def main():
	s = input()
	pmin=1000
	mmin=0
	s='0'+s
	for c in s[::-1]:
		v = int(c)
		npmin = min(pmin + 10 - (v+1), mmin + 10 - v)
		nmmin = min(pmin + v + 1, mmin + v)
		pmin = npmin
		mmin = nmmin
	return min(pmin, mmin)
	
	
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):

N = input()

lim = len(N)
dp = [[0, 0] for _ in range(lim + 1)]
dp[0][1] = 1
for i in range(lim):
    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] + 10 - n - 1)

print(dp[-1][0])

Solution (Python):
N = list(input())

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

ans += num
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

dp = [[10**18]*2 for _ in range(length+1)]
dp[0][0] = 0
for i in range(1, length+1):
    n = N[-i]
    dp[i][1] = min(dp[i-1][1]+(9-n), dp[i-1][0]+(10-n))
    dp[i][0] = min(dp[i-1][0]+n, dp[i-1][1]+n+1)
    if i==length:
        dp[i][1] = dp[i][1]+1
print(min(dp[-1]))

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

INF = float('inf')
dp = [[INF]*(L+1) for _ in range(2)]
dp[0][0] = 0

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

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = input()
N = [int(i) for i in N]

dp = [[0, 0] for i in range(len(N))]


dp[0][0] = min(N[0], 11 - N[0])

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

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

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

Solution (Python):
def main():
    s = input()
    dp = [0, 1]
    for c in s:
        x = int(c)
        a = dp[0] + x
        if a > dp[1] + 10 - x:
            a = dp[1] + 10 - x
        b = dp[0] + x + 1
        if b > dp[1] + 10 - x - 1:
            b = dp[1] + 10 - x - 1
        dp[0] = a
        dp[1] = b
    dp[1] += 1
    print(min(dp))

if __name__ == "__main__":
    main()

Solution (Python):
s = '0' + input()
m = len(s)
up = 0
cnt = 0
y = []
for i in range(-1, -m-1, -1):
    cs = int(s[i]) + up
    if cs < 5 or (cs == 5 and int(s[i-1]) < 5):
        cnt += cs
        y.append([cs, s[i]])
        up = 0
    else:
        cnt += 10 - cs
        y.append([10 - cs, s[i]])
        up = 1
        
print(cnt)

Solution (Python):
s = '0' + input()
m = len(s)
up = 0
cnt = 0
y = []
for i in range(-1, -m-1, -1):
    cs = int(s[i]) + up
    if cs < 5 or (cs == 5 and int(s[i-1]) < 5):
        cnt += cs
        y.append([cs, s[i]])
        up = 0
    else:
        cnt += 10 - cs
        y.append([10 - cs, s[i]])
        up = 1
        
print(cnt)

Solution (Python):
import sys
import numpy as np



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


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[:],i8[:,:])')(main)
    
    cc.compile()
else:
    from my_module import main
    N = np.array([int(_) for _ in input()])
    dp=np.zeros((len(N),2),dtype=np.int64)
    main(N,dp)

Solution (Python):
import numpy as np
from numba import njit
N = np.array([int(_) for _ in input()])
dp = np.array([[0, 0] for _ in range(len(N))])


@njit
def solve(N, dp):
    dp[0, 0] = min(N[0], 11 - N[0])
    dp[0, 1] = min(N[0] + 1, 10 - N[0])
    for i in range(1, len(N)):
        dp[i, 0] = min(dp[i - 1, 0] + N[i], dp[i - 1, 1] + 10 - N[i])
        dp[i, 1] = min(dp[i - 1, 0] + N[i] + 1, dp[i - 1, 1] + 9 - N[i])
    print(dp[-1][0])


solve(N, dp)

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

Solution (Python):
INF=10**30
N=list(map(int,list(input())))[::-1]
l=len(N)
dp=[[INF,INF] for i in range(l+1)]
dp[0][0]=0
for i in range(l):
    dp[i+1][0]=min(dp[i][0]+N[i],dp[i][1]+N[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-N[i]),dp[i][1]+(9-N[i]))
print(min(dp[l][0],dp[l][1]+1))

Solution (Python):
INF=10**30
N=list(map(int,list(input())))[::-1]
l=len(N)
dp=[[INF,INF] for i in range(l+1)]
dp[0][0]=0
for i in range(l):
    dp[i+1][0]=min([dp[i+1][0],dp[i][0]+N[i],dp[i][1]+N[i]+1])
    dp[i+1][1]=min([dp[i+1][1],dp[i][0]+(10-N[i]),dp[i][1]+(9-N[i])])
ans=min(dp[l][0],dp[l][1]+1)
print(ans)

Solution (Python):
INF=10**30
N=list(map(int,list(input())))[::-1]
l=len(N)
dp=[[INF,INF] for i in range(l+1)]
dp[0][0]=0
for i in range(l):
    dp[i+1][0]=min(dp[i+1][0],dp[i][0]+N[i])
    if N[i]!=9:
        dp[i+1][0]=min(dp[i+1][0],dp[i][1]+N[i]+1)
    dp[i+1][1]=min(dp[i+1][1],dp[i][0]+(10-N[i]))
    if N[i]!=0:
        dp[i+1][1]=min(dp[i+1][1],dp[i][1]+(10-N[i]-1))
    else:
        dp[i+1][1]=min(dp[i+1][1],dp[i][1]+9)
ans=min(dp[l][0],dp[l][1]+1)
print(ans)

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

def solve(N):
    res = 0
    flg = 0
    for n in reversed(N):
        if flg == 2:
            if n >= 5:
                flg = 1
            else:
                flg = 0
        m = flg + n
        if m == 5:
            res += 5
            flg = 2
        elif m < 5:
            res += m
            flg = 0
        else:
            res += (10 - m)
            flg = 1
    return res + flg%2


N = list(map(int, input().strip()))
print(solve(N))

Solution (Python):

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

for i in range(len(N)):
    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] + 10 - (n + 1))

print(dp[-1][0])

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


dp=0,1

for i in range(n):
  si=int(s[i])
  
  a=min(dp[0]+si,dp[1]+10-si)
  
  
  b=min(dp[0]+si+1,dp[1]+10-(si+1))
  dp=a,b
print(dp[0])

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

Solution (Python):
s='0'
s+=input()
n=len(s)
inf=float('inf')
dp=[[inf]*2 for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(2):
    si=int(s[-i-1])
    si+=j
    for a in range(10):
      ni=i+1
      nj=0
      b=a-si
      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):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=input()
l=len(n)
ans=0
d=[(0,0)]*l
d[0]=min(int(n[0]),10-int(n[0])+1),min(int(n[0])+1,10-int(n[0]))
for i in range(1,l):
    ori=min(int(n[i])+d[i-1][0],10-int(n[i])+d[i-1][1])
    ori_1=min(int(n[i])+1+d[i-1][0],10-int(n[i])-1+d[i-1][1])
    d[i]=ori,ori_1
print(d[l-1][0])