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:
import sys
read = sys.stdin.readline


# 下の桁から貪欲に見ていくと解ける
# 1の位が4以下ならそのまま紙幣で支払うのが得→自身をそのまま答えに採用 (枚数として加算)
# 6以上ならばお釣り狙いのほうが得→自身は0にセットして、上位桁を+1する (枚数として10-自身を加算)
# 5ちょうどのときは、お釣りもそのまま払っても枚数は変わらない。だけど555みたいに、上位桁に+1すると得になる可能性がある。
# 555→15枚, 1000-445→15枚
# つまり5が出たときは更に上位の桁を見て、4以下ならそのまま払うほうが得,5以上なら桁上りのほうが得

# 5ちょうどのときは？ #お釣りもそのまま払っても同じ。だけど上位 お釣り狙いだと上の桁が多くなって支払う金額が増える可能性がある？
# 5ピッタリのときに上位桁に+1すると悪くなる場合が存在する 455 とは 15にってしまう
# 5ピッタリのときはどうするのがよいのか？

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

N = N[::-1]
ans = 0
# agari = 0
# is_pre5 = False
# for n in N:
#     n = int(n) + agari
#     print(n, ans)
#     if is_pre5:
#         if n == 5:
#             ans += n
#             continue

#         if n < 5:
#             # そのまま支払う
#             ans += n
#             agari = 0
#         else:
#             # 桁上り
#             ans += 9 - n
#             agari = 1
#     else:
#         if n == 5:
#             is_pre5 = True
#             ans += n
#             agari = 0
#             # もし5だったら5が終わるまでなめる
#         elif n < 5:
#             ans += n
#             agari = 0
#         else:
#             ans += 10 - n
#             agari = 1
#     if n != 5:
#         is_pre5 = False

i = 0
lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    # print(hi, lo, i)
    if lo == 5 and hi == 5:
        # 5が連続してた場合
        # 5の最後まで移動(移動の道中は 5+4+4...としていく)
        # 5じゃなくなったhiに対して足し算する必要がある。
        ans += 5
        i += 1
        while i < len(N) - 1 and N[i + 1] == '5':
            ans += 4
            # print(i)
            i += 1
        ans += 4
        # low = N[i]
        hi = int(N[i + 1]) + 1
        # print(hi, lo, i)

        # loが5以外のとき (お釣りが良いか、そのまま払うのが良いか考えるだけ)
    elif lo == 5:
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:  # 5が連続しないときもここに入る
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  # 上の桁が繰り上がる
    lo = hi  # 桁を一つずらす
    i += 1


print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

    return dp[n-1][0]

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

Submission status: Accepted

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

Submission status: Accepted

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

main()

Submission status: Accepted

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32

def solve(N: "List[int]"):
    # N=36を考える
    # l = list(map(int, list(str(N))))
    dp = 0,1
    for i in N:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = list(input())

N.reverse()

ans = 0
flag = False
L = len(N)
for i,s in enumerate(N):
    n = int(s)
    
    if flag:
        n += 1
    
    if n<5:
        ans += n
        flag = False
    elif n>5:
        ans += 10-n
        flag = True
    else:
        if i==L-1:
            ans += n
            flag = False
            break
            
        if int(N[i+1])<5:
            ans += n
            flag = False
        else:
            ans += 10-n
            flag = True

if flag:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
l=[0]+[int(i) for i in input()]
l.reverse()
su=0
for i in range(len(l)):
    if l[i]>5:
        l[i]=10-l[i]
        l[i+1]+=1
    elif l[i]==5 and l[i+1]>4:
        l[i+1]+=1
    su+=l[i]
print(su)

Submission status: Accepted

Solution code:
n=input()
ans=0
x=-1
n=n+str(0)
for i in range(len(n)-1):
    v=int(n[i])
    w=int(n[i+1])
    if x<0:
        if v<5:
            ans+=v
        elif v==5:
            if w>=5:
                ans+=9-v+2
                x+=1
            else:
                ans+=v
        else:
            ans+=9-v+2
            x+=1
    else:
        if v<4:
            ans+=v
            x-=1
        elif v==4:
            if w>=5:
                ans+=9-v
            else:
                ans+=v
                x-=1
        else:
            ans+=9-v

print(ans)

Submission status: Accepted

Solution code:
#import sys
#inf = sys.maxsize

n = str(input())
#l = len(str(n))

'''
a = []
for i in range(l):
    if m[i] <= 5:
        a.append(0)
    elif m[i] > 5:
        a.append(1)

for i in range(l):
    if i < l-1 and a[i+1] == 1 and m[i] == 5:
        a[i] = 1

p = []
for i in range(l):
    if a[i] == 0:
        if i < l-1 and a[i+1] == 1:
            p.append(m[i]+1)
        else:
            p.append(m[i])
    elif a[i] == 1:
        p.append(0)

pp = ''
for i in range(l):
    pp += str(p[i])
if pp[0] == '0':
    pp = '1' + pp
pp = int(pp)
oo = pp - n
print(pp)
print(oo)
ppp = [int(str(pp)[i]) for i in range(len(str(pp)))]
ooo = [int(str(oo)[i]) for i in range(len(str(oo)))]

print(sum(ppp) + sum(ooo))
'''
dp = [0, 1] #dp[0]: ちょうど dp[1]: 1多い

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import log10, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()

dp = (0, 1)  # 左:ちょうど  右:1だけ多い
for i in N:
	i = int(i)
	dp = (min(dp[0] + i, dp[1] + 10 - i), min(dp[0] + i + 1, dp[1] + 9 - i))
print(dp[0])

Submission status: Accepted

Solution code:
a=b=0
for n in map(int,'0'+input()):a,b=n+min(a,b),9-n+min(b,a+2)
print(min(a,b))

Submission status: Accepted

Solution code:
digits = [0] + [int(c) for c in input()]

dp = [0, 1]
for digit in reversed(digits):
    dp0, dp1 = dp
    dp[0] = min(dp0, dp1 + 1) + digit
    dp[1] = min(dp0, dp1 - 1) + 10 - digit

print(min(dp))

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = input()
m = len(n)
n = n[::-1] + '0'

dp = [[inf]*2 for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    x = int(n[i])
    for j in range(2):
        x += j
        for a in range(10):
            b = a-x
            if a >= x:
                dp[i+1][0] = min(dp[i+1][0],dp[i][j]+a+b)
            else:
                dp[i+1][1] = min(dp[i+1][1],dp[i][j]+a+10+b)
ans = min(dp[-1][0],dp[-1][1]+1)
print(ans)

Submission status: Accepted

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

dp = [0, float('inf')]
# dp = [桁上げしてない, 桁上げあった]
for n in N :
  ndp = [0] * 2
  ndp[0] = min(dp[0] + n, dp[1] + n)
  ndp[1] = min(dp[0] + 11 - n, dp[1] + 9 - n)
  dp = ndp

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

Submission status: Accepted

Solution code:
s = input()
nums = list(reversed([int(c) for c in s])) + [0]
r = (0, 1) # no borrow, with borrow
for i in range(len(nums)):
    # print(r)
    next_no_borrow = min(r[0] + nums[i], r[1] + nums[i] + 1)
    next_borrow = min(10 - nums[i] + r[0], 9 - nums[i] + r[1])
    r = (next_no_borrow, next_borrow)
print(min(r))

Submission status: Accepted

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

import sys
import math
import itertools

def main():
    ns = list(map(int, sys.stdin.readline().strip()))
    ns.reverse()
    ns.append(0)

    ans = 0
    lastpay = 0

    for i in range(len(ns)):
        if lastpay == 0:
            if ns[i] <= 4 or (ns[i] == 5 and ns[i + 1] <= 4):
                ans += ns[i]
                lastpay = 0
            else:
                ans += 1 + (10 - ns[i])
                lastpay = 1
        else:
            if lastpay + ns[i] <= 4 or (lastpay + ns[i] == 5 and ns[i + 1] <= 4):
                ans += ns[i]
                lastpay = 0
            else:
                ans += 1 - 1 + (9 - ns[i])
                lastpay = 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

for idx, num in enumerate(n):
    if num == 10:
        n[idx+1] += 1
    elif num == 5:
        if n[idx+1] >= 5:
            n[idx+1] += 1
            count += 10 - num
        else:
            count += num

    elif num <= 4:
        count += num
    else:
        count += 10 - num
        n[idx+1] += 1

print(count)

Submission status: Accepted

Solution code:
def main():
    s = input()
    s = list(reversed(s))
    s.append('0')
    dp = [[10**10 for _ in range(2)] for _ in range(len(s)+1)]
    dp[0][0] = 0
    for i in range(len(s)):
        for j in range(2):
            x = int(s[i])
            x += j
            for a in range(10):
                ni = i+1
                nj = 0
                b = a-x
                if b < 0:
                    nj = 1
                    b += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b)
    print(dp[len(s)][0])


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

def main():
    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)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
d,e=0,0
for x in list("0"+input()):
	d,e=int(x)+min(e,d),9-int(x)+min(e,d+2)
print(min(d,e))

Submission status: Accepted

Solution code:
nn = [0] + list(map(int, list(input())))
dp0, dp1 = 0, 0
for i in range(len(nn)):
	dp0, dp1 = nn[i] + min(dp1, dp0), 9 - nn[i] + min(dp1, dp0 + 2)
print(min(dp0, dp1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

L=list(map(int,input())); n=len(L)
L.reverse();L.append(0)
for i in range(n):

  if L[i] >= 6:
    count += 10-L[i]
    L[i] = 0; L[i+1] += 1

  elif L[i] == 5 and L[i+1] >= 5:
    count += 10-L[i]
    L[i] = 0; L[i+1] += 1

print(count + sum(L))
# print(L)

Submission status: Accepted

Solution code:
m=str(raw_input())
n=[int(i) for i in m]
n.insert(0,0)
l=len(n)
ans=0
for i in range(l-1,-1,-1):
    current=n[i]
    if(current<5):
        ans+=current
    elif(current==5):
        ans+=current
        if(n[i-1]>=5):
            n[i-1]+=1
    else:
        ans+=10-current
        n[i-1]+=1
print ans

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = [0] + list(map(int, list(input())))
ans = 0
c_in = 0

while n:
    s = n.pop()
    s += c_in
    if 0 <= s <= 4:
        ans += s
        c_in = 0
    elif 6 <= s:
        ans += abs(10 - s)
        c_in = 1
    else:
        ans += 5
        if 5 <= n[-1]:
            c_in = 1
        else:
            c_in = 0

print(ans)

Submission status: Accepted

Solution code:
N_str = input()

ln = len(N_str)
ans = 0
no_mu, move_up = int(N_str[-1]), 11 - int(N_str[-1])
for i in range(2, ln + 1):
    n = int(N_str[-i])
    no_mu, move_up = n + min(no_mu, move_up), min(11 - n + no_mu, 9 - n + move_up)
print(min(no_mu, move_up))

Submission status: Accepted

Solution code:
N = ("00"+input())[::-1]

ans = 0
carry = 0
for i in range(len(N)-1):
    n = int(N[i])
    nextn = int(N[i+1])
    if carry == 1:
        carry = 0
        n += 1

    if n <=4:
        ans += n
    elif n >= 6:
        ans += 10-n
        carry = 1
    else: # n==5
        if nextn <= 4:
            ans += n
        else:
            ans += 10-n
            carry = 1

print(ans)

Submission status: Accepted

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

def calc(k):
    return 10-k

S = [0] + list(map(int, readline().strip()))

M = len(S)
inf = 10**9+7
dpn = [inf]*M
dpk = [inf]*M
dpn[0] = 0
dpk[0] = 1
pre = 0
for i in range(1, M):
    s = S[i]
    if s != 9:
        dpn[i] = min(dpn[i-1] + s, dpk[i-1] + calc(s))
        dpk[i] = min(dpn[i-1] + s+1, dpk[i-1] + calc(s+1))
        pre = i
    else:
        dpn[i] = min(dpn[i-1] + s, dpk[pre] + calc(s))
        dpk[i] = dpk[pre]

print(dpn[-1])

Submission status: Accepted

Solution code:
N = input()

nagasa = len(N)
flag = 0
res = 0
for i in range(nagasa):
	s = nagasa - i - 1
	n = int(N[s])

	if flag == 2:
		if n <= 4:
			flag = 0
			res += n
		elif n == 5:
			flag = 1
			res += 4
		elif n >= 6:
			flag = 1
			res += 9 - n
	else:
		if flag == 1:
			n += 1
		if n == 5:
			flag = 2
			res += 5
		elif n > 5:
			flag = 1
			res += 10 - n
		else:
			flag = 0
			res += n

if flag == 1:
	print(res + 1)
else:
	print(res)

Submission status: Accepted

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

def main():
    S = input()
    l = len(S)
    S = "0"+ S
    up = 0
    ans = 0
    for i in range(l):
        num = int(S[-i-1])+up
        if num == 5:
            ans += 5
            if int(S[-i-2]) < 5:
                up = 0
            else:
                up = 1
        elif num > 5:
            ans += 10-num
            up = 1
        else:
            ans += num
            up = 0
            
    print(ans+up)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    n = [int(c) for c in "0" + input()]
    I = len(n)
    ans = 0
    for i in range(I-1, -1, -1):
        b = n[i]
        if b < 5:
            ans += b
        elif b == 5:
            c = n[i-1]
            ans += b
            if c >= 5:
                n[i-1] += 1
        else:
            ans += 10 - b
            n[i-1] += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    n = [int(c) for c in "0" + input()]
    I = len(n)
    ans = 0
    for i in range(I-1, -1, -1):
        b = n[i]
        if b < 5:
            ans += b
        elif b == 5:
            for j in range(2):
                c = n[i-j-1]
                cn = 5 - j
                if c < cn:
                    ans += b
                    break
                elif c > cn:
                    ans += b
                    n[i-1] += 1
                    break
            else:
                ans += b
                n[i-1] += 1
        else:
            ans += 10 - b
            n[i-1] += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = list(input())
n = [int(val) for val in reversed(N)] + [0]
ln = len(N)

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

ans += n[ln]
print(ans)

Submission status: Accepted

Solution code:
def main():
  n=list(input())
  n=[int(i) for i in reversed(n)]
  l=len(n)
  n.append(0)
  
  ans=0
  for i in range(l):
    if n[i]<=4:
      a=n[i]
    elif n[i]==5:
      if n[i+1]<=4:
        a=n[i]
      else:
        a=10-n[i]
        n[i+1]+=1
    else:
      n[i+1]+=1
      a=10-n[i]
    ans+=a
  ans+=n[l]
  print(ans)  
if __name__=='__main__':
    main()

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

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[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:
n = [0]
n1 = list(input())
n2 = [int(s) for s in n1]
nn = len(n1)
n = n + n2
# print(n)

ans = 0
for i in range(nn, -1, -1):
    # print(n[i])
    if n[i] >= 10:
        n[i - 1] += 1
    elif n[i] == 5:
        if n[i - 1] >= 5:
            ans += n[i]
            n[i - 1] += 1
        else:
            ans += n[i]
    elif n[i] < 5:
        ans += n[i]
    else:
        ans += 10 - n[i]
        n[i - 1] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def main():
    n = list(input())
    l = len(n)
    ans = 0
    for i in range(l):
        n[i] = int(n[i])
    for i in range(l-1,-1,-1):
        if n[i] <= 4:
            ans += n[i]
        elif n[i] == 5 and (i == 0 or n[i-1] <= 4):
            ans += n[i]
        else:
            ans += 10 - n[i]
            n[i] = 0
            if i != 0:
                n[i-1] += 1
        if i == 0 and n[i] == 0:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  n=list(input())
  n=[int(i) for i in n]
  l=len(n)
  
  dp=[[0]*2 for _ in range(l+1)]
  if n[0]>=5:
    dp[0][1]=1
    
  for i in range(l):
      dp[i+1][0]=min(dp[i][0]+n[i],dp[i][1]+10-n[i])
      dp[i+1][1]=min(dp[i][0]+n[i]+1,dp[i][1]+9-n[i])
      
  #print(dp)
  print(dp[l][0])

if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
n = len(s)
dp = [ [0,1e18] for i in range(n+1) ]
for i in range(n):
  d = int(s[i])
  dp[i+1][0] = min(dp[i][0], dp[i][1])+d
  dp[i+1][1] = min(dp[i][0], dp[i][1]-2)+11-d
print(min(dp[n][0],dp[n][1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
n = len(s)
dp = [ [0,0] for i in range(n) ]
dp[0][0] = ord(s[0])-ord('0')
dp[0][1] = 11-(ord(s[0])-ord('0'))
for i in range(n-1):
  d = ord(s[i+1])-ord('0')
  dp[i+1][0] = min(dp[i][0], dp[i][1]) + d
  dp[i+1][1] = min(dp[i][0]+11-d, dp[i][1]+9-d)
print(min(dp[n-1][0],dp[n-1][1]))

Submission status: Accepted

Solution code:
N = list(input())
N = list(map(int, N))
N = [0] + N
n = len(N)

answer = 0
for i in range(n - 1, -1, -1):
    j = N[i]
    if j == 10:
        N[i - 1] += 1
        continue
    if j == 5 and N[i - 1] >= 5:
        N[i - 1] += 1
        answer += 5
    elif j <= 5:
        answer += j
    else:
        N[i - 1] += 1
        answer += 10 - j

print(answer)

Submission status: Accepted

Solution code:
N = list(input())
N = list(map(int, N))
N = [0] + N
n = len(N)

answer = 0
for i in range(n - 1, -1, -1):
    if N[i] == 10:
        N[i - 1] += 1
        continue
    if N[i] == 5 and N[i - 1] >= 5:
        N[i - 1] += 1
        answer += 5
    elif N[i] <= 5:
        answer += N[i]
    else:
        N[i - 1] += 1
        answer += 10 - N[i]

print(answer)

Submission status: Accepted

Solution code:
s=input()
l=len(s)
cnt=0
A=[]
A.append(0)
for i in range(l):
  A.append(int(s[i]))
for i in reversed(range(l+1)):
  if A[i]<5 or (A[i]==5 and A[i-1]<5):
    cnt+=A[i]
  else:
    A[i-1]+=1
    cnt+=(10-A[i])
    A[i]=0
print(cnt)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = '0' + input()

    ans = 0
    flag = 0

    for i in range(len(n)-1, 0, -1):
        if int(n[i]) + flag == 10:
            flag = 1
        elif int(n[i]) + flag > 5 or (int(n[i]) + flag == 5 and int(n[i-1]) > 4):
            ans += 10 - int(n[i]) - flag
            flag = 1
        else:
            ans += int(n[i]) + flag
            flag = 0

    if flag == 1:
        ans += 1

    print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N = list(map(int, input().strip()))[::-1]
ans = 0
before = 0
L = len(N)
for i, c in enumerate(N):
    n = c + before
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == L:
            before = 0
            ans += n
            continue
        if N[i+1] < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)

Submission status: Accepted

Solution code:
*s,a=map(int,input()+'000')
for i in range(len(s)-1):
  if s[i]>5or s[i]>4<s[i+1]:
    s[i+1]+=1
    a+=10-s[i]
  else:
    a+=s[i]
print(a)

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
s = input()
l = len(s)
cnt = 0
ls = []
ls.append(0)
ls.append(0)
for i in range(l):
    ls.append(int(s[i]))
for i in range(l+1):#下から回す
    if 6<= ls[-i-1] or (ls[-i-1] ==5 and ls[-i-2] >=5):
        ls[-i-1] = 10 -ls[-i-1] #おつりを代入
        ls[-i-2] += 1 #繰り上がり
print(sum(ls))

Submission status: Accepted

Solution code:
# 解説放送
# 写経

def main():
    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(s):  # islice不要だった
        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:
# 解説放送
# 写経

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