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:
#payment=桁DPの復習方法
n=input()
#0の方がちょうど、1の方が余裕持って払う
dp0=[0 for i in range(1000002)]
dp1=[0 for i in range(1000002)]
nums=int(n[-1])

dp0[1]=nums
dp1[1]=11-nums
#dp0、dp1でそれぞれぴったり払う時と余裕を持たせて払うときのiけためまでを一つの数としてみたときの最小の値を表すものとする
for i in range(1,len(n)):
    s=int(n[-(i+1)])
    dp0[i+1]=s+min(dp0[i],dp1[i])
    dp1[i+1]=min(9-s+dp1[i],11-s+dp0[i])
print(min(dp0[len(n)],dp1[len(n)]))

Submission status: Accepted

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

Submission status: Accepted

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

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

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 )
    # i番目で繰り上がっていたら、(10-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:
# https://atcoder.jp/contests/abc155/submissions/10175015

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc155/tasks/abc155_e
# DPで解き直してみる
# アイデアとしては以下
# F(n)をn円使ったときに使う紙幣の最小と定義
# 例えばF(36)→8,(サンプルの通り)、F(4)→4、F(6)→5
# F(23456)を考える
# F(23456)=min(F(2345)+6, F(2346)+4) となる
# ∵6をそのまま払うなら、桁上りは必要ないので2345を払う最小F(2345)を足せば良い。
# お釣り狙いならばとりあえず、10 - 6のお釣りの分をカウント。そして上位桁で多く払う分2346の最小F(2346)を足せば良い。

# ナイーブな実装

'''
def F(n: int):
    if n < 5:
        # 終了条件
        return n
    a, b = divmod(n, 10)
    ret = min(F(a) + b, F(a + 1) + (10 - b))
    # print(n, ret)
    return ret


print(F(int(input())))
'''
# しかしこれには不適切な実装が含まれている
# 1、再帰の深さが最大100000になる。再帰メモ化でもハッシュの衝突が起きたりして遅くなる可能性がある
# 2、int型を前提にした実装なので、10^100000の大きさの数字を扱おうとするとかなり遅くなる。
# よって上記の再帰関数をdpの形で書き直し、且つ文字列で扱える処理に変更する必要がある。


N = input()
# Nの先頭に0がついているとみたてて
dp0 = 0  # 桁上がりしない
dp1 = 1  # 桁上りするときに必要な紙幣の枚数

for n in N:
    n = int(n)
    dp0_new = min(dp0 + n, dp1 + (10 - n))
    n = n + 1
    dp1_new = min(dp0 + n, dp1 + (10 - n))
    dp0, dp1 = dp0_new, dp1_new

print(dp0)

Submission status: Accepted

Solution code:
def solve(n):
    n = list(map(int, n))
    a, b = 0, 9
    for d in n:
        a, b = min(d+a, d+b), min(11-d+a, 9-d+b)
    return min(a, b)

assert solve("36") == 8
assert solve("91") == 3
assert solve("314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170") == 243

n = input()
print(solve(n))

Submission status: Accepted

Solution code:
# E - Payment

S = input()
N = len(S)

# 先頭からi桁目までの金額のやり取りに必要な紙幣の枚数
dp = [0]
dp_plus1 = [1]

for i in range(N):
    x = int(S[i])
    dp.append(min(dp[i] + x, dp_plus1[i] + (10 - x)))
    dp_plus1.append(min(dp[i] +  (x + 1), dp_plus1[i] + (10 -  (x + 1))))

print(dp[-1])

Submission status: Accepted

Solution code:
INF = 10**18

S = '0'+input()
N = len(S)

dp = [[INF,INF] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(2):
        s = int(S[-1-i])
        s += j

        for a in range(10):
            ni = i+1
            nj = 0
            b = a-s
            if b < 0:
                b += 10
                nj = 1
            dp[ni][nj] = min(dp[ni][nj],dp[i][j]+a+b)

print(dp[N][0])

Submission status: Accepted

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

pay=0
back=0
for i in range(l-1,-1,-1):
    #l-1から0まで
    now = list_n[i]
    if now in [0,1,2,3,4] or (now == 5 and list_n[i-1]<5):
        pay+=now
        list_n[i]=0
    elif now in [6,7,8,9] or (now == 5 and list_n[i-1]>=5):
        back+=10-now
        list_n[i]=0
        list_n[i-1] +=1
    elif now==10:
        list_n[i]=0
        list_n[i-1] +=1
print(pay+back)

Submission status: Accepted

Solution code:
import sys

n=sys.stdin.readline().rstrip()[::-1]
to=0

m=0
n+="0"
num=len(n)

for i in range(num):
    k=int(n[i])
    k+=m
    if k==5:
        if int(n[i+1])>=5:
            to+=10-k
            m=1
        else:
            to+=k
            m=0
    if k<5:
        to+=k
        m=0
    elif k>5:
        to+=10-k
        m=1
        
print(to+m)

Submission status: Accepted

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

for i in range(len(n)):
    # d <= 4 -> and += d
    # d == 5 -> next d <= 4 ans += d else ans += d next digit += 1
    # d >= 6 -> ans += 10 - d next digit += 1
    if n[i] <= 4:
        ans += n[i]
    elif n[i] == 5:
        if n[i + 1] <= 4:
            ans += n[i] 
        else:
            ans += n[i]
            n[i + 1] += 1
    else:
        ans += 10 - n[i]
        n[i + 1] += 1
print(ans)

Submission status: Accepted

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

P=0
OT=0

for i in range(len(L)-1):
    if 0 <= L[i] <= 3:
        P += L[i] + OT
        OT = 0

    elif L[i] == 4:
        if OT == 1 and L[i+1]>=5:
            P += 5
        else:
            P += OT+L[i]
            OT = 0

    elif L[i] == 5:
        if OT == 1:
            P += 4

        else:
            if L[i+1] >= 5:
                P += 1 + 4
                OT = 1
            else:
                P += 5

    else:
        if OT == 1:
            P += 9-L[i]
            OT = 1
        else:
            P += 10 - L[i]
            OT = 1

Pone = 0
if OT==0:
    Pone = min(L[-1],11-L[-1])
elif OT==1 and L[-1]<=4:
    Pone = 1+L[-1]
else:
    Pone = 10-L[-1]

print(P+Pone)

Submission status: Accepted

Solution code:
def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = s_in()[::-1]
n = len(N)

dp1 = [0 for _ in range(n)]
dp1[0] = int(N[0])
# dp1[i] は i桁目を同じ値だけ使ったとしたときの最小値
dp2 = [0 for _ in range(n)]
dp2[0] = 10 - int(N[0])
# dp2[i] は i桁目を繰り上げたとしたときの最小値

for i, s in enumerate(N[1:]):
    i += 1

    m = int(s)
    dp1[i] = min(dp1[i-1] + m,      dp2[i-1] + (m+1))
    dp2[i] = min(dp1[i-1] + (10-m), dp2[i-1] + (10-m-1))

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

Submission status: Accepted

Solution code:
N = input()[::-1]
l = len(N)

n0 = int(N[0])
dp = [[0, 0] for i in range(l)]
dp[0] = [n0, 11-n0]

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


print(min(dp[-1]))

Submission status: Accepted

Solution code:
def read():
    N = input().strip()
    return N,


def solve(N, INF=1000000):
    L = len(N)
    N = list(reversed("0" + N))
    dp0 = [0 for i in range(L + 1)]
    dp1 = [0 for i in range(L + 1)]
    dp1[0] = INF
    for i in range(L):
        x = int(N[i])
        dp0[i + 1] = min(dp0[i] + x, dp1[i] + x)
        dp1[i + 1] = min(dp0[i] + 1 + (10 - x), dp1[i] + 1 + (10 - x) - 2)
    return min(dp0[-1], dp1[-1])


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
N = list(input())
M = [ int(i) for i in N[::-1] ]
M.append(0)
c = 0

for i in range(len(M)-1):
    if M[i] >= 6 or ( M[i] >=5 and M[i+1] >= 5):
        M[i+1] += 1
    c += min(M[i],10-M[i])
c += M[len(M)-1]

print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = input().strip()[::-1]
  dp = [[0, 0] for _ in range(len(n))]
  dp[0][0] = int(n[0])
  dp[0][1] = 10 - int(n[0])
  for i, d in enumerate(map(int, n[1:]), 1):
    dp[i][0] = min(dp[i-1][0] + d,      dp[i-1][1] + 1 + d)
    dp[i][1] = min(dp[i-1][0] + 10 - d, dp[i-1][1] + 10 - (d + 1))
  print(min(dp[-1][0], dp[-1][1]+1))  

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
コンテスト後に解説記事を見てAC
Python 3だとTLE
"""

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N_str):
    """
    https://betrue12.hateblo.jp/ の通り実装

    上の桁から順番に見ていく
    dp[i][j] =
      上から i 桁目までの硬貨の支払いとお釣りを処理し終わって、
      N の i 桁目までの金額よりも j 枚分多く支払っているときの、
      これまでの支払い・お釣り硬貨の最小合計枚数
    """
    N_str = '0' + N_str
    dp = [[0] * 2 for _ in range(len(N_str))]

    # 0376円のとき

    # dp[1][0] = 0       0円払う(0)
    # dp[1][1] = 1    1000円払う(1)
    #
    # dp[2][0] = 3    0円の状態から300円払う(3)  vs  1000円の状態から700円お釣りをもらう(8)
    # dp[2][1] = 4    0円の状態から400円払う(4)  vs  1000円の状態から600円お釣りをもらう(7)
    #
    # dp[3][0] = 7    300円の状態から追加で70円払う(3+7) vs 400円の状態から30円もらう(4+3)
    # dp[3][1] = 6    300円の状態から追加で80円払う(3+8) vs 400円の状態から20円もらう(4+2)
    #
    # dp[4][0] = 10   370円の状態から追加で6円払う(7+6) vs 380円の状態から4円もらう(6+4)
    # dp[4][1] = 9    370円の状態から追加で7円払う(7+7) vs 380円の状態から3円もらう(6+3)

    for i, ch in enumerate(N_str):
        if i == 0:
            dp[0][0] = 0
            dp[0][1] = 1
        else:
            dp[i][0] = min(dp[i - 1][0] + int(ch),
                           dp[i - 1][1] + 10 - int(ch))
            dp[i][1] = min(dp[i - 1][0] + int(ch) + 1,
                           dp[i - 1][1] + 9 - int(ch))

    return dp[len(N_str) - 1][0]


def wrong(N_str):
    """最初に間違って書いた貪欲
    1の位から見ていき、0~4なら支払い、5~9なら10払ってお釣りをもらう

    N = 65のとき、
    この関数だと70払って5お釣りをもらうことになるが
    実際は100払って35お釣りをもらうべきなので誤り
    """
    N_str = N_str[::-1]
    ans = 0
    prev = 0
    for ch in N_str:
        n = int(ch)
        n += prev
        if n <= 5:
            ans += n
            prev = 0
        else:
            ans += 10 - n
            prev = 1
    ans += prev    
    return ans

# for n in range(1, 101):
#     print()
#     n_str = str(n)
#     w = wrong(n_str)
#     gt = solve(n_str)
#     if w != gt:
#         print("n, gt, wrong = ", n, gt, w)

N_str = input()
print(solve(N_str))

Submission status: Accepted

Solution code:
n = input()
precise = 0
over = 1
for d in n:
    d = int(d)
    new_over = min(precise + d + 1, over + d + 2, over + 9 - d)
    precise = min(over + d + 1, precise + d)
    over = new_over
over += 1
print(min(precise, over))

Submission status: Accepted

Solution code:
N = [int(c) for c in input()]
dp = 0,1
for i in range(len(N)):
  a = min(dp[0]+N[i], dp[1]+10-N[i])
  b = min(dp[0]+N[i]+1, dp[1]+10-N[i]-1)
  dp = a,b
print(dp[0])

Submission status: Accepted

Solution code:
def main():
    N = [int(x) for x in input()]
    dp0 = 0
    dp1 = 1
    for n in N:
        # そのまま払う
        a = min(dp0 + n, dp1 + 10 - n)
        # 1多めに払う
        b = min(dp0 + n + 1, dp1 + 10 - (n+1))
        dp0, dp1 = a, b
        
    print(dp0)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S=input()
INF=10**12
# dp[i][j]: 下からi桁目まで決めた時の、くりさがりがjの時の最小値
# i: 0~N, j:2値, 前の桁でくりさがりが発生している場合に1
dp=[[INF for _ in range(2)] for _ in range(10**6+5)]
S=S[::-1]
S+="0"
N=len(S)
dp[0][0]=0
# 配るDP, 今の状態を見て次の状態を決めていく
for i in range(N):
    for j in range(2):
        # x: i桁目の数字, 前の桁でくりさがりが発生している場合はインクリメント
        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[N][0])

Submission status: Accepted

Solution code:
n = list(map(int,input()))[::-1]
n.append(0)
for i in range(len(n)):
    if n[i] >= 6 or (n[i] == 5 and n[i+1] >= 5):
        n[i] = 10 - n[i]
        n[i+1] += 1
print(sum(n))

Submission status: Accepted

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

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

print(sum(n))

Submission status: Accepted

Solution code:
"""
f(n) , f(n+1)の値を求める
f(3456)を求める時

f(0) = 0, f(1) = 1 とする

f(3) = min
(
    f(0) + 3
    f(1) + 7
)
f(4) = min
(
    f(0) + 4
    f(1) + 6
)

f(34) = min
(
    f(3) + 4
    f(4) + 6
)
f(35) = min
(
    f(3) + 5
    f(4) + 5
)

f(345) = min
(
    f(34) + 5
    f(35) + 5
)
f(346) = min
(
    f(34) + 4
    f(35) + 6
)
f(3456) = min
(
    f(345) + 6
    f(346) + 4
)
"""
N = input()
n = [int(i) for i in N]

f0 = 0
f1 = 1

dp = f0, f1

# 桁DP
for i in n:
    # 支払い枚数を考える
    fn_0 = min(dp[0] + i, dp[1] + 10 - i)
    fn_1 = min(dp[0] + (i+1), dp[1] + 10 - (i+1))
    dp = fn_0, fn_1

print(dp[0])

Submission status: Accepted

Solution code:
N = input().replace("\n", "")
L = len(N)
dp = [[0 for _ in range(2)] for i in range(L+1)]
dp[0][1] = 1
for i in range(L):
    n = int(N[i])
    dp[i+1][0] = min(dp[i][0]+n, dp[i][1]+(10-n))
    dp[i+1][1] = min(dp[i][0]+n+1, dp[i][1]+(9-n))
print(dp[L][0])

Submission status: Accepted

Solution code:
#E DPでとく
N = [int(x) for x in input()]
dp = 0,1
for item in N:
    a = min(dp[0] + item, dp[1] + 10 - item)
    b = min(dp[0] + item + 1, dp[1] + 10 - (item + 1))
    dp = a, b
    
print(dp[0])

Submission status: Accepted

Solution code:
import sys
input =sys.stdin.readline
def solve():
  s = input().rstrip()
  n = len(s)
  dp = [[float("Inf")]*2 for _ in range(n+1)]
  dp[0][0] = 0
  dp[0][1] = 1

  for i in range(0,n):
    number = int(s[i])

    dp[i+1][0] = min([dp[i][0]+number,dp[i][0]+(10-number)+1,dp[i+1][0]])
    if number != 9:
      dp[i+1][1] = min([dp[i][0]+number+1,dp[i][0]+(10-number),dp[i+1][1]])
     
    dp[i+1][0] = min(dp[i][1] +(10-number),dp[i+1][0])
    dp[i+1][1] = min(dp[i][1] + (10-number-1),dp[i+1][1])
        
  #print(dp)
  print(min(dp[n][0],dp[n][1]+1))
solve()

Submission status: Accepted

Solution code:
s = list(list(map(int,input())))
n = len(s)
dp = [ [0,0] for i in range(n) ]
dp[0][0] = s[0]
dp[0][1] = 11-(s[0]-0)
for i in range(n-1):
  d = s[i+1]
  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 = input()

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

print(dp[0])

Submission status: Accepted

Solution code:
n = input()
a = int(n[-1])
b = 10 - int(n[-1])

for i in range(len(n)-2,-1,-1):
    a,b = min(a+int(n[i]), b + int(n[i]) + 1), min(a + 10-int(n[i]), b + 9 -int(n[i]))

print(min(a,b+1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    just, less = 0, INF
    for d in input()[::-1]:
        d = int(d)
        njust = min(just + d, less + d + 1)
        nless = min(just + (10-d), less + (9-d))
        just, less = njust, nless
    print(min(just, less + 1))
resolve()

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])
    #print(str(dp[i])+":" +str(dp2[i]))
ans = min(dp[-1],dp2[-1])
#print(dp,dp2)
print(ans)

Submission status: Accepted

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


#dp[i][j]は下からi桁みたときの最小で，jは繰り下がりの有無
#自分が出す:a お釣り:b
inf=10**10
dp=[[inf,inf] for _ in range(dig+1)]
dp[0]=[0,0]

for i in range(dig):
    for j in range(2):
        if i==0 and j==1:
            break
        x=int(S[dig-i-1])
        for a in range(10):
            jj=0#次のj,繰り下がるかどうか
            b=(a-j)-x#j=1なら，繰り下がっているためaが1下がっている
            if b<0:
                b+=10
                jj=1
            dp[i+1][jj]=min(dp[i+1][jj] , dp[i][j]+a+b)
            
print(dp[-1][0])

Submission status: Accepted

Solution code:
#E 復習
N = list(input())
N = [int(n) for n in N]
N.insert(0, 0)
len_N = len(N)
ans = 0

for i in reversed(range(len_N)):
    num = int(N[i])
    if num == 10:
        N[i-1] += 1
    #他の人の回答をみて、足りなかったのはここの処理。なぜ必要なのか調べる。
    elif num==5:
        if int(N[i-1])>=5:
            ans += 5
            N[i-1] += 1
        else:
            ans += 5
    ###################################
    elif num >5:
        ans += (10-num)
        N[i-1] += 1
    else:
        ans += num

print(ans)

Submission status: Accepted

Solution code:
N = [int(n) for n in input()]
 
 
dp = [[0] * 2 for _ in range(len(N) + 1)]
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])

Submission status: Accepted

Solution code:
import sys

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

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

def solve(N):
    dp = (0, 1) # n円の場合とn+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:
import sys

n = sys.stdin.readline().rstrip()

def main():
    dp = [0, 1]
    for d in n:
        d = int(d)
        dp[0], dp[1] = min(dp[0]+d, dp[1]+10-d), min(dp[0]+d+1, dp[1]+10-d-1)

    return dp[0]

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n = list(map(int, input()))
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
print(dp[0])

Submission status: Accepted

Solution code:
import sys

n = sys.stdin.readline().rstrip()
l = len(n)

def main():
    dp0 = [None] * (l + 1)
    dp1 = [None] * (l + 1)
    dp0[0] = 0
    dp1[0] = 1

    for i in range(l):
        d = int(n[i])
        dp0[i+1] = min(dp0[i]+d, dp1[i]+10-d)
        dp1[i+1] = min(dp0[i]+d+1, dp1[i]+10-d-1)
    
    return dp0[l]

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
N = input()

a = 0  # not borrowed
b = 0  # borrowed

t = int(N[-1])
a, b = a + t, a + (10 - t)

for i in range(len(N) - 2, -1, -1):
    t = int(N[i])
    a, b = min(a + t, b + (t + 1)), min(a + (10 - t), b + (10 - (t + 1)))
print(min(a, b + 1))

Submission status: Accepted

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

b0 = [0]*len(n)
b1 = [0]*len(n)
b1[0] = 1
for i in range(1, len(n)):
  num = n[i]
  b0[i] = min(b0[i-1]+num, b1[i-1]+num+1)
  b1[i] = min(b0[i-1]+10-num, b1[i-1]+10-(num+1))

print(min(b0[-1], b1[-1]))
#print(b0[-1], b1[-1])

Submission status: Accepted

Solution code:
N = input()

a = 0  # not carried
b = 0  # carried
t = int(N[-1])
a, b = a + t, a + (10 - t)

for i in range(len(N) - 2, -1, -1):
    t = int(N[i])
    a, b = min(a + t, b + (t + 1)), min(a + (10 - t), b + (10 - (t + 1)))
print(min(a, b + 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
dp = [0, 1]

s = input()
s = s[::-1]
s += "0"

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

print(min(dp))

Submission status: Accepted

Solution code:
N = '0' + input()
INF = float('inf')
dp = [[INF] * 2 for _ in range(len(N) + 1)]
dp[0][0] = 0

for i in range(len(N)):
    n = int(N[len(N) - 1 - i])
    for j in range(2):
        for a in range(10):
            ni = i + 1
            nj = 0
            b = a - n - j
            if b < 0:
                b += 10
                nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b)
            a == b

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def y_solver(tmp):
    l=len(tmp)
    rev=[int(i) for i in tmp[::-1]+"0"]
    ans=0
    for i in range(l):
        num=rev[i]
        next_num=rev[i+1]
        if (num>5) or (num==5 and next_num>=5):
            rev[i+1]+=1
        ans+=min(num,10-num)  
    last=rev[l]
    ans+=min(last,10-last)
    return ans
s=input()
ans=y_solver(s)
print(ans)

Submission status: Accepted

Solution code:
###さらに綺麗に！！！
def y_solver(tmp):
    l=len(tmp)
    rev=[int(i) for i in tmp[::-1]+"0"]
    ans=0
    for i in range(l):
        num=rev[i]
        next_num=rev[i+1]
        if (num>5) or (num==5 and next_num>=5):
            rev[i+1]+=1
        ans+=min(num,10-num)  
    last=rev[l]
    ans+=min(last,10-last)
    return ans
  
s=input()
ans=y_solver(s)
print(ans)

Submission status: Accepted

Solution code:
###綺麗になったよ！！！！！
def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if (num<5) or (num==5 and next_num<5):
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
        else:
            kuri_cal+=10-num
            next_bit=1 
    
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=y_solver(n)
print(ans)

Submission status: Accepted

Solution code:
def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    import numpy as np
    dp=np.array(dp)
    return(dp[l+1])

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    seq_flag=False
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if not seq_flag:
            if (num<5) or (num==5 and next_num<5):
                ans+=num
                next_bit=0
                kuri_cal=0
                continue
            seq_s=i
            seq_flag=True
            kuri_cal=10-num
            next_bit+=1
            continue
        #print(kuri_cal)
        if num<5:
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
            seq_flag=False
        elif num>5:
            kuri_cal+=10-num
        else:
            if next_num<5:
                ans+=(kuri_cal+num)
                next_bit=0
                kuri_cal=0
                seq_flag=False
            else:
                kuri_cal+=10-num
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=y_solver(n)
print(ans)

Submission status: Accepted

Solution code:
N = input()

N = '0' + N
result = 0
carry = 0
for i in range(len(N) - 1, 0, -1):
    c = int(N[i]) + carry
    n = int(N[i - 1])
    if c < 5 or (c == 5 and n < 5):
        result += c
        carry = 0
    else:
        result += 10 - c
        carry = 1
result += carry
print(result)

Submission status: Accepted

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

dp = [[0] * 2 for _ in range(len(N) + 1)]
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])

Submission status: Accepted

Solution code:
def main():
    S = map(int, input())

    a, b = 0, 1
    for s in S:
        a, b = a + s if a + s < b + 10 - s else b + 10 - s, a + (s + 1) if a + (s + 1) < b + 10 - (s + 1) else b + 10 - (s + 1)

    print(a)


main()

Submission status: Accepted

Solution code:
S = map(int, input())

a, b = 0, 1
for s in S:
    a, b = a + s if a + s < b + 10 - s else b + 10 - s, a + (s + 1) if a + (s + 1) < b + 10 - (s + 1) else b + 10 - (s + 1)

print(a)

Submission status: Accepted

Solution code:
def main():
    S = map(int, input())

    a, b = 0, 1
    for s in S:
        a, b = min(a + s, b + 10 - s), min(a + (s + 1), b + 10 - (s + 1))

    print(a)


main()

Submission status: Accepted

Solution code:
S = map(int, input())

a, b = 0, 1
for s in S:
    a, b = min(a + s, b + 10 - s), min(a + (s + 1), b + 10 - (s + 1))

print(a)

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
i = 0

lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    if lo == 5:  # 5のときは上の桁の大きさによってお釣りが得になるかそのまま払うのが良くなるか変化する
        ans += lo
        if hi < 5:
            pass
        else:
            hi += 1
    elif lo < 5:
        # loが5以外のとき (お釣りが良いか、そのまま払うのが良いか考えるだけ)
        ans += lo
    else:
        ans += 10 - lo
        hi += 1  # 上の桁が繰り上がる
    lo = hi  # 桁を一つずらす
    i += 1


print(ans)

Submission status: Accepted

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

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

i = 0
lo = int(N[i])
while i < len(N) - 1:
    hi = int(N[i + 1])
    # loが5以外のとき (お釣りが良いか、そのまま払うのが良いか考えるだけ)
    if 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)