Problem:


Score: 500 points

Problem Statement

In the Kingdom of AtCoder, only banknotes are used as currency. There are 10^{100}+1 kinds of banknotes, with the values of 1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}. You have come shopping at a mall and are now buying a takoyaki machine with a value of N. (Takoyaki is the name of a Japanese snack.)

To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.

What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?

Assume that you have sufficient numbers of banknotes, and so does the clerk.

Constraints

N is an integer between 1 and 10^{1,000,000} (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print the minimum possible number of total banknotes used by you and the clerk.

Sample Input 1

36

Sample Output 1

8

If you give four banknotes of value 10 each, and the clerk gives you back four banknotes of value 1 each, a total of eight banknotes are used.

The payment cannot be made with less than eight banknotes in total, so the answer is 8.

Sample Input 2

91

Sample Output 2

3

If you give two banknotes of value 100, 1, and the clerk gives you back one banknote of value 10, a total of three banknotes are used.

Sample Input 3

314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170

Sample Output 3

243



Sample input:
36


Sample output:
8

Submission status: Accepted

Solution code:
# 解説放送
# 写経

def main():
    from itertools import islice

    inf = 18 * (10 ** 6 + 1)

    s = '0' + input()
    n = len(s)

    s = map(int, reversed(s))  # 先に一括でintにした

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

    for i, c in enumerate(islice(s, 0, n, 1)):
        for j in range(2):
            x = c + j
            if x < 10:
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)  # a=x,b=0
            if x > 0:
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))  # a=0,bに繰り下がり

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = '0' + input()
L = len(N)

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

for i in range(L):
    x = int(N[L - 1 - i])
    for j in range(2):
        for a in range(10):
            b = a - j - x
            temp1 = dp[i][j] + a + (b + 10 * (b < 0))
            temp2 = dp[i + 1][b < 0]
            dp[i + 1][b < 0] = min(temp1, temp2)

print(dp[L][0])

Submission status: Accepted

Solution code:
Ns = [int(s) for s in input()]
order = len(Ns)

dp_just = [0 for _ in range(order + 1)]
dp_plus = [0 for _ in range(order + 1)]

dp_just[0] = 0
dp_plus[0] = 1

for o in range(order):
  n = Ns[o]
  dp_just[o+1] = min(dp_just[o] + n, dp_plus[o] + (10 - n))
  dp_plus[o+1] = min(dp_just[o] + n + 1, dp_plus[o] + (9 -n))
  
print(dp_just[-1])

Submission status: Accepted

Solution code:
S=input()
N=len(S)
INF=10**9
#dp[i][j]: 下からi桁目まで見たときの枚数最小値(jは上への繰り上がりがあるか)
dp=[[INF for _ in range(2)] for __  in range(N+1)]
dp[0][0]=0
for i in range(N):
    n=int(S[N-1-i])
    ni=i+1
    for j in range(2):
        if n+j<=9:
            dp[ni][0]=min(dp[ni][0],dp[i][j]+n+j)
            dp[ni][1]=min(dp[ni][1],dp[i][j]+10-n-j)
        else:
            dp[ni][1]=min(dp[ni][1],dp[i][j])
print(min(dp[N][0],dp[N][1]+1))

Submission status: Accepted

Solution code:
n = input()

c = 0
r = 1
for x in map(int, n):
    tc = min(c + x, r + 10 - x)
    if x == 9:
        tr = r
    else:
        tr = min(c + x + 1, r + 10 - (x + 1))
    c, r = tc, tr

print(c)

Submission status: Accepted

Solution code:
import sys

ns = sys.stdin.readline().strip()
ns = ns[::-1]
ns += '0'
ns_arr = list(ns)
n_arr = [int(s) for s in ns_arr]
nl = len(n_arr)

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

dp[0][0] = 0

for j in range(nl):
    for i in range(2):
        num = n_arr[j]
        num += i

        if num < 10:
            dp[0][j+1] = min(dp[0][j+1], dp[i][j] + num)

        if num > 0:
            dp[1][j+1] = min(dp[1][j+1], dp[i][j] + (10 - num))

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

Submission status: Accepted

Solution code:
N = input()
A = [int(N[i]) for i in range(len(N))]
A.reverse()
A.append(0)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
S=input()
B0=int(S[-1])
B1=10-int(S[-1])
for s in S[::-1][1:]:
    x=int(s)
    B0,B1=min(B0+x,B1+x+1),min(B0+(10-x),B1+(10-x-1))
print(min(B0,B1+1))

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

s = input()
n = len(s)
ans = 0

dp1 = [999999999999999999] * (n+1)
dp2 = [999999999999999999] * (n+1)

# dp1[i] = 上からi桁目までピッタリ払った最小コスト
# dp2[i] = 上からi桁目を1多く払った最小コスト

dp1[0] = 0
dp2[0] = 1

for i,c in enumerate(s):
    a = int(c)

    dp1[i+1] = min(dp1[i]+a, dp2[i]+a+1)
    dp2[i+1] = min(dp1[i]+a+1, dp2[i]+(10-a-1), dp2[i]+a+2)

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

Submission status: Accepted

Solution code:
def main():
    N=input()
    X=len(N)
    INF=10**100
    dp=[[INF,INF] for i in range(0,X+1)]
    dp[0][0]=0
    dp[0][1]=1
    for j in range(1,X+1):
        dp[j][0]=min(dp[j-1][0]+int(N[j-1])%10,dp[j-1][1]+10-int(N[j-1])%10)
        if int(N[j-1])%10!=9:
            dp[j][1]=min(dp[j-1][1]+9-int(N[j-1])%10,dp[j-1][0]+int(N[j-1])%10+1)
        else:
            dp[j][1]=dp[j-1][1]+9-int(N[j-1])%10
    print(dp[X][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
X = [0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
def solve(N):
    N = [int(c) for c in N][::-1]
    p = 0
    b = 0
    for i in range(len(N)):
        c = N[i] + b
        p += X[c]
        if c == 5:
            b = 0 if i == len(N)-1 or N[i+1] < 5 else 1
        else:
            b = c > 5
    return p + b

print(solve(input()))

Submission status: Accepted

Solution code:
s=input()
a=0
b=0
c=len(s)
s='0'+s
s=s[::-1]
d=0
for i in range(c+1):
  if 0<b:
    if 4<int(s[i])+1:
      if 5==int(s[i])+1 and int(s[i+1])<5:
        a+=5
        b=0
      else:
        a+=(9-int(s[i]))
    else:
      a+=(int(s[i])+1)
      b=0
  else:
    if 4<int(s[i]):
      if int(s[i])==5 and int(s[i+1])<5:
        a+=5
      else:
        b+=1
        a+=(10-int(s[i]))
    else:
      a+=int(s[i])
print(a)

Submission status: Accepted

Solution code:
n = input()
def main(n):
    n = [0] + [int(i) for i in n] + [0]
    last = 0
    ans = 0
    last_5 = 0
    ls = []
    for i in n[::-1]:
        if i > 5:
            if last == 0 and last_5 == 0:
                ans += 10 - i
                ls.append(10 - i)
            else:
                ans += 10 - i - 1
                ls.append(10 - i - 1)
            last += 1 + last_5
            last_5 = 0
        elif i == 5:
            if last == 0 and last_5 == 0:
                ans += 5
                last = 0
                last_5 = 1
                ls.append(5)
            else:
                ans += 10 - 5  - 1
                last += 1 + last_5
                last_5 = 0
                ls.append(4)
        else:
            if last >= 1:
                if i == 4:
                    ans += 5
                    last = 0
                    last_5 = 1
                    ls.append(5)
                    continue
                else:
                    ans += 1 + i
                    ls.append(1 + i)
            else:
                ans += i
                ls.append(i)
            last = 0
            last_5 = 0
    print(ans)

if __name__ == '__main__':
    main(n)

Submission status: Accepted

Solution code:
X = [0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0]
def solve(N):
    N = [int(c) for c in N][::-1]
    p = 0
    b = 0
    for i in range(len(N)):
        c = N[i] + b
        p += X[c]
        if c == 5:
            b = 0 if i == len(N)-1 or N[i+1] < 5 else 1
        elif c > 5:
            b = 1
        else:
            b = 0
    return p + b

print(solve(input()))

Submission status: Accepted

Solution code:
N=list(input())

N.insert(0,0)
ans=0
for i in range(len(N)-1,-1,-1):
  n=int(N[i])
  if n//10>=1:
    N[i-1]=str(int(N[i-1])+1)
    continue
    
  if n==5:
    if int(N[i-1])>=5:
      N[i-1]=str(int(N[i-1])+1)
    ans+=5
  elif n>=6:
    ans+=10-n
    N[i-1]=str(int(N[i-1])+1)
  else:
    ans+=n
    
print(ans)

Submission status: Accepted

Solution code:
N = input()

DP_just = 0
DP_plus = 1

for c in N:
    d = int(c)
    last_just = DP_just
    last_plus = DP_plus
    DP_just = min(last_just + d, last_plus + 10 - d)
    d += 1
    DP_plus = min(last_just + d, last_plus + 10 - d)

print(DP_just)

Submission status: Accepted

Solution code:
N = input()

DP_just = [0]
DP_plus = [1]

for c in N:
    d = int(c)
    last_just = DP_just[-1]
    last_plus = DP_plus[-1]
    DP_just.append(min(last_just + d, last_plus + 10 - d))
    d += 1
    DP_plus.append(min(last_just + d, last_plus + 10 - d))

print(DP_just[-1])

Submission status: Accepted

Solution code:
n = input()
n = n[::-1]
n += '0'
cnt = 0
tmp = 0
for i in range(len(n)):
    a = int(n[i])
    a += tmp
    if a == 5:
        cnt += a
        if int(n[i + 1]) >= 5:
            tmp = 1
        else:
            tmp = 0
    elif a < 5:
        cnt += a
        tmp = 0
    else:
        cnt += 10 - a
        tmp = 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=list(ss())
n=list(reversed(list(map(int,n))))+[0]
#print(n)
ans=0
for i in range(len(n)):
    if n[i]>=6 or (n[i]==5 and n[i+1]>=5):
        ans+=10-n[i]
        n[i+1]+=1
    else:
        ans+=n[i]
#print(n)
print(ans)

Submission status: Accepted

Solution code:
S = input()
n = len(S)
dp = [[0] * 2 for _ in range(n+1)]

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

print(dp[n][0])

Submission status: Accepted

Solution code:
n="0"+input()
A,b,c=0,0,0
for i in n[::-1]:
    a=int(i)+b
    if a==5 and c==0:
        A+=5
        b=0
        c=1
    elif a<5:
        A+=a
        b=0
        c=0
    else:
        A+=10-a-c
        b=1
        c=0
print(A)

Submission status: Accepted

Solution code:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep = ' ', end = '\n'):
    print(*var, file=sys.stderr, end = end, sep = sep)

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

s = [0] + [int(i) for i in input()]
ans = 0
n = len(s)
for i in range(n - 1, 0, -1):
    x = s[i]
    if x > 5:
        ans += (10 - x)
        idx = i - 1
        s[idx] += 1
        while idx > 0 and s[idx] == 10:
            s[idx] = 0
            s[idx - 1] += 1
            idx -= 1
    elif x == 5 and s[i - 1] >= 5:
        ans += 5
        idx = i - 1
        s[idx] += 1
        while idx > 0 and s[idx] == 10:
            s[idx] = 0
            s[idx - 1] += 1
            idx -= 1
    else:
        ans += x
ans += s[0]
print(ans)

Submission status: Accepted

Solution code:

N=input()
cnt=0
bit=0
bitflag=0
cur=0
inf=float("inf")

Nd="".join(("0",N))


dp=[[inf for _ in range(2)] for _ in range(1000005)]
dp[0][0]=0
#print(dp)
for i in range(0,len(Nd),1):
    for j in range(2):
        x=int(Nd[len(Nd)-1-i])
        #print(x)
        x=x+j
        for a in range(0,10,1):
            ni=i+1
            nj=0
            b=a-x
            if b<0:
                nj=1
                b=b+10
            dp[ni][nj]=min(dp[ni][nj],dp[i][j]+a+b)

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

Submission status: Accepted

Solution code:
s = input()[::-1]
s += "0"
n = len(s)
dp = [[10**7 for _ in range(2)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	for j in range(2):
		x = int(s[i]) + j
		for a in range(10):
			kurisagaru = False
			if a >= x:
				b = 0
			else:
				b = 10 + a - x
				kurisagaru = True
			dp[i+1][kurisagaru] = min(dp[i+1][kurisagaru], dp[i][j]+a+b)
print(dp[n][0])

Submission status: Accepted

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

ans = 0
n_dig = len(n) # Nの桁数

carry = 0
d_next = int(n[n_dig - 1])

for i in range(n_dig - 1, 0, -1):  # n[0]はダミーなのでn[1]で止める
    d = d_next
    d_next = int(n[i - 1])

    if carry + d <= 4 or (carry + d == 5 and d_next <= 4):
        ans += d + carry
        carry = 0  # 繰り上がり
    else:
        ans += 10 - d - carry
        carry = 1

print(ans + carry)

Submission status: Accepted

Solution code:
N = map(int, input()[::-1])
a, b = 0, 9
for n in N:
    a, b = min(n+a, n+b), min(11-n+a, 9-n+b)
print(min(a, b))

Submission status: Accepted

Solution code:
N = list(input())
ans = 0
temp = [0] + [int(n) for n in N]
for i in reversed(range(1, len(N)+1)):
    if temp[i] < 5 or (temp[i] == 5 and temp[i-1] < 5):
        ans += temp[i]
    else:
        temp[i-1] += 1
        ans += (10 - temp[i])
        temp[i] = 0
ans += temp[0]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()[::-1]+'0'
n=len(s)
ans=0
flg=False
for i in range(n):
    a=int(s[i])
    if flg:
        a+=1
    if a==5:
        if int(s[i+1])>=5:
            ans+=5
            flg=True
        else:
            ans+=5
            flg=False
    elif a>5:
        ans+=10-a
        flg=True
    else:
        ans+=a
        flg=False
if flg:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = str(input())
L = len(N)
ans = 0
dp = [[0,0] for _ in range(L)]
s = list(map(int,N))
dp[0] = [s[0],11-s[0]]
for i in range(1,L):
    n = s[i]
    dp[i][0] = min(dp[i-1][0]+n,dp[i-1][1]+n)
    dp[i][1] = min(dp[i-1][1]+9-n,dp[i-1][0]+11-n)
print(min(dp[-1]))

Submission status: Accepted

Solution code:
n = list(reversed(list(map(int, input()))))
k = len(n)
dp1, dp2 = [0] * k, [0] * k
dp1[0], dp2[0] = n[0], 11-n[0]
for i, x in enumerate(n[1:], 1):
    dp1[i] = min(x+dp1[i-1], x+dp2[i-1])
    dp2[i] = min(11-x+dp1[i-1], 9-x+dp2[i-1])
print(min(dp1[-1], dp2[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = "0" + input()
ans, carry = 0, 0
for i in range(len(N) - 1, 0, -1):
    n = int(N[i]) + carry
    ans += min(10 - n, n)
    carry = 1 if n > 5 or (n == 5 and int(N[i - 1]) >= 5) else 0

print(ans + carry)

Submission status: Accepted

Solution code:
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True


def main():
    n = '0' + S()
    N = len(n)
    n = n[::-1]
    n = [int(i) for i in n]
    dp = [[0] * 2 for i in range(N+1)]
    dp[0][1] = 1

    # print(n)
    for i in range(N):
        # print(i, 'no up', dp[i][0] + n[i], dp[i][1] + n[i] + 1)
        # print(i, 'no down', dp[i][0] + 10 - n[i], dp[i][1] + 10 - (n[i] + 1))
        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] + 10 - (n[i] + 1))

    print(min(dp[N]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# たこ焼き器の価値
N = [0] + list(map(int, tuple(input().rstrip("\n"))))
# 支払額
Ncopy = N.copy()

def main():
    # 紙幣の枚数
    ans = 0

    # 繰り上げ発生時に変更
    flag = False
    for i in range(len(N)-1, 0, -1):
        # 繰り上げしない場合
        if (Ncopy[i] <= 4) or (Ncopy[i] == 5 and N[i-1] <= 4):
            ans += Ncopy[i]
            flag = False
        # 繰り上げする場合
        else:
            Ncopy[i-1] += 1
            if not flag:
                ans += 10 - N[i]
            else:
                ans += 9 - N[i]
            Ncopy[i] = 0
            flag = True

    if Ncopy[0] == 1:
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N):
    l=len(N)
    sw=0
    a=[0]*l
    for i in range(l):
        a[i]=int(N[i])
    a.insert(0,0)

    carry=0
    for i in reversed(range(l+1)):
        if a[i]<5:
            sw+=a[i] 
        elif a[i]==5 and a[i-1]<5:
            sw+=a[i] 
        else:
            sw+=10-a[i]
            tsugi=i-1
            while a[tsugi]==9:
                a[tsugi]=0
                tsugi-=1
            a[tsugi]+=1
    print(sw)
    return

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# たこ焼き器の価値
N = [0] + list(map(int, tuple(input().rstrip("\n"))))

def main():
    # 支払額
    Ncopy = N.copy()
    # 紙幣の枚数
    ans = 0

    # 繰り上げ発生時に変更
    flag = False
    for i in range(len(N)-1, 0, -1):
        # 繰り上げしない場合
        if (Ncopy[i] <= 4) or (Ncopy[i] == 5 and N[i-1] <= 4):
            ans += Ncopy[i]
            flag = False
        # 繰り上げする場合
        else:
            Ncopy[i-1] += 1
            # 最後だけ特殊
            if not flag:
                ans += 10 - N[i]
            else:
                ans += 9 - N[i]
            Ncopy[i] = 0
            flag = True

    if Ncopy[0] == 1:
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=("0"+input())[::-1]
ans=0
kuriagari=0
for i in range(len(N)):
  n=int(N[i])+kuriagari
  if n==5:
    if i+1<len(N):
      if int(N[i+1])>=5:
        ans+=(10-n)
        kuriagari=1
      else:
        ans+=n
        kuriagari=0
    else:
      ans+=n
      kuriagari=0
  elif n<=5:
    ans+=n
    kuriagari=0
  else:
    ans+=(10-n)
    kuriagari=1

print(ans)

Submission status: Accepted

Solution code:
n = input()
Nr = list(map(int,list(reversed(n))))
Nr.append(0)

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

print(ans)

Submission status: Accepted

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

# 不変
N = [0] + list(map(int, tuple(input().rstrip("\n"))))

# 計算用
Ncopy = N.copy()
ans = 0
# 繰り上げ発生時に変更
flag = False
for i in range(len(N)-1, 0, -1):
    if (Ncopy[i] <= 4) or (Ncopy[i] == 5 and N[i-1] <= 4):
        ans += Ncopy[i]
        flag = False
    else:
        Ncopy[i-1] += 1
        # 最後だけ特殊
        if not flag:
            ans += 10 - N[i]
        else:
            ans += 9 - N[i]
        Ncopy[i] = 0
        flag = True

if Ncopy[0] == 1:
    ans += 1

print(ans)

Submission status: Accepted

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

ans=0
u=0

for i in range(L-1,0,-1):
    s=int(N[i])+u
    if s < 5: 
        ans+=s
        u=0
    if s > 5:
        ans+=10-s
        u=1
    if s == 5:
        if int(N[i-1]) < 5:
            ans+=s
            u=0
        else:
            ans+=10-s
            u=1

        
s=int(N[0])+u
if s <= 5: 
    ans+=s
    u=0
if s > 5:
    ans+=10-s
    u=1

if u==1:
    ans+=1 

print(ans)

Submission status: Accepted

Solution code:
N = input()
count = 0
prev = 0
for i in range(len(N)):
  if 0 <= int(N[i]) + prev < 5:
    count += int(N[i]) + prev
    prev = 0
  elif 6 <= int(N[i]) + prev <= 9:
    count += 10 - (int(N[i]) + prev)
    prev = 1
  elif int(N[i]) + prev == 10:
    prev = 1
  else:
    if (i < (len(N) - 1) and int(N[i+1]) < 5) or i == len(N) - 1:
      count += 5
      prev = 0
    else:
      count += 5
      prev = 1
count = count + prev
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = input()
    p = int(N[0])
    o = 11 - int(N[0])
    for i in N[1:]:
        j = int(i)
        np = min(p + j, o + j)
        no = min(o + 9 - j, p + 11 - j)
        p = np
        o = no
    print(min(p,o))
main()

Submission status: Accepted

Solution code:
N = input()
ans = 0
N1 = N[::-1]

l = 0
for i in range(len(N)):
  if int(N1[i])+l==5 and i<len(N)-1 and int(N1[i+1])>=5:
    ans +=5
    l=1
    continue
  if int(N1[i])+l>10-(int(N1[i])+l):
    if i==len(N)-1:
      ans+=10-(int(N1[i])+l)+1
      continue
    ans+=10-(int(N1[i])+l)
    l=1
  else:
    ans+=int(N1[i])+l
    l=0
#print(b[::-1])
print(ans)

Submission status: Accepted

Solution code:
S = "0" + input()

digits = [int(c) for c in S.rstrip("0")]
N = len(digits)

# Track number of bills necessary to create digits[:i]
# Can either pay exact or overpay by one bill to flip the sign of the balance
dpPos = [None] * len(digits)
dpNeg = [None] * len(digits)

dpPos[-1] = digits[-1]
dpNeg[-1] = 10 - digits[-1]

for place in reversed(range(len(digits) - 1)):
    # Positive balance case
    exact = digits[place]
    dpPos[place] = exact + min(dpPos[place + 1], 1 + dpNeg[place + 1])
    # Negative balance case
    exact = 10 - digits[place] - 1
    dpNeg[place] = exact + min(dpNeg[place + 1], 1 + dpPos[place + 1])
print(dpPos[0])

Submission status: Accepted

Solution code:
S = "0" + input()

digits = [int(c) for c in S.rstrip("0")]
N = len(digits)

# Track number of bills necessary to create digits[:i]
# Can either pay exact or overpay by one bill to flip the sign of the balance
dpPos = [None] * len(digits)
dpNeg = [None] * len(digits)

dpPos[-1] = digits[-1]
dpNeg[-1] = 10 - digits[-1]

for place in reversed(range(len(digits) - 1)):
    # Positive balance case
    exact = digits[place]
    overpay = exact + 1
    dpPos[place] = min(exact + dpPos[place + 1], overpay + dpNeg[place + 1])
    # Negative balance case
    exact = 10 - digits[place] - 1
    overpay = exact + 1
    dpNeg[place] = min(exact + dpNeg[place + 1], overpay + dpPos[place + 1])
print(dpPos[0])

Submission status: Accepted

Solution code:
# maspy
p=list(map(int,input()))

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

Submission status: Accepted

Solution code:
n = list(map(int, list(input())))
m = len(n)

DP = [[float("inf")]*2 for i in range(m+1)]
DP[0] = [0,1]

for i in range(m):
    # tight
    tmp = float("inf")
    for j in range(10):
        if j == 0:
            tmp = min(tmp, DP[i][1]+9-n[i])
        elif j <= n[i]:
            tmp = min(tmp, DP[i][1]+j+10+j-1-n[i])
        else:
            tmp = min(tmp, DP[i][0]+j+j-1-n[i])
    DP[i+1][1] = tmp

    # not tight
    tmp = float("inf")
    for j in range(10):
        if j < n[i]:
            tmp = min(tmp, DP[i][1]+j+(10+j)-n[i])
        else:
            tmp = min(tmp, DP[i][0]+j+j-n[i])
    DP[i+1][0] = tmp

print(DP[-1][0])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')

s = "0"+s

lst1 = []

for i in range(len(s)):
    lst1.append(int(s[i]))

n = len(lst1)-1

res = 0

for i in range(n,-1,-1):
    if lst1[i] <= 4: #自分で払ったほうが良い
        res += lst1[i]
    elif lst1[i] == 5: #5の場合、その上の桁によって話が変わってくる
        if lst1[i-1] >= 5: #どうせ次の桁で多くなるなら
            res += 5 #おつりでもらって
            lst1[i-1] += 1 #次の桁を1枚多く払う
        else: #そうでないなら、素直にその桁は5枚払う。
            res += 5
    else: #お釣りをもらったほうが良い
        res += 10-lst1[i]
        lst1[i-1] += 1 #一個上の桁で払う金が一枚多くなる
print(res)

Submission status: Accepted

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

cnt1=0
cnt2=0
kkk=0

for i in range(len(N)):
    if N[i]<=3:
        cnt1+=N[i]
        kkk=0
    
    elif N[i]==4:
        if kkk==0:
            cnt1+=4
        else:
            if i+1<len(N) and N[i+1]>=5:
                cnt1+=5  
            else:
                cnt1+=4
                kkk=0
                
    elif N[i]==5:
        
        if kkk==1:
            cnt1+=4
            
        else:
            if i+1==len(N):
                cnt1+=5
            elif N[i+1]<=4:
                cnt1+=5  
            else:
                cnt2+=1
                cnt1+=4
                kkk=1
                
    else:
        if kkk==0:
            cnt2+=1
            kkk=1
            
        cnt1+=9-N[i]

ans=cnt1+2*cnt2
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    # dp[i][0 or 1]:=1.上からi桁目までぴったり払える最小の枚数, 2.i桁目を1余分に払っている
    S = list(map(int, '0'+input()))
    l = len(S)
    dp = [[1e18]*2 for _ in range(1001001)]
    dp[0][0]=0
    for i in range(l):
        k = S[i]
        dp[i+1][0] = min(dp[i+1][0], dp[i][0]+k) # 1の位そのまま
        dp[i+1][1] = min(dp[i+1][1], dp[i][0]+k+1) # 1の位に1加える
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+10-k) # 上の桁で1余分に払っているのでお釣りが出る
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+10-k-1) # 1の位も1余分に払うのでお釣りが1減る
    print(dp[l][0])

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input()
n = n[::-1]
l = len(n)
ans = 0
flg = 0
x = []
for j in range(l):
  i = n[j]
  i = int(i)
  i += flg
  if i >= 6:
    ans += (10-i)
    flg = 1
  elif i == 5:
    if j == l-1:
      ans += i
      flg = 0
    elif int(n[j+1]) >= 5:
      ans += (10-i)
      flg = 1
    else:
      ans += i
      flg = 0
  else:
    ans += i
    flg = 0
if flg:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = "0" + input()
n = list(map(int, list(n)))
n.reverse()

pay = 0
turi = 0

pls = 0
for i in range(len(n)):
  val = n[i] + pls
  pls = 0
  if val < 5:
    pay += val
  elif val == 5:
    pay += val
    if n[i + 1] >= 5:
      pls = 1
  else:
    turi += 10 - val
    pls = 1

ans = pay + turi
print(ans)

Submission status: Accepted

Solution code:
N = list(map(int, input()))
N.insert(0, 0)
count = 0
for i in range(len(N)-1, -1, -1):
    if N[i] <= 4 or (N[i] == 5 and N[i-1] <= 4):
        count += N[i]
    else:
        count += 10 - N[i]
        N[i-1] = N[i-1] + 1
print(count)

Submission status: Accepted

Solution code:
N = [int(x) for x in input()]


def solve(N):
    # n円の場合、n+1円の場合
    # 繰り上げる方がいいのか繰り上げない方がいいのか判断している
    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))

Submission status: Accepted

Solution code:
S = input().strip()

num = list(map(int, list(S)))
num.reverse()
num.append(0)

ans = 0
for i in range(len(S)):
    n = num[i]
    if n < 5:
        ans += n
    if n > 5:
        ans += 10-n
        num[i+1] += 1
    if n == 5:
        ans += 5
        if num[i+1] >= 5:
            num[i+1] += 1


print(ans+num[-1])

Submission status: Accepted

Solution code:
N = input()
n = [0]*(len(N) + 1)
ans = 0
for i in range(len(N)):
    n[i] = int(N[len(N) - 1 - i])
for i in range(len(n)):
    if n[i] < 5:
        ans += n[i]
    elif n[i] == 5:
        if n[i+1] >= 5:
            ans += 10 - n[i]
            n[i+1] += 1
        else:
            ans += 5
    else:
        ans += 10 - n[i]
        n[i+1] += 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = list(input())
N.insert(0, '0')
count = 0
for i in range(len(N)-1, -1, -1):
    if int(N[i]) <= 4:
        count += int(N[i])
    elif int(N[i]) == 5 and int(N[i-1]) <= 4:
        count += int(N[i])
    else:
        count += 10 - int(N[i])
        N[i-1] = str(int(N[i-1]) + 1)

print(count)