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: Time Limit Exceeded

Solution code:

def cost(d):
    if d <= 5:
    #if True:
        return d
    else:
        return 11 - d

def gyaku(d):
    return 10-d

input = raw_input
out = 0
s = input()
s_int = int(s)

len_s = len(s)
shisuu = 0

def get_d(s_int, shisuu):
    if s_int // (10 ** shisuu) == 0:
        return None
    d = s_int % (10 ** (shisuu+1)) // (10**shisuu)
    return d


#del s
while True:
    d = get_d(s_int, shisuu)
    if d is None:
        break
    #try:
    #    c = s[-(shisuu+1)]
    #except:
    #    break

    #d = int(c)
    tmp = cost(d)
    #if d >= 6:
    if d >= 5:
        d_gyaku = gyaku(d)
        s_int2 = s_int + d_gyaku * (10 ** shisuu)
        #s2 = str(s_int2)

        #c = s2[-(shisuu+1)]
        #d = int(c)
        d = get_d(s_int2, shisuu)

        tmp2 = cost(d)
        tmp2 += d_gyaku

        if tmp > tmp2:
            #s = s2
            s_int = s_int2
            tmp = tmp2
        elif tmp == tmp2:
            d_next = get_d(s_int, shisuu+1)
            if d_next is not None:
                if d_next >= 5:
                    s_int = s_int2
                    tmp = tmp2
            #try:
            #    d_next = int(s[-(shisuu+1+1)])
            #    if d_next >= 5:
            #        #s = s2
            #        s_int = s_int2
            #        tmp = tmp2
            #except:
            #    pass

    out += tmp
    shisuu += 1


print(out)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
sys.setrecursionlimit(100000)

def calc(n):
    digit = len(str(n))
    if digit==1:
        if n<=5:
            ans = n
        else:
            ans = (10-n)+1
    else:
        top = int(str(n)[0])
        if n-top*10**(digit-1)==0:
            ans = calc(top)
        else:
            cand1 = top + calc(n-top*10**(digit-1))
            cand2 = (top+1) + calc2((top+1)*10**(digit-1)-n)
            cand3 = 1 + calc2(10**(digit)-n)
            ans = min(cand1, cand2, cand3)
    #print("calc",n,ans)
    return ans

def calc2(n):
    digit = len(str(n))
    if digit == 1:
        if n<=5:
            ans = n
        else:
            ans = (10-n)+1
    else:
        top = int(str(n)[0])
        cand1 = top + calc2(n-top*10**(digit-1))
        cand2 = (top+1) + calc((top+1)*10**(digit-1)-n)
        ans = min(cand1, cand2)
    #print("calc2",n,ans)
    return ans

N = int(input())
ans = calc(N)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = 0
while n > 0:
    t = n % 10
    if t < 5:
        a += t
        n -= t
        n //= 10
    elif t != 5:
        n += 10 - t
        a += 10 - t
    else: # t == 5
        s = list(map(int, str(n)))
        i = 0
        while len(s) > 0 and s[-1] == 5:
            s.pop(-1)
            i += 1
        if len(s) == 0:
            a += t * i
            n -= t * i
            n //= 10 ** i
        elif s[-1] <= 4:
            a += t * i
            n -= t * i
            n //= 10 ** i
        else: # s[-1] >= 6
            n += 10 ** i - int('5' * i)
            a += sum(list(map(int, str(10 ** i - int('5' * i)))))
print(a)

Submission status: Time Limit Exceeded

Solution code:
#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque

#a, b = [int(v) for v in input().split()]

n = int(input())
n0 = n


count = 0
while n > 0:
    #print(n, count)
    v = n % 10
    n //= 10
    if v < 5:
        count += v
    elif v == 5:
        if (n % 10) >= 5:
            n += 1
        count += 5
    else:
        count += 10 - v
        n += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = int(input().strip() ) ;


dic = {} ;
dic[S] = 0 ; 
t = S ;
while len(dic) > 0 :
	dic2 ={} ;
	for S in dic :
		if S <= 10 :
			v = min ( dic[S] + S  , dic[S] + 1 + ( 10 - S ) ) ;
			t = min ( t , v ) ;
			continue ;
		s2 = S % 10  ;
		s1 = S // 10 ; 

		if s1 in dic2 :
			dic2[s1] = min ( dic2[s1] , dic[S] + s2 ) ;
		else :
			dic2[s1] = dic[S] + s2 ; 

		s1 += 1 ;
		if s1 in dic2 :
			dic2[s1] = min ( dic2[s1] , dic[S] + (10-s2) ) ;
		else :
			dic2[s1] = dic[S] + (10-s2) ; 
	dic = dic2 ;
print ( t ) ;

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = len(str(n))
count = 0
while True:
    bottom = 10 ** (t-1)
    top = 10 ** t
    
    n = min(top-n,n-bottom)
    t = len(str(n))
    count += 1
    if n == 0:
        print(count)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
n = int(math.log10(N))
ans = 0
for i in range(n + 2):
    a = N % (10**(i+1)) // (10**(i))
    b = N % (10**(i+2)) // (10**(i+1))
    if a < 5 or (a == 5 and b < 5):
        ans += a
        N -= a * (10**(i))
    else:
        ans += 10 - a
        N += (10 - a) * (10**(i))
    if N == 0:
        break
        
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  s=int(input())
  #while s%10==0:
  #    s//=10
  #s=9**800000
  s=str(s)
  lens=len(s)

  d=int(s[0])
  p=11-int(s[0])

  for c in s[1:]:
      j=int(c)
      a=min(d+j,p+j)
      b=min(d+11-j,p+9-j)
      d,p=a,b

  print(min(d,p))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  s=int(input())
  #while s%10==0:
  #    s//=10
  s=9**800000
  s=str(s)
  lens=len(s)

  d=int(s[0])
  p=11-int(s[0])

  for c in s[1:]:
      j=int(c)
      a=min(d+j,p+j)
      b=min(d+11-j,p+9-j)
      d,p=a,b

  print(min(d,p))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

def log(x):
    t=1
    s=1
    while t*10 <= x:
        s = s+1
    return s

def point(a,b):
    for i in range(b-1):
        a = a-a%(10**(i+1))
    return (a%(10**b))//(10**(b-1))

ans = 0
for i in range(1,log(N)+1):
    if point(N,i)<=5:
        ans = ans+point(N,i)
    else:
        ans = ans + 11- point(N,i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def cost(d):
    if d <= 5:
    #if True:
        return d
    else:
        return 11 - d

def gyaku(d):
    return 10-d

input = raw_input
out = 0
s = input()
s_int = int(s)

len_s = len(s)
shisuu = 0

while True:
    try:
        c = s[-(shisuu+1)]
    except:
        break

    d = int(c)
    tmp = cost(d)
    #if d >= 6:
    if d >= 5:
        d_gyaku = gyaku(d)
        s_int2 = s_int + d_gyaku * (10 ** shisuu)
        s2 = str(s_int2)
        c = s2[-(shisuu+1)]
        d = int(c)
        tmp2 = cost(d)
        tmp2 += d_gyaku

        if tmp > tmp2:
            s = s2
            s_int = s_int2
            tmp = tmp2
        elif tmp == tmp2:
            try:
                d_next = int(s[-(shisuu+1+1)])
                if d_next >= 5:
                    s = s2
                    s_int = s_int2
                    tmp = tmp2
            except:
                pass


    #if d >= 6:
    #if d >= 5:
    #    d_gyaku = gyaku(d)

    #    s_int2 = s_int + d_gyaku * (10 ** shisuu)
    #    tmp2 = d_gyaku
    #    s2 = str(s_int2)
    #    c2 = s2[-(shisuu+1)]
    #    d2 = int(c2)
    #    tmp2 += cost(d)

    #    if tmp > tmp2:
    #    #if True:
    #        tmp = tmp2
    #        s_int = s_int2
    #        s = s2



    out += tmp
    shisuu += 1


print(out)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = 0
while n > 0:
    t = n % 10
    if t < 5:
        a += t
        n -= t
        n //= 10
    elif t != 5:
        n += 10 - t
        a += 10 - t
    else: # t == 5
        s = list(map(int, str(n)))
        while len(s) > 0 and s[-1] == 5:
            s.pop(-1)
        if len(s) == 0:
            a += t
            n -= t
            n //= 10
        elif s[-1] <= 4:
            a += t
            n -= t
            n //= 10
        else: # s[-1] >= 6
            n += 10 - t
            a += 10 - t
print(a)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(len(N)-1, -1, -1):

    if i < len(N)-1 and N[i+1] == 5 and N[i] >= 5:
        N[i] += 1
    x = N[i]
    if x > 5:
        ans += (10 - x)
        if i > 0:
            N[i-1] += 1
        else:
            ans += 1
    else:
        ans += x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N):
    ans = 0
    M = str(N)
    A = [0] * (len(M)+2)
    M = [c for c in M[::-1]]
    M.append('0')
    carry = 0
    for i, c in enumerate(M):
        c = int(c) + carry
        carry = 0
        if c == 5 and int(M[i+1]) >= 5:
                carry += 1
                a = 0
        elif c >= 6:
            carry += 1
            a = 0
        else:
            a = c
        A[i] = a
    A[len(M)] = carry

    # print(A)
    A = ''.join(map(str, [c for c in A[::-1]]))
    A = int(A)
    B = A - int(N)
    for c in str(B):
        ans += int(c)
    for c in str(A):
        ans += int(c)

    # print('   ', B)
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(len(N)-1, -1, -1):

    if i < len(N)-1 and N[i+1] == 5 and N[i] >= 5:
        N[i] += 1
    x = N[i]
    if x > 5:
        ans += (10 - x)
        if i > 0:
            N[i-1] += 1
        else:
            ans += 1
    else:
        ans += x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
g = [0,1,2,3,4,5,6,7,8,9,1]
import sys
sys.setrecursionlimit(1000000000)
@lru_cache(maxsize=None)
def solve(i,j):
    if i<0:
        if j==0:
            return 0
        else:
            return 1
    res = 10**18
    for d in range(10):
        n = int(N[i])+j
        sm = g[d]
        if d<n:
            sm += solve(i-1,1)+g[10+d-n]
        else:
            sm += solve(i-1,0)+g[d-n]
        res = min(res,sm)
    return res

N = input()
print(solve(len(N)-1,0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [0,1,2,3,4,5,4,3,2,1]
ans = 0

for _ in range(len(str(n))+1):
    num = n%10
    ans += lst[num]
    if num > 5:
        n = n//10 +1
    elif num < 5:
        n = n//10
    else:
        if (n//10)%10 > 4:
            n = n//10 +1
        else:
            n = n//10

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

S=input()
dig=len(S)
N=int(S)


ans=0

b=0#繰り上がり
for i in range(dig):
    a=N%10+b
    if a<=4:
        ans+=a
        b=0
    elif a>=6:
        ans+=(10-a)
        b=1
    else:#a==5
        if (N%100 - N%10)//10 >=5:
            b=1
        else:
            b=0
        ans+=5
 
    N=N//10

        

if b==1:
    ans+=1

    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
Z = [0,1,2,3,4,5,6,7,8,9,10]
C = [0,1,2,3,4,5,6,7,8,9]
X = [0,1,2,3,4,5,6,7,8,9]

def solve_dp(s):
    n = len(s)
    s = [int(c) for c in s]
    inf = 10**9

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

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

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

    return dp[n-1][0]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N):
    ans = 0
    A = 0
    M = str(N)
    M = [c for c in M[::-1]]
    M.append('0')
    carry = 0
    for i, c in enumerate(M):
        c = int(c) + carry
        carry = 0
        if c == 5 and int(M[i+1]) >= 5:
                carry += 1
                a = 0
        elif c >= 6:
            carry += 1
            a = 0
        else:
            a = c
        A += 10**i * a
    A += 10**(len(M)) * carry

    # print(A)

    B = A - int(N)
    for c in str(B):
        ans += int(c)
    for c in str(A):
        ans += int(c)

    # print('   ', B)
    return ans


def main():
    N = read_int()
    print(slv(N))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = LI()
    N.sort()
    if N[0]==N[1] and N[0]!=N[2]:
        print("Yes")
    elif N[1]==N[2] and N[0]!=N[2]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    A = LI()
    for a in A:
        if a%2==0:
            if a%3!=0 and a%5!=0:
                print("DENIED")
                return
    print("APPROVED")
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    t = max(d.values())
    ans = []
    for s in S:
        if d[s]==t:
            ans.append(s)
            d[s] = 0
    ans.sort()
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    A = LI()

    ans = 0
    print(ans)
    return

def examE():
    S = SI()
    N = len(S)
    flag = False
    ans = 0
    index4 = "4"*N
    for i in range(N):
        #print(ans)
        if flag:
            if int(S[i])>=5:
                ans += 9-int(S[i])
            else:
                if (i<N-1 and int(S[i:])>=int(index4[i:])):
                    ans += 9-int(S[i])
                else:
                    ans += int(S[i])
                    flag = False
            continue

        if (i<N-1 and int(S[i]+S[i+1])>=56) or int(S[i])>=6:
            flag = True
            ans += 11-int(S[i])
        else:
            ans += int(S[i])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""
4396817
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

s = input()

def pay(num,count):
    digits = len(num)
    if digits >= 2:
        s0 = int(num[0])
        s1 = int(num[1])
        border = int('5'*digits)
        if int(num) > border:
            count += 1
            num_next = str(10**(digits) - int(num))
            return pay(num_next,count)
        if s1 > 5:
            if s0 != 9:
                count += s0 + 1
                num_next = str(10**(digits-1) - int(num[1:]))
                return pay(num_next,count)
            else:
                count += 1
                num_next = str(10**(digits-1) - int(num[1:]))
                return pay(num_next,count)
        else:
            count += s0
            return pay(num[1:],count)
    else:
        s0 = int(num)
        if s0 > 5:
            return count + 1 + 10-s0
        else:
            return count + s0

print(pay(s,0))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
n = int(math.log10(N))
ans = 0
for i in range(N + 2):
    a = N % (10**(i+1)) // (10**(i))
    b = N % (10**(i+2)) // (10**(i+1))
    if a < 5 or (a == 5 and b < 5):
        ans += a
        N -= a * (10**(i))
    else:
        ans += 10 - a
        N += (10 - a) * (10**(i))
    if N == 0:
        break
        

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = input()

a = n[::-1] + "0"

ans = 0

prev = 0

INF = 10 ** 100

dp = [[-1, -1] for i in range(len(a)+3)]

dp[0][0] = int(a[0])
dp[0][1] = 10 - int(a[0])

# dp[下の桁から][繰り上げるかどうか]
for i in range(1, len(a)):
    x = int(a[i])
    y = x + 1
    dp[i][0] = min([x + dp[i - 1][0], y + dp[i - 1][1]])
    dp[i][1] = min([(10 - x) + dp[i - 1][0], (10 - y) + dp[i - 1][1]])

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
while n!=0:
    tmp=n%100
    x=tmp%10
    y=(tmp-x)//10

    if x<5 or (x==5 and y<5):
        ans+=x
    else:
        ans+=10-x
        n+=10-x

    n=n//10
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    res = 0
    while N:
        r = N%10
        N //= 10
        r_ = N%10
        if r < 5 or (r==5 and r_ < 5):
            res += r
        else:
            res += 10-r
            N += 1
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
def f(i):
    a[i]=(a[i]+1)%10
    if a[i]==0: f(i+1)

n=int(input())
a=[]
tmp=10
while n!=0:
    a.append(n%tmp)
    n=n//tmp
a.append(0)

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

    else:
        ans+=10-a[i]
        f(i+1)

if a[-1]!=0: ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n_s = input()
n_s = n_s[::-1]
#n = int(n_s)

pay = 0
back = 0
flag = 0

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

dp[0][0] = int(n_s[0])
dp[0][1] = 10 - int(n_s[0])

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

print(min(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
s = input()



def pay(num,count):
    digits = len(num)
    if digits >= 2:
        s0 = int(num[0])
        s1 = int(num[1])
        border = int('5'*digits)
        if int(num) > border:
            count += 1
            num_next = str(10**(digits) - int(num))
            return pay(num_next,count)
        if s1 > 5:
            if s0 != 9:
                count += s0 + 1
                num_next = str(10**(digits-1) - int(num[1:]))
                return pay(num_next,count)
            else:
                count += 1
                num_next = str(10**(digits-1) - int(num[1:]))
                return pay(num_next,count)
        else:
            count += s0
            return pay(num[1:],count)
    else:
        s0 = int(num)
        if s0 > 5:
            return count + 1 + 10-s0
        else:
            return count + s0

print(pay(s,0))

Submission status: Time Limit Exceeded

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

INF = float('inf')
dp = [[INF]*2 for _ in range(L)]
dp[0][0] = int(S[-1])
dp[0][1] = 10-int(S[-1])
S = S[::-1]
for i,c in enumerate(S[1:]):
    c = int(c)
    d = 10-c
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+c)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0]+d)
    c += 1
    d -= 1
    if c==10:
        dp[i+1][1] = min(dp[i+1][1], dp[i][1])
    else:
        dp[i+1][0] = min(dp[i+1][0], dp[i][1]+c)
        dp[i+1][1] = min(dp[i+1][1], dp[i][1]+d)
print(min(dp[-1][0], dp[-1][1]+1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
n = str(n)
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
ans = 0
for i in range(len(n_list) - 1):
    num = n_list[i]
    if (num <= 5 and n_list[i + 1] < 5) or num < 5:
        # pay += num * 10 ** k
        ans += num
    else:
        n_list[i + 1] += 1
        ans += 10 - n_list[i]
    k += 1

# pay += n_list[-1] * 10 ** k
ans += n_list[-1]
print(ans)
# oturi = pay - int(n)
# ans = 0
#
# for i in str(pay):
#     ans += int(i)
# for i in str(oturi):
#     ans += int(i)
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=int(input())
while s%10==0:
    s//=10
s=str(s)
lens=len(s)

dp=[[0,0] for i in range(lens)]

dp[0][0]=int(s[0])
dp[0][1]=11-int(s[0])

for i in range(1,lens):
    dp[i][0]=min(dp[i-1][0]+int(s[i]),dp[i-1][1]+int(s[i]))
    dp[i][1]=min(dp[i-1][0]+11-int(s[i]),dp[i-1][1]+9-int(s[i]))

print(min(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
n = str(n)
k = 0
pay = 0
n_list = []
for i in n[::-1]:
    n_list.append(int(i))
n_list.append(0)
for i in range(len(n_list) - 1):
    num = n_list[i]
    if (num <= 5 and n_list[i + 1] < 5) or num < 5:
        pay += num * 10 ** k
    else:
        n_list[i + 1] += 1
    k += 1
pay += n_list[-1] * 10 ** k
oturi = pay - int(n)
ans = 0

for i in str(pay):
    ans += int(i)
for i in str(oturi):
    ans += int(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

x=0
flag=0
while N>=1:
  m=N%10
  if m==5:
    x+=5
    flag=1
  elif m<5:
    x+=m
    flag=0
  else:
    x+=(10-m)
    flag=2
  N=N//10
  if flag==2:
    N+=1
  elif flag==1:
    if N%10>=5:
      N+=1
print(x)

Submission status: Time Limit Exceeded

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

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    S="00"+input()
    S=S[::-1]
    N=len(S)-1
    
    def calc(x,nxt):
        # 今見てる数字,次の桁の数字,を受けて
        # 今使う,繰り上がり，を返す

        if x<=4:
            return x,0
        elif x>=6:
            return 10-x,1
        else:
            # 次が5なら，そのあと5以上ががくればお得，そうでなくとも損しない
            if nxt<5:
                return 5,0
            else:
                return 5,1
    
    kuri=0
    ans=0
    for i in range(N):
        now=int(S[i])
        nxt=int(S[i+1])
        now+=kuri
        temp,kuri = calc(now,nxt)
        
        ans+=temp
        
    print(ans)
        

main()

Submission status: Accepted

Solution code:
N=input()
inf=float("inf")
dp=[[inf]*(len(N)+1) for i in range(2)]
dp[0][0]=0
for i in range(len(N)):
   tmp=int(N[-1-i])
   dp[0][i+1]=min(dp[0][i],dp[1][i])+tmp
   dp[1][i+1]=min(dp[0][i]+11,dp[1][i]+9)-tmp
print(min(dp[0][-1],dp[1][-1]))

Submission status: Accepted

Solution code:
N = input()[::-1]
l = len(N)
dp = [[0,0] for i in range(l+1)]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
dp = [0, 2]
for d in map(int, reversed(input())):
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

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

Submission status: Accepted

Solution code:
import sys
import functools
# sys.setrecursionlimit(100000000)
n = input()
# import random
# n = ''.join(str(random.randint(1,9)) for _ in range(10**6))

#
# @functools.lru_cache(None)
# def doit(index: int, carry: int) -> int:
#     if index >= len(n):
#         return 0 if carry == 0 else 2
#     d = int(n[index])
#     if carry > 0:
#         return min(10 - d + doit(index + 1, 0), 9 - d + doit(index + 1, 1))
#     else:
#         return min(d + doit(index + 1, 0), d + 1 + doit(index + 1, 1))
#
#
# print(min(doit(0, 0), 1 + doit(0, 1)))


dp = [0, 2]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

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

Submission status: Accepted

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

dp = [0, 10000]
for d in reversed(n):
    d = int(d)
    dp = [min(d + dp[0], d + 1 + dp[1]), min(10 - d + dp[0], 9 - d + dp[1])]

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

Submission status: Accepted

Solution code:
n = input()
dp = [0, 10000]
for d in reversed('0' + n):
    newdp = []
    newdp.append(min(int(d) + dp[0], int(d) + 1 + dp[1]))
    newdp.append(min(10 - int(d) + dp[0], 10 - int(d) - 1 + dp[1]))
    dp = newdp
print(dp[0])

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N = S()
    N =  N[::-1]
    N += '0'
    cnt = 0
    next = 0
    for i in range(len(N)):
        num = int(N[i])
        num += next
        if num <= 4:
            cnt += num
            next = 0
        elif num >= 6:
            cnt += 10 - num
            next = 1
        else:
            if int(N[i + 1]) <= 4:
                cnt += num
                next = 0
            else:
                cnt += 10 - num
                next = 1

    print(cnt)
if __name__ == "__main__":
    main()

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