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:
import sys
sys.setrecursionlimit(10**9)

S = input()
N = int(S)
dp = dict()


def c0():
    c0 = 0
    for i in S:
        c0 += int(i)
    return c0


def f2(value):
    s = list(str(value))
    rs = list(reversed(s))
    cnt = 0
    for i in rs:
        if i != '0':
            break
        else:
            cnt += 1

    if cnt != 0:
        return int(''.join(s[:-cnt]))
    else:
        return value


def f(value):
    for key in dp.keys():
        if f2(key) == f2(value):
            _v = dp.get(key, None)
            return _v
    if value < 10:
        _v = min(value, 10 - value + 1)
        dp[value] = _v
        return _v
    if value % 10 == 0:
        p = 1
        while value >= 10**p:
            p += 1
        syo = value // 10**(p - 1)
        # print('p', p, value, syo)
        if value == syo * 10**(p - 1):
            dp[value] = syo
            return syo
    l = []
    p = 1
    while value >= 10**p:
        tmp = (value // (10**p) + 1) * (10**p)
        l.append(tmp)
        p += 1
    l.append(10**p)
    # print('len(l)', len(l))
    candidates = [c0()]
    for i in l:
        child = i - value
        # print('value = i - child', value, i, child)
        if child >= value:
            continue
        candidates.append(f(i) + f(child))
    _v = min(candidates)
    dp[value] = _v
    return _v


print(f(N))

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_list = list((map(int,list(N))))
N_list.insert(0,0)
for i in range(len(N_list)-1,0,-1):
    if 6<=N_list[i] and N_list[i-1]<9:
        N_list[i] = 0
        N_list[i-1] += 1
    elif 5<=N_list[i] and N_list[i-1] == 9:
        N_list[i] = 0
        d = i-1
        while N_list[d]==9:
            N_list[d] = 0
            d -= 1
        N_list[d] += 1
    elif 1<i:
        if N_list[i] == 5 and 5<=N_list[i-1]:
            N_list[i] = 0
            N_list[i-1] = 0
            d = i-2
            while N_list[d]==9:
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        
print(sum(N_list)+sum(map(int,list(str(int("".join(map(str,N_list)))-int(N))))))

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_list = list((map(int,list(N))))
N_list.insert(0,0)
for i in range(len(N_list)-1,0,-1):
    if 6<=N_list[i] and N_list[i-1]<9:
        N_list[i] = 0
        N_list[i-1] += 1
    elif 5<=N_list[i] and N_list[i-1] == 9:
        N_list[i] = 0
        d = i-1
        while(N_list[d]==9):
            N_list[d] = 0
            d -= 1
        N_list[d] += 1
    elif 1<i:
        if N_list[i] == 5 and 5<=N_list[i-1]:
            N_list[i] = 0
            N_list[i-1] = 0
            d = i-2
            while(N_list[d]==9):
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        
print(sum(N_list)+sum(map(int,list(str(int("".join(map(str,N_list)))-int(N))))))

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_list = list((map(int,list(N))))
N_list.insert(0,0)
for i in range(len(N_list)-1,0,-1):
    if 6<=N_list[i] and N_list[i-1]<9:
        N_list[i] = 0
        N_list[i-1] += 1
    elif 5<=N_list[i] and N_list[i-1] == 9:
        N_list[i] = 0
        d = i-1
        while(N_list[d]==9):
            N_list[d] = 0
            d -= 1
        N_list[d] += 1
    elif 1<i:
        if N_list[i] == 5 and 5<=N_list[i-1]:
            N_list[i] = 0
            N_list[i-1] = 0
            d = i-2
            while(N_list[d]==9):
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        elif N_list[i] == 5 and N_list[i-1] == 5 and N_list[i-2] == 9:
            N_list 
        
print(sum(N_list)+sum(map(int,list(str(int("".join(map(str,N_list)))-int(N))))))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_list = list((map(int,list(N))))
N_list.insert(0,0)
for i in range(len(N_list)-1,0,-1):
    if 6<=N_list[i] and N_list[i-1]<9:
        N_list[i] = 0
        N_list[i-1] += 1
    elif 5<=N_list[i] and N_list[i-1] == 9:
        N_list[i] = 0
        d = i-1
        while(d==9):
            N_list[d] = 0
            d -= 1
        N_list[d] += 1
    elif 1<i:
        if N_list[i] == 5 and 5<=N_list[i-1]:
            N_list[i] = 0
            N_list[i-1] = 0
            d = i-2
            while(d==9):
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        elif N_list[i] == 5 and N_list[i-1] == 5 and N_list[i-2] == 9:
            N_list 

total = 0
for s in str(int("".join(map(str,N_list)))-int(N)):
    total += int(s)
print(sum(N_list)+total)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
N = []
ans = 0
l = len(str(n))

for i in range(l):
    N.append(int(str(n)[-i-1]))
N.append(0)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_list = list((map(int,list(N))))
N_list.insert(0,0)
for i in range(len(N_list)-1,0,-1):
    if 6<=N_list[i] and N_list[i-1]<9:
        N_list[i] = 0
        N_list[i-1] += 1
    elif 5<=N_list[i] and N_list[i-1] == 9:
        N_list[i] = 0
        d = i-1
        while(d==9):
            N_list[d] = 0
            d -= 1
        N_list[d] += 1
    elif 1<i:
        if N_list[i] == 5 and 5<=N_list[i-1]:
            N_list[i] = 0
            N_list[i-1] = 0
            d = i-2
            while(d==9):
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        elif N_list[i] == 5 and N_list[i-1] == 5 and N_list[i-2] == 9:
            N_list 
        
print(sum(N_list)+sum(map(int,list(str(int("".join(map(str,N_list)))-int(N))))))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    pay = ""
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay += str(n[i]+kuriage)
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
            else:
                if int(n[i])+kuriage <= 5:
                    pay += str(n[i]+kuriage)
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
        else:
            if int(n[i])+kuriage <= 5:
                pay += str(n[i]+kuriage)
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay += "0" 
                kuriage = 1

    if kuriage == 1:
        pay += "1"
        pay_count += 1
    
    pay = pay[::-1]
    oturi = int(pay)-N
    oturi_count = 0
    
    for i in str(oturi):
        oturi_count += int(i)
    print(pay_count+oturi_count)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

#    0, 1, 2, 3, 4, 5, 6, 7, 8, 9
P = [0, 1, 2, 3, 4, 0, 0, 0, 0, 0]
C = [0, 0, 0, 0, 0, 5, 4, 3, 2, 1]
X = [0, 1, 2, 3, 4, 5, 4, 3, 2, 1]
import sys
def solve(N):
    N = [int(c) for c in N]
    N = N[::-1]
    p = 0
    b = 0
    s = []
    for i in range(len(N)):
        c = N[i]
        c += b
        if c == 10:
            c = 0
            b = 1
            p += X[c]
            s.append(P[c])
        elif c == 5:
            if i == len(N)-1:
                p += 5
                s.append(5)
                b = 0
            else:
                if N[i+1] < 5:
                    p += 5
                    b = 0
                    s.append(5)
                else:
                    p += 5    
                    b = 1
                    s.append(0)
        elif c > 5:
            b = 1
            p += X[c]
            s.append(P[c])
        else:
            b = 0
            p += X[c]
            s.append(P[c])
    if b:
        s.append(b)
    #print(b, file=sys.stderr)
    return p + b, s[::-1]

def count(n):
    return sum([int(x) for x in str(n)])

def test(N):
    m = 10e10
    p = 0
    for P in range(N, N*10):
        n = count(P) + count(P - N)
        if n < m:
            p = P
            m = n
    e,s = solve(str(N))
    if e != m:
        print("N=%d"%N, "expected=%d"%m, p, "actual=%d"%e, "".join(str(c) for c in s))

N = [int(x) for x in input()]
a,_ = solve(N)
print(a)
if 1==1:
    for i in range(1, 1000):
        test(i)
    test(159)
    test(149)
    test(449)
    test(959)
    test(949)
    test(939)
    test(539)
    test(569)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

n=input()
lst=[int(n[i]) for i in range(len(n))]
# for i in range(len(n)):
#     lst.append(int(n[i]))
# n=int(n)

keta=len(lst)
ans=0
lst.reverse()

dp=[[float('inf')]*2 for i in range(keta+1)]
dp[0]=[0,1]
# print(dp)
for i in range(keta):
    dp[i+1][0]=min(dp[i][0]+lst[i],dp[i][1]+lst[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-lst[i]),dp[i][1]+(10-lst[i]-1))
# print(dp)
print(min(dp[-1][0],dp[-1][1]+1))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
try:
    t = int(math.log10(n) + 1)
except ValueError:
    t = len(str(n))

count = 0
while True:
    bottom = 10 ** (t-1)
    top = 10 ** t
    
    n = min(top-n,n-bottom)
    try:
        t = int(math.log10(n)+1)
    except ValueError:
        t = len(str(n))
    count += 1
    if n == 0:
        print(count)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

n=input()
lst=[int(n[i]) for i in range(len(n))]
# for i in range(len(n)):
#     lst.append(int(n[i]))
# n=int(n)

keta=len(lst)
ans=0
lst.reverse()

dp=[]
for i in range(keta+1):
    dp.append([float('inf')]*2)
dp[0]=[0,1]
# print(dp)
for i in range(keta):
    dp[i+1][0]=min(dp[i][0]+lst[i],dp[i][1]+lst[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-lst[i]),dp[i][1]+(10-lst[i]-1))
# print(dp)
print(min(dp[-1][0],dp[-1][1]+1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
# print(N)
kyaku = 0
mise = 0

while N:
    # print(N, kyaku, mise)
    c = N%10
    if c == 5 and N%100-c >= 50:
        mise += 10 - c
        N += 10
    elif c <= 5:
        kyaku += c
    else:
        mise += 10-c
        N += 10
    N = N//10

print(kyaku+mise)

Submission status: Time Limit Exceeded

Solution code:
N = input()
N_list = list((map(int,list(N))))
N_list.insert(0,0)
for i in range(len(N_list)-1,0,-1):
    if 6<=N_list[i] and N_list[i-1]<9:
        N_list[i] = 0
        N_list[i-1] += 1
    elif 5<=N_list[i] and N_list[i-1] == 9:
        N_list[i] = 0
        d = i-1
        while(d==9):
            N_list[d] = 0
            d -= 1
        N_list[d] += 1
    elif 1<i:
        if N_list[i] == 5 and 5<=N_list[i-1]:
            N_list[i] = 0
            N_list[i-1] = 0
            d = i-2
            while(d==9):
                N_list[d] = 0
                d -= 1
            N_list[d] += 1
        elif N_list[i] == 5 and N_list[i-1] == 5 and N_list[i-2] == 9:
            N_list 
        

ans = sum(N_list)

print(sum(N_list)+sum(list(map(int,list(str(int("".join(map(str,N_list)))-int(N)))))))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int):
    n = str(N)
    pay = ""
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if int(n[i-1]) >= 5:
                if int(n[i])+kuriage <= 4:
                    pay += str(int(n[i])+kuriage)
                    pay_count += int(n[i])+kuriage
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
            else:
                if int(n[i])+kuriage <= 5:
                    pay += str(int(n[i])+kuriage)
                    pay_count += int(n[i])+kuriage
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
        else:
            if int(n[i])+kuriage <= 5:
                pay += str(int(n[i])+kuriage)
                pay_count += int(n[i])+kuriage
                kuriage = 0
            else:
                pay += "0" 
                kuriage = 1

    if kuriage == 1:
        pay += "1"
        pay_count += 1
    
    pay = pay[::-1]
    oturi = int(pay)-N
    # pay_count = 0
    oturi_count = 0
    
    for i in str(oturi):
        oturi_count += int(i)

    print(pay_count+oturi_count)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nn = n
ans = 0
s = 0
count = 0
while n > 0:
    a = n%10
    b = min(a,10-a)
    if b == a and a != 5:
        s += b*10**count
    #    ans += b
        n = n//10
    elif a == 5 and (n//10)%10 < 5:
    #    ans += 1
        s += b*10**count
        n = n//10
    else:
   #     s += 10**(count+1)
   #     ans += 1
        n = n//10
        n += 1
    count += 1
o = s-nn
while s > 0:
    ans += s%10
    s = s//10
#print(ans)
#print(s)
#print(o)
while o > 0:
    ans += o%10
    o = o//10
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

srt_n = str(N)
keta = len(srt_n)

#ans = [0] * ( keta + 1 )
N_list = [0] * (keta+1)
ans_num = 0

for i in reversed(range(keta)):
    N_list[keta-i-1] = int(srt_n[i])

for i in range(keta+1):
    if N_list[i] == 5 and N_list[i+1] >= 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    elif N_list[i] > 5:
        #ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    else:
        #ans[i] =  N_list[i]
        ans_num += N_list[i]
#print(ans)
print(ans_num)

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
n = [0]+list(str(m))
for i in range(len(n)):
    n[i] = int(n[i])

for i in range(len(n)):
    if n[(i + 1) * (-1)] >= 10:
        n[(i + 1) * (-1)] -= 10
        n[(i + 2) * (-1)] += 1
    if n[(i + 1) * (-1)] >= 6:
        n[(i + 2) * (-1)] += 1
        n[(i + 1) * (-1)] = 0
    if n[(i + 1) * (-1)] == 5:
        if n[(i + 2) * (-1)] >= 5 :
            n[(i + 2) * (-1)] += 1
            n[(i + 1) * (-1)] = 0
cnt = sum(n)

num = ''
for i in n:
    num = num + str(i)
num = int(num)

m = num - m
n = [0]+list(str(m))
for i in range(len(n)):
    n[i] = int(n[i])
cnt += sum(n)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

n=input()
lst=[]
for i in range(len(n)):
    lst.append(int(n[i]))
# n=int(n)

keta=len(lst)
ans=0
lst.reverse()

dp=[]
for i in range(keta+1):
    dp.append([float('inf')]*2)
dp[0]=[0,1]
# print(dp)
for i in range(keta):
    dp[i+1][0]=min(dp[i][0]+lst[i],dp[i][1]+lst[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-lst[i]),dp[i][1]+(10-lst[i]-1))
# print(dp)
print(min(dp[-1][0],dp[-1][1]+1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int):
    n = str(N)
    pay = ""
    kuriage = 0
    LEN = len(n)

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if int(n[i-1]) >= 5:
                if int(n[i])+kuriage <= 4:
                    pay += str(int(n[i])+kuriage)
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
            else:
                if int(n[i])+kuriage <= 5:
                    pay += str(int(n[i])+kuriage)
                    kuriage = 0
                else:
                    pay += "0" 
                    kuriage = 1
        else:
            if int(n[i])+kuriage <= 5:
                pay += str(int(n[i])+kuriage)
                kuriage = 0
            else:
                pay += "0" 
                kuriage = 1

    if kuriage == 1:
        pay += "1"
    
    pay = pay[::-1]

    oturi = int(pay)-N
    pay_count = 0
    oturi_count = 0

    for i in pay:
        pay_count += int(i)
    
    for i in str(oturi):
        oturi_count += int(i)

    # print(pay)
    # print(oturi)
    print(pay_count+oturi_count)
    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


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


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


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


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, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from functools import lru_cache
import sys
sys.setrecursionlimit(1 << 25)

N = read_a_int()
siharai = ''


@lru_cache(None)
def F(n):
    '''
    支払う金額を返す。再帰関数
    '''
    global siharai
    # 終了条件
    assert n > -1
    if n < 5:
        siharai += str(n)
        return 0

    # 桁dpもどき
    # 1の位が4以下ならそのまま紙幣で支払うのが得→自身をそのまま答えに採用
    # 6以上ならばお釣り狙いのほうが得→自身は0にセットして、上位桁を+1する
    # 5ちょうどのときは？ #お釣りもそのまま払っても同じ。だけど上位 お釣り狙いだと上の桁が多くなって支払う金額が増える可能性がある？
    # 5ピッタリのときに上位桁に+1すると悪くなる場合が存在する 455 とは 15にってしまう
    # 5ピッタリのときはどうするのがよいのか？
    q, r = divmod(n, 10)
    if r == 5:
        qq, rr = divmod(q, 10)
        if rr < 5:
            # そのまま
            joint = 5
            F(q)
        else:
            joint = 0
            F(q + 1)
            # +1
    elif r < 5:
        joint = r
        F(q)
    else:
        joint = 0
        F(q + 1)
    siharai += str(joint)


F(N)
siharai = int(siharai)
oturi = siharai - N
# print(siharai, oturi)

ans = 0
for a in str(siharai) + str(oturi):
    ans += int(a)

# print(sum(list(siharai)) + sum(list(str(oturi))))
# print(sum(list(siharai)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


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


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


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


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, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from functools import lru_cache
import sys
sys.setrecursionlimit(1 << 25)

N = read_a_int()
siharai = ''


def F(n):
    '''
    支払う金額を返す。再帰関数
    '''
    global siharai
    # 終了条件
    assert n > -1
    if n < 5:
        siharai += str(n)
        return 0

    # 桁dpもどき
    # 1の位が4以下ならそのまま紙幣で支払うのが得→自身をそのまま答えに採用
    # 6以上ならばお釣り狙いのほうが得→自身は0にセットして、上位桁を+1する
    # 5ちょうどのときは？ #お釣りもそのまま払っても同じ。だけど上位 お釣り狙いだと上の桁が多くなって支払う金額が増える可能性がある？
    # 5ピッタリのときに上位桁に+1すると悪くなる場合が存在する 455 とは 15にってしまう
    # 5ピッタリのときはどうするのがよいのか？
    q, r = divmod(n, 10)
    if r == 5:
        qq, rr = divmod(q, 10)
        if rr < 5:
            # そのまま
            joint = 5
            F(q)
        else:
            joint = 0
            F(q + 1)
            # +1
    elif r < 5:
        joint = r
        F(q)
    else:
        joint = 0
        F(q + 1)
    siharai += str(joint)


F(N)
siharai = int(siharai)
oturi = siharai - N
# print(siharai, oturi)

ans = 0
for a in str(siharai) + str(oturi):
    ans += int(a)

# print(sum(list(siharai)) + sum(list(str(oturi))))
# print(sum(list(siharai)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
a = N % 10
while N > 0:
    b = N % 100 // 10
    if a < 5 or (a == 5 and b < 5):
        ans += a
        N = N // 10
        a=b
    else:
        ans += 10 - a
        N += 10
        N //=  10
        a = N % 10
        

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
flag = False
flag5 = False
for i in range(len(N)-1, -1, -1):
    x = N[i]
    if flag or (flag5 and x >= 5):
        x += 1
    flag5 = False
    flag = False
    if x > 5:
        ans += (10 - x)
        flag = True
        if i == 0:
            ans += 1
    else:
        ans += x
    if x == 5:
        flag5 = True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dis(a,num):
  return int((num % 10 ** (a + 1)) / 10 ** a)

inp_num = input()
intnum = int(inp_num)
ans = 0
i = 0
while intnum != 0:
  if dis(i,intnum) <= 4:
    ans += dis(i,intnum)
    intnum -= dis(i,intnum) * (10 ** i)
  elif (dis(i,intnum) == 5 and dis(i+1,intnum) >= 5) or dis(i,intnum) >= 6:
    ans += 10 - dis(i,intnum)
    intnum += (10 - dis(i,intnum)) * (10 ** i)
  else:
    ans += dis(i,intnum)
    intnum -= dis(i,intnum) * (10 ** i)
  i += 1
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

def get_d(s_int, shisuu):
    tmp = 10 ** shisuu
    if s_int < tmp:
        return None
    d = s_int % (tmp*10) // tmp
    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:
N = int(input())

srt_n = str(N)
keta = len(srt_n)

ans = [0] * ( keta + 1 )
N_list = [0] * (keta+1)
ans_num = 0

for i in reversed(range(keta)):
    N_list[keta-i-1] = int(srt_n[i])

for i in range(keta+1):
    if N_list[i] == 5 and N_list[i+1] >= 5:
        ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    elif N_list[i] > 5:
        ans[i] = 0
        N_list[i+1] += 1
        ans_num += 10 - N_list[i]
    else:
        ans[i] =  N_list[i]
        ans_num += N_list[i]
#print(ans)
print(ans_num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cin = 0
cout = 0
ans = 0

for i in range(len(str(N))):
  k = (N // (10 ** i)) % 10
  cin += k * (10 ** i)
  t = (cin // (10 ** i)) % 10
  if(t >= 6):
    cout += (10 - t) * (10 ** i)
    cin += 10 ** (i+1)
    cin -= t * (10 ** i)
  elif(t == 5):
    k1 = (N // (10 ** (i+1))) % 10
    cin += k1 * (10 ** (i+1))
    t1 = (cin // (10 ** (i+1))) % 10
    if(t1 >= 5):
      cout += (10 - t) * (10 ** i)
      cin += 10 ** (i+1)
      cin -= t * (10 ** i)
    cin -= k1 * (10 ** (i+1))
  
    
while(cin != 0):
  ans += (cin % 10)
  cin = cin // 10
while(cout != 0):
  ans += (cout % 10)
  cout = cout // 10

print(ans)

Submission status: Time Limit Exceeded

Solution code:
m = int(input())
n = list(str(m))
n.insert(0, 0)
for i in range(len(n)):
    n[i] = int(n[i])

for i in range(len(n)):
    if n[(i + 1) * (-1)] >= 10:
        n[(i + 1) * (-1)] -= 10
        n[(i + 2) * (-1)] += 1
    if n[(i + 1) * (-1)] >= 6:
        n[(i + 2) * (-1)] += 1
        n[(i + 1) * (-1)] = 0
    if n[(i + 1) * (-1)] == 5:
        if n[(i + 2) * (-1)] >= 5 :
            n[(i + 2) * (-1)] += 1
            n[(i + 1) * (-1)] = 0
cnt = sum(n)

num = ''
for i in n:
    num = num + str(i)
num = int(num)

m = num - m
n = list(str(m))
n.insert(0, 0)
for i in range(len(n)):
    n[i] = int(n[i])
cnt += sum(n)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
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] = d0
    dp[0][1] = d0+1

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

    return dp[n-1][0]

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

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 sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=pow(10,9)+7

n=input()
lst=[]
for i in range(len(n)):
    lst.append(int(n[i]))
n=int(n)

keta=len(lst)
ans=0
lst.reverse()
# print(lst)
dp=[[float('inf')]*2 for i in range(keta+1)]
dp[0]=[0,1]

for i in range(keta):
    dp[i+1][0]=min(dp[i][0]+lst[i],dp[i][1]+lst[i]+1)
    dp[i+1][1]=min(dp[i][0]+(10-lst[i]),dp[i][1]+(10-lst[i]-1))
# print(dp)
print(min(dp[-1][0],dp[-1][1]+1))