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
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def solve(N):
    dp = [0] * (len(N) + 1)

    for i, e in enumerate(N):
        if int(e) + dp[i] >= 6:
            dp[i] = 10 - (int(e) + dp[i])
            dp[i+1] += 1
        elif int(e) + dp[i] == 5 and i < len(N)-1 and int(N[i+1]) >= 5:
            dp[i] = 5
            dp[i+1] += 1
        else:
            dp[i] += int(e)
    return dp

def digit_sum(n):
    tmp = 0
    while n:
        tmp += n % 10
        n //= 10
    return tmp

def greedy(N):
    ans = INF
    bestp = None
    for p in itertools.product(range(10), repeat=len(N)+1):
        n = 0
        for i in range(len(p)):
            n += p[i] * (10 ** i)
        intN = 0
        for i in range(len(N)):
            intN += int(N[i]) * (10 ** i)
        if n >= intN:
            if ans > digit_sum(n) + digit_sum(n - intN):
                ans = digit_sum(n) + digit_sum(n - intN)
                bestp = p
    return ans, bestp

# def main():
#     it = 1000
#     for N in range(1, it+1):
#         tmp = list(str(N))[::-1]
#         dp = solve(tmp)

#         ans1, (ans2, p) = sum(dp), greedy(tmp)
#         if ans1 != ans2:
#             print(N, dp, p, ans1, ans2)


def main():
    N = SL()[::-1]
    dp = [0] * (len(N) + 1)

    for i, e in enumerate(N):
        if int(e) + dp[i] >= 6:
            dp[i] = 10 - (int(e) + dp[i])
            dp[i+1] += 1
        elif int(e) + dp[i] == 5 and i < len(N)-1 and int(N[i+1]) >= 5:
            dp[i] = 5
            dp[i+1] += 1
        else:
            dp[i] += int(e)
    print(sum(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = input() + "0"

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

    print(dp[-1][0])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
S = input()
ans = 0
flag = False #繰り上がりありならTrue
flag2 = False #前が5ならTrue
for k in range(len(S)):
  n = int(S[-k-1])
  if flag2:
    if n < 5:
      flag = False
    else:
      flag = True
  if flag:
    n += 1
  if n == 5:
    ans += 5
    flag2 = True
    flag = False
  elif n < 5:
    ans += n
    flag2 = False
    flag = False
  else:
    ans += 10-n
    flag2 = False
    flag = True
if flag:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    ans = 0
    n = input()
    dp = [0,1] #0,1多く入れる
    for i in n:
        ni = int(i)
        pdp = dp*1
        dp[0] = min(pdp[0]+ni,pdp[1]+(10-ni))
        dp[1] = min(pdp[0]+ni+1,pdp[1]+(10-ni-1))
    print(dp[0])


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = list(map(int, list(input())))
N.reverse()
N=N+[0]
cnt = 0
for i in range(len(N)):
    n=N[i]
    if n<5:
        cnt+=n
    elif n==5:
        cnt+=n
        if N[i+1]>=5:
            N[i+1]+=1
    else:
        cnt+=10-n
        N[i+1]+=1
print(cnt)

Submission status: Accepted

Solution code:
n = str(input())
n_list = list(reversed(n))
n_list.append('0')
sum = 0
kuriagari = False
for i in range(len(n_list)):
    num = int(n_list[i])
    if(kuriagari):
        num+=1
        kuriagari=False
    
    if(num==10):
        num=0
        kuriagari=True

    if(num<5):
        sum+=num
    else:
        if(num>5):
            sum+=10-num
            kuriagari=True
        else:
            sum+=5
            if(int(n_list[i+1])>=5):
                kuriagari=True

print(sum)

Submission status: Accepted

Solution code:
s = "0" + input()
n = len(s)
S = []
for i in range(n-1,-1,-1):
    S.append(int(s[i]))

ans = sum(S)
ans0 = ans
D = [[0] * 3 for i in range(n)]
D[0] = [S[0], S[0]+1, 10-S[0]]
for i in range(1, n):
    D[i][0] = min(D[i-1][0], D[i-1][1]) + S[i]
    D[i][1] = D[i-1][2] + S[i] + 1
    D[i][2] = min(D[i-1][0]+10-S[i], D[i-1][1]+10-S[i], D[i-1][2]+9-S[i])

# print(D)
print(min(D[-1][:2]))

Submission status: Accepted

Solution code:
import math


def count(N, X):
    cnt = sum(map(int, str(X))) + sum(map(int, str(X - N)))
    return cnt


def solve_naive_first(N):
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive(N), 1+solve_naive(p*10-N))


def solve_naive(N):
    if N < 10:
        return min(N, 10-N+1)
    keta = math.floor(math.log(N, 10))
    p = pow(10, keta)
    return min(solve_naive((N // p + 1) * p - N) + (N // p + 1), solve_naive(N % p) + N // p)


def solve(N):
    n_0, n_1 = 0, 1  # 0: その桁で処理, 1: 次の桁に1タス
    for i in N[::-1]:
        i = int(i)
        if i == 9:
            n_0, n_1 = n_0 + i, min(n_0 + 10 - i, n_1 + 10 - i - 1)
        else:
            n_0, n_1 = min(n_0 + i, n_1 + i + 1), min(n_0 +
                                                      10 - i, n_1 + 10 - i - 1)
    return min(n_0, n_1+1)


if __name__ == '__main__':
    N = input()
    ans = solve(N)
    print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=RD()[::-1]
	N=list(map(int,n))+[0]
	#print(N)

	ans=0

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

	print(ans)









if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
abef=0
bbef=1
s=input()
for i in range(len(s)):
  curr=int(s[len(s)-1-i])
  a=abef+curr
  b=bbef+9-curr
  a=min(a,1+bbef+curr)
  b=min(b,abef+10-curr)
  abef=a
  bbef=b
curr=0
a=abef+curr
b=bbef+9-curr
a=min(a,1+bbef+curr)
b=min(b,abef+10-curr)
print(min(a,b))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = [0] + list(map(int,SI()))
    ans = 0
    for i in range(len(N)-1,-1,-1):

        if N[i] < 6 and not(N[i] == 5 and (i > 0 and N[i-1] >= 5)):
            ans += N[i]
        else:
            ans += 10 - N[i]
            N[i-1] += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

N = np.array([int(_) for _ in input()])


def solve(N):
    p, q = 0, 1
    for x in N:
        p, q = min(p + x, q + 10 - x), min(p + x + 1, q + 9 - x)
    print(p)


solve(N)

Submission status: Accepted

Solution code:
p, q = 0, 1
for x in map(int, input()):
    p, q = min(p + x, q + 10 - x), min(p + x + 1, q + 9 - x)
print(p)

Submission status: Accepted

Solution code:
import sys


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


def main():
    N = list(map(int,input()))
    count = 0

    S = len(N)
    flag = 0
    for i in range(S):
        temp = flag + N[-1 - i]
        if temp > 5:
            count += 10 - temp
            flag = 1
        elif temp ==5  and i !=S-1 and N[-1-i-1]>=5:
            count+=temp
            flag=1

        else:
            count += temp
            flag = 0

    print(count + flag)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


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


def main():
    N = input()
    count = 0

    S = len(N)
    flag = 0
    for i in range(S):
        temp = flag + int(N[-1 - i])
        if temp > 5:
            count += 10 - temp
            flag = 1
        elif temp ==5  and i !=S-1 and int(N[-1-i-1])>=5:
            count+=temp
            flag=1

        else:
            count += temp
            flag = 0

    print(count + flag)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
A = list(map(int, input()))
while A[-1] == 0:
  A.pop()
n = len(A)
dp = [[0]*2 for _ in range(n)]
dp[0][1] = 1
for i, a in enumerate(A[:-1]):
  if i < n-1:
    dp[i+1][0] = min(dp[i][0]+a, dp[i][1]+10-a)
    dp[i+1][1] = min(dp[i][0]+a+1, dp[i][1]+9-a)
ans = min(dp[-1][0]+A[-1], dp[-1][1]+10-A[-1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def resolve(in_):
    dp0 = [1 << 60] * 1000100
    dp1 = [1 << 60] * 1000100
    zero = ord(b'0')
    dp0[0] = 0
    dp1[0] = 2

    for i, v in enumerate(in_.read().rstrip()):
        v -= zero

        # ちょうど支払う。おつりなし。
        dp0[i + 1] = min(dp0[i] + v, dp1[i] + v)

        # 前の桁の支払い枚数に 1 を加えてお釣りを払うのと、
        # 前の桁で多く払ってあるのでお釣りの払い出しの継続の二通り
        dp1[i + 1] = min(dp0[i] + 1 + 10 - v, dp1[i] + 9 - v)
    else:
        i += 1


    return min(dp0[i], dp1[i])


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(N):
    N = [0] + N
    k = 0  # 繰り上がり
    ans = 0
    for d, d_next in zip(N[::-1], N[-2::-1]):
        d += k
        if d <= 4 or (d==5 and d_next<5):
            k = 0
            ans += d
        else:
            k = 1
            ans += 10 - d
    if k:
        ans += 1
    return ans

def test(N, ans):
    for i in range(N, 10000):
        rem = i - N
        if sum(map(int, str(i))) + sum(map(int, str(rem))) < ans:
            print(f"!!! N={N}, ans={ans}, trueans={i, rem}")
def main():
    N = list(map(int, input()))
    print(solve(N))
    # for i in range(1, 10000):
    #     ans = solve(list(map(int, str(i))))
    #     test(i, ans)
main()

Submission status: Accepted

Solution code:

def resolve():
    S = "0" + input()
    N = len(S)

    dp = [[1<<60]*2 for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        now = int(S[i])
        dp[i+1][0] = min(dp[i][0]+now, dp[i][1]+(10- now))
        dp[i + 1][1] = min(dp[i][0] + now + 1, dp[i][1] + (10 - now - 1))
    print(dp[N][0])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

for i in range(len(N)):
    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[-1][0])

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
S += '0'

n = len(S)
dp = [[10**20 for j in range(2)] for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(2):
        x = ord(S[i])-ord('0')
        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:
import sys
input = sys.stdin.readline

n = list(input().strip())
ans = 0

carry = False
for i in range(len(n) - 1, -1, -1):
    p = int(n[i])
    if carry:
        p += 1
        carry = False
    if p == 10:
        carry = True
    elif p >= 6:
        carry = True
        ans += 10 - p
    elif p == 5:
        if i != 0 and int(n[i - 1]) >= 5:
            carry = True
            ans += 5
        else:
            carry = False
            ans += 5
    else:
        ans += p
if carry:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main_b():
	s = input()
	pp=0
	na=0
	for i, c in enumerate(s[::-1]):
		cc=na+int(c)
		na=0
		if cc <= 4:
			pp+=cc
		else:
			na = 1
			if i==len(s)-1:
				pp+=1
			pp+=10-cc
			
	print(pp)
	
def main():
	s = input()
	pmin=1000
	mmin=0
	s='0'+s
	for c in s[::-1]:
		v = int(c)
		npmin = min(pmin + 10 - (v+1), mmin + 10 - v)
		nmmin = min(pmin + v + 1, mmin + v)
		pmin = npmin
		mmin = nmmin
	return min(pmin, mmin)
	
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:

N = input()

lim = len(N)
dp = [[0, 0] for _ in range(lim + 1)]
dp[0][1] = 1
for i in range(lim):
    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[-1][0])

Submission status: Accepted

Solution code:
N = list(input())

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

ans += num
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = list(map(int, list(input())))
length = len(N)
# 丁度払うか釣りをもらうか
dp = [[10**18]*2 for _ in range(length+1)]
dp[0][0] = 0
for i in range(1, length+1):
    n = N[-i]
    dp[i][1] = min(dp[i-1][1]+(9-n), dp[i-1][0]+(10-n))
    dp[i][0] = min(dp[i-1][0]+n, dp[i-1][1]+n+1)
    if i==length:
        dp[i][1] = dp[i][1]+1
print(min(dp[-1]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = input()
N = [int(i) for i in N]
# 数え上げ問題なので多分dp
dp = [[0, 0] for i in range(len(N))]

# ぴったし払うための最小値
dp[0][0] = min(N[0], 11 - N[0])
# お釣りをもらう用の紙幣を１枚余分にとっておく場合の最小値
dp[0][1] = min(N[0] + 1, 10 - N[0])

for i in range(1, len(N)):
    # dp[i - 1][1] + 10 - N[i]:とっておいた紙幣を使用し、お釣りを10 - N[i]枚もらう
    dp[i][0] = min(dp[i - 1][0] + N[i], dp[i - 1][1] + 10 - N[i])
    # dp[i - 1][1] + 9 - N[i]:お釣りを10 - N[i]枚もらい、そのうち１枚は次のお釣りを
    # もらう試行のためにとっておく
    dp[i][1] = min(dp[i - 1][0] + N[i] + 1, dp[i - 1][1] + 9 - N[i])
print(dp[len(N) - 1][0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    s = input()
    dp = [0, 1]
    for c in s:
        x = int(c)
        a = dp[0] + x
        if a > dp[1] + 10 - x:
            a = dp[1] + 10 - x
        b = dp[0] + x + 1
        if b > dp[1] + 10 - x - 1:
            b = dp[1] + 10 - x - 1
        dp[0] = a
        dp[1] = b
    dp[1] += 1
    print(min(dp))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = '0' + input()
m = len(s)
up = 0
cnt = 0
y = []
for i in range(-1, -m-1, -1):
    cs = int(s[i]) + up
    if cs < 5 or (cs == 5 and int(s[i-1]) < 5):
        cnt += cs
        y.append([cs, s[i]])
        up = 0
    else:
        cnt += 10 - cs
        y.append([10 - cs, s[i]])
        up = 1
        
print(cnt)

Submission status: Accepted

Solution code:
import sys
import numpy as np



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


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[:],i8[:,:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    from my_module import main
    N = np.array([int(_) for _ in input()])
    dp=np.zeros((len(N),2),dtype=np.int64)
    main(N,dp)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
N = np.array([int(_) for _ in input()])
dp = np.array([[0, 0] for _ in range(len(N))])


@njit
def solve(N, dp):
    dp[0, 0] = min(N[0], 11 - N[0])
    dp[0, 1] = min(N[0] + 1, 10 - N[0])
    for i in range(1, len(N)):
        dp[i, 0] = min(dp[i - 1, 0] + N[i], dp[i - 1, 1] + 10 - N[i])
        dp[i, 1] = min(dp[i - 1, 0] + N[i] + 1, dp[i - 1, 1] + 9 - N[i])
    print(dp[-1][0])


solve(N, dp)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF=10**30
N=list(map(int,list(input())))[::-1]
l=len(N)
dp=[[INF,INF] for i in range(l+1)]
dp[0][0]=0
for i in range(l):
    dp[i+1][0]=min(dp[i][0]+N[i],dp[i][1]+N[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-N[i]),dp[i][1]+(9-N[i]))
print(min(dp[l][0],dp[l][1]+1))

Submission status: Accepted

Solution code:
INF=10**30
N=list(map(int,list(input())))[::-1]
l=len(N)
dp=[[INF,INF] for i in range(l+1)]
dp[0][0]=0
for i in range(l):
    dp[i+1][0]=min([dp[i+1][0],dp[i][0]+N[i],dp[i][1]+N[i]+1])
    dp[i+1][1]=min([dp[i+1][1],dp[i][0]+(10-N[i]),dp[i][1]+(9-N[i])])
ans=min(dp[l][0],dp[l][1]+1)
print(ans)

Submission status: Accepted

Solution code:
INF=10**30
N=list(map(int,list(input())))[::-1]
l=len(N)
dp=[[INF,INF] for i in range(l+1)]
dp[0][0]=0
for i in range(l):
    dp[i+1][0]=min(dp[i+1][0],dp[i][0]+N[i])
    if N[i]!=9:
        dp[i+1][0]=min(dp[i+1][0],dp[i][1]+N[i]+1)
    dp[i+1][1]=min(dp[i+1][1],dp[i][0]+(10-N[i]))
    if N[i]!=0:
        dp[i+1][1]=min(dp[i+1][1],dp[i][1]+(10-N[i]-1))
    else:
        dp[i+1][1]=min(dp[i+1][1],dp[i][1]+9)
ans=min(dp[l][0],dp[l][1]+1)
print(ans)

Submission status: Accepted

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

def solve(N):
    res = 0
    flg = 0
    for n in reversed(N):
        if flg == 2:
            if n >= 5:
                flg = 1
            else:
                flg = 0
        m = flg + n
        if m == 5:
            res += 5
            flg = 2
        elif m < 5:
            res += m
            flg = 0
        else:
            res += (10 - m)
            flg = 1
    return res + flg%2


N = list(map(int, input().strip()))
print(solve(N))

# N = 1
# q = 0
# while True:
#     p = solve(list(map(int, str(N))))
#     if abs(p-q) > 1:
#         print(N, "OK")
#         exit()
#     q = p
#     N += 1

Submission status: Accepted

Solution code:

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

for i in range(len(N)):
    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[-1][0])

Submission status: Accepted

Solution code:
s=input()
n=len(s)
# ある桁まで、ぴったり支払う時の解、+1円支払う時の解
# はじめは0円に対して考えるので、0と1。
dp=0,1
# 上からi+1桁目にたいして 
for i in range(n):
  si=int(s[i])
  # i+i桁目までぴったり払うときの最小値。ひとつ上の桁で+1払っているときは、繰り下がりを考慮。
  a=min(dp[0]+si,dp[1]+10-si)
  # i+1桁目までぴったり＋1を払う時の最小値。
  # つまり、次の桁に繰り下がりの1を残す。この桁における1は次の桁から見れば10。なのでdp[1]からの遷移には10が計算の項にある。
  b=min(dp[0]+si+1,dp[1]+10-(si+1))
  dp=a,b
print(dp[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=input()
l=len(n)
ans=0
d=[(0,0)]*l
d[0]=min(int(n[0]),10-int(n[0])+1),min(int(n[0])+1,10-int(n[0]))
for i in range(1,l):
    ori=min(int(n[i])+d[i-1][0],10-int(n[i])+d[i-1][1])
    ori_1=min(int(n[i])+1+d[i-1][0],10-int(n[i])-1+d[i-1][1])
    d[i]=ori,ori_1
print(d[l-1][0])

Submission status: Accepted

Solution code:
N = input()
dp = [[0]*2 for _ in range(1001000)]
dp[0][1] = 1
for i in range(len(N)):
    d = int(N[i])
    dp[i+1][0] = min(dp[i][0] + d, dp[i][1] + 10-d)
    dp[i+1][1] = min(dp[i][0] + d + 1, dp[i][1] + 10-d-1)  # もらいすぎている状態を維持する
ans = dp[len(N)][0]
print(ans)

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    NS=(input().strip("\n"))[::-1]
    dp=[[0]*2 for i in range(len(NS))]
    # 0:おつり0 1:おつり10-d
    dp[0][0]=int(NS[0])
    dp[0][1]=10-int(NS[0])
    for i in range(1,len(NS)):
        d=int(NS[i])
        dp[i][0]=min(dp[i-1][0]+d,dp[i-1][1]+d+1)
        dp[i][1]=min(dp[i-1][0]+10-d,dp[i-1][1]-1+10-d)
    dp[-1][1]+=1
    print(min(dp[-1]))
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N=[int(c) for c in input()][::-1]

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

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

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

Submission status: Accepted

Solution code:
def main():
    N = "0" + input()
    N = list(map(int, N[::-1]))
    ans = 0
    up = 0
    for i, n in enumerate(N):
        d = n + up
        # くりあがりアリ
        if d > 5 or (i < len(N) - 1 and d == 5 and N[i + 1] >= 5):
            ans += 10 - d  # 0枚の支払い（後に回す）、10-d枚のおつり
            up = 1
        # くりあがりナシ
        else:
            ans += d  # d枚の支払い、0枚のおつり
            up = 0
    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 d>5 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:
n = input()
n = n[::-1] + '0'
inf = 10 ** 9
dp = [[inf for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0] = 0
dp[0][1] = 2
for i in range(len(n)):
        n_i = int(n[i])
        dp[i + 1][0] = min(dp[i][0] + n_i, dp[i][1] + n_i)
        dp[i + 1][1] = min(dp[i][0] + 11 - n_i, dp[i][1] + 9 - n_i)
print(min(dp[-1][0], dp[-1][1]))

Submission status: Accepted

Solution code:
def main():
    S = list( map( int, list( input())))
    N = len(S)
    dp = [[0,0] for _ in range(N+1)]
    dp[0][1] = 2
    for i in range(N):
        s = S[i]
        dp[i+1][0] = min(dp[i][0] + s, dp[i][1]+s)
        dp[i+1][1] = min(dp[i][0] + 11-s, dp[i][1]+9-s)
        # dp[i+1][2] = min(dp[i][1], dp[i][2])+9-s
        # 11-sは、追加で支払うものと、お釣り
        # 9-sは、追加はすでに支払われていて、繰り下がりが起こっている
    print( min(dp[N][0], dp[N][1]))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    S = list( map( int, list( input())))
    N = len(S)
    dp = [[0,0] for _ in range(N+1)]
    dp[0][1] = 2
    for i in range(N):
        s = S[i]
        dp[i+1][0] = min(dp[i][0] + s, dp[i][1]+s)
        dp[i+1][1] = min(dp[i][0] + 11-s, dp[i][1]+9-s)
        # dp[i+1][2] = min(dp[i][1], dp[i][2])+9-s
        # 11-sは、追加で支払うものと、お釣り
        # 9-sは、追加はすでに支払われていて、繰り下がりが起こっている
    print( min(dp[N][0], dp[N][1]))
if __name__ == '__main__':
    main()