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
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/abc155/tasks/abc155_e

# dp?
# もしXiが6より大きかったらX(i-1)という上の桁10借りてくればお釣りで枚数が減る
# そうなると上位桁では1枚増えるけどi桁では減る
# 解けなかったね ピッタリ払うときと一枚余分に払うときというアイデアは合ってたけど、一枚余分はdpの数字に反映させるんじゃなくて、前の桁に反映させよう


N = '0' + read()[:-1]
pre_is_kuriagari = False
dp1 = int(N[0])
dp2 = dp1 + 1
for i in ra(1, len(N)):
    n = int(N[i])
    # ピッタリ払うときの最小
    oturi = dp2 + (10 - n)
    pay = dp1 + n
    dp1_new = min(oturi, pay)

    # 1多く払うときの最小
    oturi = dp2 + (10 - (n + 1))
    pay = dp1 + n + 1
    dp2_new = min(oturi, pay)
    dp1, dp2 = dp1_new, dp2_new
print(dp1)

Submission status: Accepted

Solution code:
N = input().strip()
INFTY = 10**8
dp = [[INFTY for _ in range(2)] for _ in range(len(N)+1)]
a = int(N[-1])
for i in range(10):
    if i<a:
        dp[1][1] = min(dp[1][1],i+10-a)
    else:
        dp[1][0] = min(dp[1][0],i+i-a)
for k in range(2,len(N)+1):
    a = int(N[-k])
    for i in range(10):
        if i>=a:
            dp[k][0] = min(dp[k][0],dp[k-1][0]+i+i-a)
        if i-1>=a:
            dp[k][0] = min(dp[k][0],dp[k-1][1]+i+i-1-a)
        if i<a:
            dp[k][1] = min(dp[k][1],dp[k-1][0]+i+10-a)
        if i==0:
            dp[k][1] = min(dp[k][1],dp[k-1][1]+9-a)
        if 0<=i-1<a:
            dp[k][1] = min(dp[k][1],dp[k-1][1]+i+10-a+i-1)
print(min(dp[len(N)][0],dp[len(N)][1]+1))

Submission status: Accepted

Solution code:
S = ['0'] + list(input()) + ['0']
N = len(S)
flag = False

ans = 0

for i in range(N - 1, 0, -1):
    j = int(S[i])
    if flag:
        j += 1
        S[i] = j

    if j <= 5:
        if j == 5 and int(S[i - 1]) >= 5:
            ans += j
            flag = True
        else:
            ans += j
            flag = False

    else:
        ans += 10 - j
        flag = True

if flag:
    ans += 1


# print (ans)
count = 0
for s in S:
    if s == 5:
        count += 1
    else:
        ans -= max(0, count - 2)
        count = 0

print (ans)

Submission status: Accepted

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

# dp[i][j]: 紙幣の最小枚数
# i: 決定した桁数
# j: 1枚多めに渡すフラグ
dp = [[float("inf")] * 2 for _ in range(L + 1)]

# 初期条件
dp[0][0] = 0
dp[0][1] = 1

# 貰うDP
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] + (10 - (n + 1)))

print(dp[L][0])

Submission status: Accepted

Solution code:
N = input()

over = 1
eq = 0

for n in map(int, N):
    o = min(eq + n + 1, over + (10 - n) - 1)
    e = min(eq + n, over + (10 - n))

    over = o
    eq = e

print(eq)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = list(map(int, list(readline().rstrip().decode())[::-1]))
a = 0
b = 10000
for x in n:
    memo = min(a + x, b + x)
    b = min(a + 11 - x, b + 9 - x)
    a = memo
print(min(a, b))

Submission status: Accepted

Solution code:
nl = list(input())


# 繰り上げと繰り下げ
dp = [[0, 10000] for i in range(len(nl) + 1)]

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



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

Submission status: Accepted

Solution code:
s = input()
state = [0, 1]
for i in s:
    n = int(i)
    state_new = [min(state[0] + n, state[1] + 10 - n), 
                 min(state[0] + n + 1, state[1] + 9 - n)]
    state = state_new
print(state[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = [int(x)-48 for x in read().rstrip()]

ans = 0

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


dp[1][0] = 1
dp[0][0] = 0


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

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


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

Submission status: Accepted

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

Submission status: Accepted

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

dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))

Submission status: Accepted

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

m = 0 # 最小の枚数
m_ = 1 # 繰り上がり時の枚数

for n in N:
  m, m_ = min(m+n, m_ + 10-n), min(m+n + 1, m_ + 10-(n+1))
print(m)

Submission status: Accepted

Solution code:
def main():
    n = input()
    l = len(n)
    ans = 0
    p = 0

    for i in range(l-1, -1, -1):
        v = int(n[i])
        if p == 1:
            v += 1
        if v > 5 or (i != 0 and v == 5 and int(n[i-1]) >= 5):
            ans += (10-v)
            p = 1
        else:
            ans += v
            p = 0
    if p == 1:
        ans += 1

    print(ans)
main()

Submission status: Accepted

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

count = 0

for i, n in enumerate(N):
  if n < 5:
    count += n
  elif n > 5:
    count += 10 - n
    N[i+1] += 1
  elif n == 5:
    if N[i+1] >= 5:
      N[i+1] += 1
    count += 5
    
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = "0" + input() # 文字列として受け取り
N = len(n)
plus = 1
just = 0
for i in range(1,N):
    #前の桁がplusだった場合の最低枚数を計算する
    plus_plus = plus+10-(int(n[i])+1)#この桁も１枚多く払う
    plus_just = plus+10-int(n[i])#この桁はちょうど払う
    #前の桁はちょうど払っていた場合
    just_plus = just+1+int(n[i])#この桁は１枚多く払う
    just_just = just+int(n[i])#この桁もちょうど払う
    
    plus = min(plus_plus,just_plus)
    just = min(just_just,plus_just)

#最後の桁は1枚余分に払う必要がない
print(just)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
nums = list(map(int, input().strip()))
nums = nums[::-1]
nums.append(0)
ans = 0
for i in range(len(nums) - 1):
    if nums[i] > 5:
        ans += 10 - nums[i]
        nums[i+1] += 1
    elif nums[i] == 5:
        if nums[i + 1] >= 5:
            nums[i + 1] += 1
        ans += 5
    else:
        ans += nums[i]
ans += nums[-1]
print(ans)

Submission status: Accepted

Solution code:
s = input()
s = '0' + s[::-1]
dp = [[0, 0] for _ in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(2):
        if j == 0: #ぴったり
            dp[i + 1][j] = min(dp[i]) + int(s[i])
        else: #1枚多めに払う
            dp[i + 1][j] = min(dp[i][1] + 9 - int(s[i]), dp[i][0] + 11 - int(s[i]))

print(min(dp[-1]))

Submission status: Accepted

Solution code:
import sys
n = [int(i) for i in sys.stdin.readline().rstrip()[::-1]]
ans = 0
i = 0
p = [n[i],10 - n[i]]
now = [0,0]
i += 1
ans = min(p[0], p[1] + 1)
for i in range(1,len(n)):
  now[0] = min(p[0] + n[i]%10, p[1] + n[i]%10 + 1)
  now[1] = min(p[0] + 10 - n[i]%10, p[1] + 9 - n[i]%10)
  ans = min(now[0], now[1] + 1)
  p[0],p[1] = now[0],now[1]
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


n = ns()
n = list(map(int,n[::-1])) + [0]

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
S = input().strip()
INFTY=10**8
dp = [[INFTY for _ in range(2)] for _ in range(len(S))]
for k in range(10):
    n = int(S[-1])
    if k>= n:
        dp[0][0] = min(dp[0][0],2*k-n)
    else:
        dp[0][1] = min(dp[0][1],2*k-n+10)
for i in range(1,len(S)):
    n = int(S[-(1+i)])
    for k in range(10):
        if k>n:
            dp[i][0] = min(dp[i][0],2*k-n+dp[i-1][0],k+(k-1)-n+dp[i-1][1])
        elif k==n:
            dp[i][0] = min(dp[i][0],2*k-n+dp[i-1][0])
            if n==0:
                dp[i][1] = min(dp[i][1],k+(k-1)%10-n+dp[i-1][1])
            else:
                dp[i][1] = min(dp[i][1],k+10-n+k-1+dp[i-1][1])
        elif k<n:
            dp[i][1] = min(dp[i][1],k+10-n+k+dp[i-1][0],k+10-n+k-1+dp[i-1][1])
print(min(dp[len(S)-1][0],dp[len(S)-1][1]+1))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = input()
    l = len(n)

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

    dp[0][1] = 1

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

    ans = min(dp[l][0], dp[l][1] + 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = input()
len_n = len(n)
dp = [[0,2] for i in range(len_n+1)]
for k,v in enumerate(n[::-1]):
    v = int(v)
    dp[k+1][0] = min(dp[k][0] + v, dp[k][1] + v)
    dp[k+1][1] = min(dp[k][0] + 10 - v + 1, dp[k][1] + 10 - v - 1)
print(min(dp[len_n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = input()

N = [int(i) for i in list(N)][::-1] + [0]
# print(N)
lenN = len(N)

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


for i in range(1, len(N)+1):
    res0 = float('inf')
    res1 = float('inf')

    for j in range(2):
        for num in range(10):
            if j == 1:
                # 前に繰り下がりしていたらnumを減らす
                num = num - 1
            if num >= N[i-1]:
                b = num - N[i-1]
                res0 = min(res0, dp[i - 1][j] + num + b + j)
            else:
                b = num - N[i-1] + 10
                res1 = min(res1, dp[i - 1][j] + num + b + j)
    dp[i][0] = res0
    dp[i][1] = res1

# print(dp)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import time
N = input()
n = len(N)
# t1 = time.time()
# ぴったり払う:a 余分に払う:b
a = int(N[0])
b = 11-int(N[0])
# t2 = time.time()
for i in range(n-1):
    a1 = min(a+int(N[i+1]), b+int(N[i+1]))
    b1 = min(a+11-int(N[i+1]), b+9-int(N[i+1]))
    a = a1
    b = b1
print(min(a,b))
# t3 = time.time()

# print(t2-t1,t3-t2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    s = list(str(input()))
    s.reverse()
    s = [int(c) for c in s]
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    s = list(str(input()))
    s.reverse()
    for i in range(len(s)):
        s[i] = int(s[i])
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    sN = input()
    nl = [int(i) for i in sN]
    nl.reverse()

    ret = 0
    b = nl[0]
    fin = len(nl) - 1
    for i in range(len(nl)):
        if i != fin:
            a = b
            b = nl[i + 1]
            if a >= 10:  # 繰り上がり処理
                a -= 10
                b += 1

            if a <= 4:
                ret += a  # その桁が4以下ならちょうど払う

            if a == 5:  # 1つ上の桁次第
                if b >= 5:
                    b += 1
                    ret += 5
                else:
                    ret += 5

            if a >= 6:  # 1つ上の桁の金で払う
                b += 1
                ret += (10 - a)

        else:
            if b <= 5:
                ret += b
                return ret
            if b >= 6:
                ret += 1 + (10 - b)
                return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = input()
    nl = [int(i) for i in N]
    nl.reverse()

    ret = 0
    b = nl[0]
    fin = len(nl) - 1
    for i in range(len(nl)):
        if i != fin:
            a = b
            b = nl[i + 1]
            if a >= 10:  # 繰り上がり処理
                a -= 10
                b += 1

            if a <= 4:
                ret += a  # その桁が4以下ならちょうど払う

            if a == 5:  # 1つ上の桁次第
                if b >= 5:
                    b += 1
                    ret += 5
                else:
                    ret += 5

            if a >= 6:  # 1つ上の桁の金で払う
                b += 1
                ret += (10 - a)

        else:
            if b <= 5:
                ret += b
                return ret
            if b >= 6:
                ret += 1 + (10 - b)
                return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret



def main():
    r = solve()
    print(r)


def solve():
    nl = input()
    nl = [int(i) for i in nl]
    nl.reverse()

    ret = 0
    next_keta = nl[0]
    fin = len(nl) -1
    for i in range(len(nl)):
        current_keta = next_keta

        if i != fin:
            next_keta = nl[i+1]

            if current_keta <= 4:
                ret += current_keta
                continue
            elif current_keta == 5:
                ret += 5
                if next_keta >= 5:
                    next_keta += 1
                continue
            elif current_keta >= 6:
                ret += (10-current_keta)
                next_keta += 1
                continue

        else:
            if current_keta <= 5:
                ret += current_keta
                return ret
            else:
                ret += (1 + (10-current_keta))
                return ret

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))

def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l




def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input().rstrip()

total = 0
carry = 0
for i in range(len(n)-1, -1, -1):
    v = int(n[i]) + carry
    if v > 5:
        total += 10 - v
        carry = 1
    elif v == 5:
        if i == 0:
            total += 5
            carry = 0
        else:
            if int(n[i-1]) >= 5:
                total += 5
                carry = 1
            else:
                total += 5
                carry = 0
    else:
        total += v
        carry = 0

print(total + carry)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = [int(c) for c in input()][::-1]
N.append(0)
ans = 0
for i in range(len(N)):
    c = N[i]
    if c <= 4:
        ans += c
    elif 6 <= c:
        ans += 10 - c
        N[i + 1] += 1
    else:
        if N[i + 1] < 5:
            ans += c
        else:
            ans += 10 - c
            N[i + 1] += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input().rstrip()
    s = "0" + s
    dp = [0, float("inf")]
    for c in s:
        x = int(c)
        dp = [min(dp[0] + x, dp[1] + (10-x)), min(dp[0] + x+1, dp[1] + (10-x) - 1)]
    print(dp[0])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = [int(s) for s in input()]
M = len(N)

eq = 0
ov = 1

for n in N:
    a = min(eq + n, ov + 10 - n)
    b = min(eq + (n + 1), ov + 10 - (n + 1))
    eq, ov = a, b

print(eq)

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
s += '0'
ans = 0
dp = [0, 10**9]
for c in s:
    i = int(c)
    a = dp[0]+i
    if i<9 and a>dp[1]+i+1:
        a = dp[1]+i+1
    b = dp[1]+9-i
    if i>0 and b>dp[0]+10-i:
        b = dp[0]+10-i
    dp = [a, b]
print(dp[0])

Submission status: Accepted

Solution code:
m = input()[::-1]
n = []
for i in range(len(m)):
    n.append(int(m[i]))

dp = [[0, 0] for _ in range(len(n)+1)]

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

s = len(n)
print(min(dp[s][0], (dp[s][1]+1)))

Submission status: Accepted

Solution code:



n = list(map(int, list(input())))[::-1] + [0]
sum1 = sum(n)
for i in range(len(n)-1):
    if n[i] > 5 or (n[i]==5 and n[i+1]>4):
        n[i] = 10-n[i]
        n[i+1] += 1
print(min(sum1, sum(n)))

Submission status: Accepted

Solution code:
def main():
    n=list(map(int,list(input())[::-1]))+[0]
    nl=len(n)
    ans=0
    for i in range(nl-1):
        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))
      
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = input()
dp = [0,1]
ans = 0
for i in range(len(n)):
    cur1 = dp[0]
    cur2 = dp[1]
    if i != len(n)-1:
        dp[0] = min(cur1+int(n[i]), cur2+10-int(n[i]))
        dp[1] = min(cur1+int(n[i])+1, cur2+9-int(n[i]))
    else:
        ans = min(dp[0]+int(n[i]), dp[1]+10-int(n[i]))
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N = input().strip()
    carry = 0
    a = 0 # 99 -> 099
    b = 1 # 99 -> 100
    for ch in N:
        n = ord(ch) - ord('0')
        a2 = min(a+n, b+10-n)
        b = min(a+n+1, b+10-n-1)
        a=a2
    print(a)

resolve()

Submission status: Accepted

Solution code:
from sys import stdin

N = stdin.readline().rstrip()
ans = 0

N = N[::-1]
N = N + '0'
kuriagari = 0

for i in range(len(N)):
    r = int(N[i])
    if kuriagari == 1:
        r += 1
    if 10 - r < r:
        kuriagari = 1
    else:
        kuriagari = 0
    if r == 5 and int(N[i + 1]) > 4:
        kuriagari = 1
    if r == 10:
        r = 0
    ans += min(r, 10 - r)

print(ans)

Submission status: Accepted

Solution code:
S=input()[::-1]
ans=0
#支払う枚数
array = list(map(int, S))
L=len(array)
for i,n in enumerate(array):
    if n< 5 :
        ans+=n
    elif n > 5:
        ans+= 10-n
        if i <L-1:
            array[i+1] +=1
        else:
            ans +=1
    else:
        ans+=5
        if i < L-1:
            if array[i+1] >=5:
                array[i+1] +=1
                
print( ans)