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:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    L = list(map(int, reversed(li())))
    n = len(L)
    payment = L[:]
    payment.append(0)

    ans = 0
    carry = False
    for i in range(n):
        if 5 < payment[i] or (5 == payment[i] and 5 <= payment[i+1]):
            ans += 9 - L[i] if carry else 10 - L[i]
            payment[i] = 0
            payment[i+1] += 1
            carry = True
        else:
            carry = False
    
    # print(L)    
    # print(list(reversed(payment)))
    ans += sum(payment)
    

    # ans = 0
    # ans += sum(payment)

    # a = int(''.join(list(map(str, reversed(L)))))
    # b = int(''.join(list(map(str, reversed(payment)))))
    # # print(f"required {a}, paid: {b}")
    # ans += sum(map(int, list(str(b - a))))

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = input()
N = N[::-1]+"0"
ans = 0
up = 0
for i,n in enumerate(N):
    d = int(n)+up
    if 5 < d or (d == 5 and i < len(N)-1 and int(N[i+1]) >= 5):
        ans += (10-d)
        up = 1
    else:
        ans += d
        up = 0
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ns()

ans = [0, 1000000000]
kuri = [0, 0]
five = 0
for n in N[::-1]:
    n = int(n)
    # print(ans)
    ans_old = [ans[0], ans[1]]
    ans[0] = min(ans_old[0] + n, ans_old[1] + n + 1)
    ans[1] = min(ans_old[0] + 10 - n, ans_old[1] + 9 - n)
print(min(ans[0], ans[1] + 1))

Submission status: Accepted

Solution code:
N=input()
N='0'+N
M=len(N)
INF=10**12
DP1=[INF]*(M+1)
DP2=[INF]*(M+1)
DP1[0]=0
for i in range(M):
  DP1[i+1]=min(DP1[i]+int(N[i]),DP2[i]+10-int(N[i]))
  DP2[i+1]=min(DP1[i]+int(N[i])+1,DP2[i]+9-int(N[i]))
print(min(DP1[M],DP2[M]+1))

Submission status: Accepted

Solution code:
s = "0"+input()
ans = 0
n = len(s)
f = 0
p = 0
for i in range(1,n+1):
    n = int(s[-i])
    # n += f
    if p+(n>4) > 5:
        f = 1
    else:
        # ans += f
        f = 0
    n += f
    ans += min(n,10-n)
    p = n
# ans += f
print(ans)

Submission status: Accepted

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

ans = 0
carry = 0   #0 or 1 or 2. when 2, it means that it's optional between 0 and 1.
for i in range(len(N) - 1, -1, -1):
    if carry == 2:
        if N[i] >= 5:
            digit = N[i] + 1
            carry = 1
            ans += (10 - digit)
        else:
            digit = N[i]
            carry = 0
            ans += digit
    else:
        digit = N[i] + carry
        if digit >= 6:
            carry = 1
            ans += (10 - digit)
        elif digit <= 4:
            carry = 0
            ans += digit
        else:
            carry = 2
            ans += digit
        

if carry == 1:
    ans += carry

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)

Submission status: Accepted

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

ans = 0
dp1 = [0]*(n+1)
dp0 = [0]*(n+1)

dp1[0] = 1

for i in range(n):
  k = int(s[i])
  if k < 5:
    dp0[i+1] = dp0[i] + k
  elif k > 5:
    dp0[i+1] = dp1[i] + 10-k
  else:
    if i == 0:
      dp0[i+1] = dp0[i] + k
    elif int(s[i-1]) < 5:
      dp0[i+1] = dp0[i] + k
    else:
      dp0[i+1] = dp1[i] + 10-k
  k += 1
  if k == 10:
    dp1[i+1] = dp1[i]
  elif k < 5:
    dp1[i+1] = dp0[i] + k
  elif k > 5:
    dp1[i+1] = dp1[i] + 10-k
  else:
    if i == 0:
      dp1[i+1] = dp0[i] + k
    elif int(s[i-1]) < 5:
      dp1[i+1] = dp0[i] + k
    else:
      dp1[i+1] = dp1[i] + 10-k

print(dp0[n])

Submission status: Accepted

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

ans = 0

sub = 0
judge = False
for i in range(n-1, -1, -1):
  key = int(s[i])+sub
  if key <= 4:
    ans += key
    sub = 0
  elif key == 5:
    ans += 5
    if i == 0:
      sub = 0
    elif int(s[i-1]) <= 4:
      sub = 0
    else:
      sub = 1
  else:
    ans += 10-key
    sub = 1
ans += sub
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: str):
    # 下の桁から貪欲？
    N = "0" + N
    ans = 0
    kuriagari = 0
    for i in reversed(range(len(N))):
        n = int(N[i])
        if kuriagari == 1:
            kuriagari = 0
            n += 1
        if 0 <= n <= 4:
            ans += n
        elif n == 5:
            # print("上の桁を見て決める")
            k = i-1
            if 0 <= int(N[k]) <= 4:
                # print("桁上がらない")
                ans += 5
            else:
                # print("桁上がる")
                ans += 5
                kuriagari = 1
        else:
            ans += 10 - n
            kuriagari = 1
        # print("現状", ans, kuriagari)
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)
    N = str(a)  # type: str
    solve(N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
s = "".join([ i for i in reversed(s)]) + "0"
 
INF = 10 ** 32
n = len(s)
dp = [ [INF]*2 for _ in range(n)]
 
dp[0][0] = 0
 
for i in range(n-1):
    x = int(s[i])
    dp[i+1][0] = min( dp[i][0]+x, dp[i][1]+x )
    dp[i+1][1] = min( dp[i][0]+1+(10-x), dp[i][1]+(9-x) )
 
print(min(dp[n-1][0], dp[n-1][1]))

Submission status: Accepted

Solution code:
import sys

def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし

N = [0] + LI2()
n = len(N)

dp1 = [0]*(n)
dp2 = [0]*(n)

# Nを N_1N_2…N_(n-1) と表す
# またf(a)をa円払うときの自分と店員が使う紙幣の枚数の和の最小値とする
# このとき、f(N_1…N_k) = min(f(N_1…N_(k-1))+N_k,f(N_1…(N_(k-1)+1))+10-N_k) が成立する
# ここで、dp1[i] = f(N_1…N_i),dp2[i] = f(N_1…(N_i+1)) と定めdpする

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

print(dp1[n-1])

Submission status: Accepted

Solution code:
s = input()[::-1]
size = len(s)
s += "4"

a, b = 0, 0

for i in range(size):
    v1, v2 = int(s[i]), int(s[i+1])
    if v1+b>=6 or (v1+b>=5 and v2>=5):
        a += 10-v1-b
        b = 1
    else:
        a += v1+b
        b = 0

print(a+b)

Submission status: Accepted

Solution code:
s = input()[::-1]
size = len(s)
s += "4"

ans = 0
bef = 0

for i in range(size):
    v1 = int(s[i])
    v2 = int(s[i+1])
    if v1+bef>=6 or (v1+bef>=5 and v2>=5):
        ans += 10-(v1+bef)
        bef = 1
    else:
        ans += (v1+bef)
        bef = 0

ans += bef
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

#右からi桁目、繰り上げあり1、繰り上げ無し0
dp=[[0]*2 for _ in range(len(n)+1)]

nrev=n[::-1]
nrev.append(0)
dp[0][0]=nrev[0]
dp[0][1]=10-nrev[0]
#print(0,dp)
for i in range(1,len(n)+1):
    dp[i][0]=min(dp[i-1][0]+nrev[i],dp[i-1][1]+(nrev[i]+1))
    dp[i][1]=min(dp[i-1][0]+(10-nrev[i]),dp[i-1][1]+(10-(nrev[i]+1)))
    #print(i,nrev[i],dp)

print(min(dp[-1]))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = S()
    a = [int(c) for c in s]

    dp = [0, 1]
    for c in a:
        np = [dp[0] + c, dp[0] + c + 1]
        if np[0] > dp[1] + (10 - c):
            np[0] = dp[1] + (10 - c)
        if np[1] > dp[1] + (9 - c):
            np[1] = dp[1] + (9 - c)
        dp = np

    return dp[0]

print(main())

Submission status: Accepted

Solution code:
def main():
    N = list(map(int, list(input())))
    N = N[::-1] + [0]

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

    print(ans + N[len(N)-1])

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[:-1])))
    N = N[::-1] + [0]

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

    print(ans + N[len(N)-1])

main()

Submission status: Accepted

Solution code:
s=input()[::-1]+'0'
d=[0,1]
for c in s:
    x=int(c)
    d=[x+min(d[0],1+d[1]),min(1+d[0],d[1])+9-x]
print(min(d))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
n = input()
x = len(n)
inf = 10 ** 9
#dp[i][flg]...i桁目まで、未満フラグ=1
dp = [[inf] * 2 for _ in range(x+1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(x):
    s = int(n[i])
    dp[i+1][0] = min(dp[i][0] + s, dp[i][1] + 10 - s)
    dp[i+1][1] = min(dp[i][0] + s + 1, dp[i][1] + 9 - s)

print(dp[x][0])

Submission status: Accepted

Solution code:
n = input()
l = list(map(int, str(n)))

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

for i, v in enumerate(l):
    dp[i+1][0] = min(dp[i][0] + v, dp[i][1] + (10 - v))
    dp[i+1][1] = min(dp[i][0] + v + 1, dp[i][1] + (10 - v) - 1)

print(dp[-1][0])

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = LSI()
dp = [[INF]*2 for _ in range(len(N)+1)] #dp[i][0]が下からi桁めをぴったり払う最低枚数
dp[0][0] = 0
for i in range(len(N)):
    d = N[-(i+1)]
    dp[i+1][0] = min(dp[i][0] + d, dp[i][1] + d + 1)
    dp[i+1][1] = min(dp[i][0] + (10-d), dp[i][1] + (10-d) - 1)
print(min(dp[-1][0], dp[-1][1]+1))

Submission status: Accepted

Solution code:
s = input()
keta = len(s)
infi = 10 ** 10
dp = [[infi] * (2) for _ in range(keta + 1)]
dp[0][0] = 0
s = s[::-1]
for i in range(keta):
    for j in range(2):
        num = int(s[i])
        if j == 1:
            num += 1
        ni = i + 1
        if num == 10:
            nj = 1
            num = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num < 5:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num > 5:
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
        else:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
print(min(dp[keta][0], dp[keta][1] + 1))

Submission status: Accepted

Solution code:
s = "0" + input()
keta = len(s)
dp = [0] * (keta + 1)
kuri = 0
for i in range(keta):
    ni = i + 1
    num = int(s[-i - 1])
    if kuri:
        num += 1
        kuri = 0
    if num == 10:
        kuri = 1
        dp[ni] = dp[i]
    elif num < 5:
        dp[ni] = dp[i] + num
    elif num > 5:
        num %= 10
        kuri = 1
        dp[ni] = dp[i] + 10 - num
    else:
        nn = int(s[-ni - 1])
        if nn < 5:
            dp[ni] = dp[i] + num
        else:
            kuri = 1
            dp[ni] = dp[i] + 10 - num
print(dp[keta] + kuri)

Submission status: Accepted

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

dp = [[0 for _ in range(L + 1)] for over in range(2)]
dp[0][0] = 0
dp[1][0] = 1

for j, s in enumerate(S, 1):
    n = int(s)
    dp[0][j] = min(dp[0][j - 1] + n, dp[1][j - 1] + (10 - n))
    dp[1][j] = min(dp[0][j - 1] + (n + 1), dp[1][j - 1] + (10 - n - 1))
    
print(dp[0][-1])

Submission status: Accepted

Solution code:
import collections
s = map(int,list(raw_input()))
qa = collections.deque([0])
qb = collections.deque([1])
for i in range(len(s)):
	qa.append(min(qa[0] + s[i], qb[0] + 10 - s[i]))
	qb.append(min(qa[0] + s[i] + 1, qb[0] + 10 - s[i] - 1))
	qa.popleft()
	qb.popleft()

print qa[-1]

Submission status: Accepted

Solution code:
s = map(int,list(raw_input()))
dp = [[0,0] for _ in range(len(s))]
for i in range(len(dp)):
	a = (dp[i - 1][0] if i - 1 >= 0 else 0) + s[i]
	b = (dp[i - 1][1] if i - 1 >= 0 else 1) + 10 - s[i]
	dp[i][0] = min(a,b)

	a = (dp[i - 1][0] if i - 1 >= 0 else 0) + s[i] + 1
	b = (dp[i - 1][1] if i - 1 >= 0 else 1) + 10 - s[i] - 1
	dp[i][1] = min(a,b)
print dp[-1][0]

Submission status: Accepted

Solution code:
n=list(map(int,input()))
keta=len(n)
satsu=0

for i in range(keta):
    tmp = n.pop()
    if i == keta-1:
        n.append(0)
    
    if tmp == 10:
        tmp=0
        n[-1]=n[-1]+1
    if tmp > 5 or (tmp==5 and n[-1] >= 5):
        satsu += 10 - tmp
        n[-1] = n[-1] + 1
    else:
        satsu += tmp

print(satsu+n[0])

Submission status: Accepted

Solution code:
N = [int(c) for c in input()]
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
print(dp[0])

Submission status: Accepted

Solution code:
'''
提出#12888083
'''

L = list(map(int,list(input())))
L = [0] + L
N = len(L)
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]

for i in range(N):
    dp1[i+1] = min(dp1[i] + L[i], dp2[i] + 10 - L[i])
    dp2[i+1] = min(dp2[i] + 10 - L[i] - 1, dp1[i] + L[i] + 1)

print(dp1[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**7)

def run():
    N = list(map(int, list(input())))
    N = N[::-1] + [0]
    count = 0
    seq = 0
    for idx, n in enumerate(N[:]):
        if seq == 1 and (n >= 5 or (n == 4 and N[idx+1] >= 5)):
            count += 9 - n
        elif seq == 0 and (n >= 6 or (n == 5 and N[idx+1] >= 5)):
            count += 10 - n
            seq = 1
        else:
            count += n + seq
            seq = 0
    print(count)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# ABC155E

s = input()
d0 = [0,1,2,3,4,5,6,7,8,9]
d1 = [0,1,2,3,4,5,5,4,3,2] # 通常時

a0 = d1[int(s[0])]
a1 = d1[int(s[0]) + 1] if int(s[0])<=8 else 1

for c in s[1:]:
    c = int(c)
    b0 = min(a0 + c, a1 + (10 - c))
    b1 = min(a0 + c + 1, a1 + (9 - c)) if c <=8 else a1
    a0, a1 = b0, b1
    
print(a0)

Submission status: Accepted

Solution code:
N=input()
L=len(N)
ans=[[0 for e in range(2)] for f in range(L)]
ans[0][0]=int(N[L-1])
ans[0][1]=10-int(N[L-1])
if L>1:
 for i in range(1,L):
  ans[i][0]=min(ans[i-1][0]+int(N[L-1-i]),ans[i-1][1]+int(N[L-1-i])+1)
  ans[i][1]=min(ans[i-1][0]+10-int(N[L-1-i]),ans[i-1][1]+10-int(N[L-1-i])-1)
print(min(ans[L-1][0],ans[L-1][1]+1))

Submission status: Accepted

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

DP=[[N]*2 for _ in range(L+1)]
DP[0][0]=0
DP[0][1]=1

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

print(DP[L][0])

Submission status: Accepted

Solution code:
L = list(map(int,list(input())))
L = [0] + L
N = len(L)
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]

for i in range(N):
    dp1[i+1] = min(dp1[i] + L[i], dp2[i] + 10 - L[i])
    dp2[i+1] = min(dp2[i] + 10 - L[i] - 1, dp1[i] + L[i] + 1)

print(dp1[-1])

Submission status: Accepted

Solution code:
N = input()
n = len(N)
dp = [[0,0]for i in range(0,n,1)]#[i][0]その桁はピッタリ払う[i][1]一つ上の桁を１枚つかう　ときの合計枚数

dp[n-1][0] = int(N[n-1])
dp[n-1][1] = int(10 - int(N[n-1]) + 1 )#一つ上の桁で払うandおつり

for i in range(n-2,-1,-1):
    dp[i][0] = int(N[i]) + min(dp[i+1][0],dp[i+1][1])
    dp[i][1] = 10 - int(N[i]) + 1 + min(dp[i+1][0],dp[i+1][1] - 2)#次の桁で払った、の＋１を取り消すマイナス１と繰り下がりの

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

Submission status: Accepted

Solution code:
s = input()

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+10-int(s[i]), dp[i][1]+int(s[i])+1)
    dp[i+1][1] = min(dp[i][0]+int(s[i])+1,dp[i][1]+10-int(s[i])-1)

print(dp[-1][0])

Submission status: Accepted

Solution code:
s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = list(input().rstrip())
    n = [0] + n
    n = n[::-1]
    ln = len(n)
    res = 0
    a = 0
    for i in range(ln):
        s = int(n[i])
        s += a
        if 0<=s<=4:
            res += s
            a = 0
        elif 6<=s:
            res += 10-s
            a = 1
        else:
            if int(n[i+1])>=5:
                res += 10-s
                a = 1
            else:
                res += s
                a = 0
            
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp=[[100000000000 for i in range(len(n)+1)]for j in range(2)]
dp[0][0]=0
dp[1][0]=1
for i in range(len(n)):
  d=n[i]
  dp[0][i+1]=min(dp[0][i+1],min(d,11-d)+dp[0][i],10-d+dp[1][i])
  dp[1][i+1]=min(dp[1][i+1],d+1+dp[0][i],9-d+dp[1][i])
  
  
print(dp[0][len(n)])
#print(dp)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

N = sr()
dp = [0, 1]  # ちょうど払う最小枚数、１円多くはらう最小枚数
for x in N:
    x = int(x)
    prev = dp[:]
    dp[0] = min(prev[0]+x, prev[1]+(10-x))
    dp[1] = min(prev[0]+x+1, prev[1]+(10-x-1))

answer = dp[0]
print(answer)
# 33

Submission status: Accepted

Solution code:
s=input()
dp0=[0]*(len(s)+1)
dp1=[0]*(len(s)+1)
dp1[0]=1
for i in range(1,len(s)+1):
  n=int(s[i-1:i])
  dp0[i]=min(dp0[i-1]+n,dp1[i-1]+10-n)
  dp1[i]=min(dp0[i-1]+(1 if n+1==10 else n+1),dp1[i-1]+10-n-1)
print(dp0[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc155/submissions/10157837
# 写経

def main():
    a = [0]
    a += map(int, input())
    a.reverse()

    n = len(a)
    b = a.copy()

    for i in range(n):
        if b[i] > 5 or (b[i] == 5 and b[i + 1] >= 5):
            b[i] = 0
            b[i + 1] += 1

    cnt = sum(b)
    for i in range(n):
        if a[i] > b[i]:
            b[i] += 10
            b[i + 1] -= 1
        cnt += b[i] - a[i]
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    *e, = map(int, input())
    e.reverse()

    inf = 20 * len(e)

    dp = [0, inf]  # 繰り下がり無,有

    for x in e:
        ndp = [-1, -1]  # 繰り下がり無,有

        ndp[0] = min(
            dp[0] + x,
            dp[1] + ((x + 1) if x < 9 else inf)  # ちょうど支払えないのでinf
        )  # ちょうど支払う

        ndp[1] = min(
            dp[0] + ((10 - x) if x > 0 else inf),  # 繰り下がりにならないのでinf
            dp[1] + (10 - (x + 1))
        )  # 0枚支払って繰り下がり

        dp = ndp

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

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

# print(N)
ans = 0
DP = [0] *2
DP[0] = 0
DP[1] = 1
for i in N:
    a, b = DP[0] ,DP[1]
    DP[0] = a + i if a+i < b +(10-i) else b +(10-i)
    DP[1] = a + i+1 if a + i+1 < b + (9-i) else b + (9-i)

    # print(DP)

print(DP[0] if DP[0] <= DP[1]+1 else DP[1] +1)

Submission status: Accepted

Solution code:
n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    # for a in range(10):
    #     for b in range(10):
    #         if a - b == c:
    #             ret[0][0] = min(ret[0][0], a + b)
    #         if 10 + a - b == c:
    #             ret[0][1] = min(ret[0][1], a + b)
    #         if a - 1 - b == c:
    #             ret[1][0] = min(ret[1][0], a + b)
    #         if 10 + a - 1 - b == c:
    #             ret[1][1] = min(ret[1][1], a + b)
    # for b in range(10):
    #     a = c + b
    #     if 0 <= a < 10:
    #         ret[0][0] = min(ret[0][0], a+b)
    #     a = c + b - 10
    #     if 0 <= a < 10:
    #         ret[0][1] = min(ret[0][1], a+b)
    #     a = c + b + 1
    #     if 0 <= a < 10:
    #         ret[1][0] = min(ret[1][0], a + b)
    #     a = c + b - 10 + 1
    #     if 0 <= a < 10:
    #         ret[1][1] = min(ret[1][1], a + b)
    a = c
    ret[0][0] = min(ret[0][0], a)
    b = 10 - c
    if b < 10:
        ret[0][1] = min(ret[0][1], b)
    a = c + 1
    if a < 10:
        ret[1][0] = min(ret[1][0], a)
    b = 9-c
    ret[1][1] = min(ret[1][1], b)

    return ret


dp = [[0 for _ in range(l+1)] for _ in range(2)]

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

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

Submission status: Accepted

Solution code:
n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    # for a in range(10):
    #     for b in range(10):
    #         if a - b == c:
    #             ret[0][0] = min(ret[0][0], a + b)
    #         if 10 + a - b == c:
    #             ret[0][1] = min(ret[0][1], a + b)
    #         if a - 1 - b == c:
    #             ret[1][0] = min(ret[1][0], a + b)
    #         if 10 + a - 1 - b == c:
    #             ret[1][1] = min(ret[1][1], a + b)
    for b in range(10):
        a = c + b
        if 0 <= a < 10:
            ret[0][0] = min(ret[0][0], a+b)
        a = c + b - 10
        if 0 <= a < 10:
            ret[0][1] = min(ret[0][1], a+b)
        a = c + b + 1
        if 0 <= a < 10:
            ret[1][0] = min(ret[1][0], a + b)
        a = c + b - 10 + 1
        if 0 <= a < 10:
            ret[1][1] = min(ret[1][1], a + b)
    return ret


dp = [[0 for _ in range(l+1)] for _ in range(2)]

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

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