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: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

#N,K=map(int,input().split())
#A=Sorted(list(map(int,input().split())))


N=input()
count=0
flag=0
for i in range(0,len(N)):
    n=int(N[i])
    if n<=4:
        count+=n
    elif n==5:
        count+=n
        flag=1
    else:
        if flag==1:
            count-=1
        count+=10-n+1
        flag=1
print(count)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

#N,K=map(int,input().split())
#A=Sorted(list(map(int,input().split())))


N=input()
count=0
flag=0
for i in range(0,len(N)):
    n=int(N[i])
    if n<=4:
        count+=n
    elif n==5:
        count+=n
        flag=1
    else:
        if flag==1:
            count-=1
        count+=10-n+1
print(count)

Submission status: Wrong Answer

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


count = 0
top = True
for i in n:
    i = int(i)
    if i <= 5:
        count += i
    else:
        if top:
            count += 1 + (10 - i)
        else:
            count += 10 - i
    top = False

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
index = 0
def f(n):
    global ans, index
    lenn = len(n)
    while index < lenn and (n[index] < '5' or (n[index] == '5' and (index == lenn - 1 or n[index+1] <= '4'))):
        ans += int(n[index])
        index += 1
    if index < lenn:
        ans += 1
        f(str(10**len(n)-int(n)))
f(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
index = 0
def f(n):
    global ans, index
    lenn = len(n)
    while index < lenn and (n[index] < '5' or (n[index] == '5' and (index == lenn - 1 or n[index+1] <= '4'))):
        ans += int(n[index])
        index += 1
    if index < lenn:
        ans += 1
        f(str(10**len(n)-int(n)))
f(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
def f(n):
    global ans
    while n and (n[0] < '5' or (n[0] == '5' and (len(n) == 1 or n[1] <= '4'))):
        ans += int(n[0])
        n = n[1:]
    if n:
        ans += 1
        f(str(10**len(n)-int(n)))
f(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
keta = len(s)
n = int(s)

ans = 0
while n > 0:
    hoge = 10 ** (keta-1)
    t = n // (hoge)
    if t == 0:
        keta -= 1
        continue

    if t < 5 or (t == 5 and ((n // (hoge//10) if hoge >= 10 else 0) <= 54)):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * hoge
        keta -= 1

    else:
        ans += 1
        n = hoge*10 - n  # どちらがお金を払うかが入れ替わる

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
keta = len(s) + 1
n = int(s)

ans = 0
while n > 0:
    keta -= 1
    hoge = 10 ** (keta-1)
    t = n // (hoge)
    pre_t = n // (hoge//10) if hoge >= 10 else 0
    if t == 0:
        continue
    #print(n, t, pre_t, keta, hoge)
    if t < 5 or (t == 5 and pre_t <= 54):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * hoge
        #print(t * hoge,'払った,残り', n, ans)
    else:
        ans += 1
        keta += 1
        n = hoge*10 - n  # どちらがお金を払うかが入れ替わる
        #print(hoge*10,'払った,お釣り', n, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

ans = 0
while n > 0:
    t = n
    pre_t = t
    keta = 0
    while t >= 1000000000:
        pre_t = t
        t //= 1000000000
        keta += 9
    while t >= 10:
        pre_t = t
        t //= 10
        keta += 1
    if t < 5 or (t == 5 and pre_t <= 54):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * (10 ** keta)
        #print(t * (10 ** keta),'払った,残り', n, ans)
    else:
        ans += 1
        n = (10 ** (keta + 1)) - n  # どちらがお金を払うかが入れ替わる
        #print((10 ** (keta + 1)),'払った,お釣り', n, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = input()

ans = 0
while n:
    t = n[0]
    pre_t = n[:2]
    keta = len(n)-1
    #print(t, pre_t)
    if t < '5' or (t == '5' and pre_t <= '54'):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += int(t)
        n = n[1:]
        #print(n[0],'払った,残り', n, ans)
    else:
        ans += 1
        n = str((10 ** (keta + 1)) - int(n))  # どちらがお金を払うかが入れ替わる
        #print((10 ** (keta + 1)),'払った,お釣り', n, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

# 0, 0+0
# 1, 1+0
# 2, 2+0
# 3, 3+0
# 4, 4+0
# 5, 5+0
# 6, 1+4
# 7, 1+3
# 8, 1+2
# 9, 1+1
# 99, 2枚
# 99999, 2枚...
ans = 0
while n > 0:
    t = n
    pre_t = t
    keta = 0
    while t >= 10:
        pre_t = t
        t //= 10
        keta += 1
    if t < 5 or (t == 5 and pre_t <= 54):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * (10 ** keta)
        #print(t * (10 ** keta),'払った,残り', n, ans)
    else:
        ans += 1
        n = (10 ** (keta + 1)) - n  # どちらがお金を払うかが入れ替わる
        #print((10 ** (keta + 1)),'払った,お釣り', n, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

# 0, 0+0
# 1, 1+0
# 2, 2+0
# 3, 3+0
# 4, 4+0
# 5, 5+0
# 6, 1+4
# 7, 1+3
# 8, 1+2
# 9, 1+1
# 99, 2枚
# 99999, 2枚...
ans = 0
while n > 0:
    t = n
    pre_t = t
    keta = 0
    while t >= 10:
        pre_t = t
        t //= 10
        keta += 1
    if t < 5 or (t == 5 and pre_t <= 54):  # 555 の時とか1000円だすと14枚で行けてしまう。。
        ans += t
        n = n - t * (10 ** keta)
        #print(t * (10 ** keta),'払った,残り', n, ans)
    else:
        ans += 1
        n = (10 ** (keta + 1)) - n  # どちらがお金を払うかが入れ替わる
        #print((10 ** (keta + 1)),'払った,お釣り', n, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 1001001001

s = input()
s = s[::-1]
s += '0'
n = len(s)

dp = [[INF, INF] for _ in range(n + 1)]
dp[1][0], dp[1][1] = int(s[0]), 10 - int(s[0])

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

ans = dp[n][0]
print(ans)

Submission status: Time Limit Exceeded

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


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):
    l = list(map(int, str(N)[::-1]))
    n_0, n_1 = 0, 1  # 0: その桁で処理, 1: 次の桁に1タス
    for i in l:
        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 = int(input())
    ans = solve(N)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

n = int(input())

c = 0
while n > 0:
    m = str(n)
    l = len(m)

    if len(m) >= 2:
        if int(m[0]) <= 4 or (int(m[0]) ==5 and int(m[1]) <= 5):
            c = c + int(m[0])
            n = n - int(m[0])*10**(l-1)
        else:
            c = c + 1
            n = 10**l - n
    else:
        if int(m[0]) <= 5:
            c = c + int(m[0])
            n = n - int(m[0]) * 10 ** (l - 1)
        else:
            c = c + 1
            n = 10 ** l - n

print(c)

Submission status: Time Limit Exceeded

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.array([[0, 0] for _ in range(len(N))])
    main(N, dp)

Submission status: Time Limit Exceeded

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

Solution code:
s='0'
s+=input()
n=len(s)
inf=float('inf')
dp=[[inf]*2 for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(2):
    si=int(s[-i-1])
    si+=j
    for a in range(10):
      ni=i+1
      nj=0
      b=a-si
      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: Time Limit Exceeded

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    L = list(map(int, reversed(li())))
    n = len(L)
    payment = L[:]
    payment.append(0)

    for i in range(n):
        if 5 < payment[i] or (5 == payment[i] and 5 <= payment[i+1]):
            payment[i] = 0
            payment[i+1] += 1
    
    # print(L)    
    # print(list(reversed(payment)))

    ans = 0
    ans += sum(payment)

    a = int(''.join(list(map(str, reversed(L)))))
    b = int(''.join(list(map(str, reversed(payment)))))
    # print(f"required {a}, paid: {b}")
    ans += sum(map(int, list(str(b - a))))

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ans=0
ns=str(n)
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ans=0
l=[]
for _ in range(10**6+1):
    x=n%10
    l.append(x)
    n=(n-x)//10
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
memo = {}
def search(x):
    if x in memo:
        return memo[x]

    sx = str(x)
    sn = len(sx)

    if sn == 1:
        if x <= 5:
            return x
        else:
            return 11 - x

    if int(sx[0]) < 9:
        p = int(sx[0]) + 1
    else:
        p = 1
    res1 = search(int(sx[1:])) + int(sx[0])
    res2 = search((int(sx[0]) + 1) * (10 ** (sn - 1)) - x) + p

    memo[x] =  min(res1, res2)
    return memo[x]

print(search(n))

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint


def main():
    n = input().strip()
    # print("finish reading")
    digits = [int(x) for x in n]

    # print(sz)

    INF = 10**7

    sz = len(n)
    cache = [[-INF]*3 for _ in range(sz)]
    # print("finish cache")

    def dfs(which, one_more):
        # digit = int(n[which])
        digit = digits[which]

        if which + 1 == sz:
            ans = digit-one_more
            if one_more:
                ans = min(ans, 10-digit)
            return ans

        # if (which, one_more) in cache:
        #     return cache[(which, one_more)]
        if cache[which][one_more+1] != -INF:
            return cache[which][one_more+1]

        # exactly
        ans = digit + dfs(which+1, 0)-one_more
        if one_more:
            ans = min(ans, 10-digit+dfs(which+1, 0))
        # one more for next
        ans = min(ans, digit + 1 + dfs(which+1, 1)-one_more)
        if one_more:
            ans = min(ans, 10-digit-1+dfs(which+1, -1))

        # cache[(which, one_more)] = ans
        cache[which][one_more+1] = ans
        return ans

    sys.setrecursionlimit(10**6+10)
    # print("finish setting")

    ans = min(1+dfs(0, 1), dfs(0, 0))
    print(ans)

    # pprint(cache)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint

def main():
    n = input()
    # print("finish reading")

    # print(len(n))

    INF = 10**7

    cache = [[-INF]*3 for _ in range(len(n))]


    def dfs(which, one_more):
        digit = int(n[which])

        if which + 1 == len(n):
            ans = digit-one_more
            if abs(one_more) == 1:
                ans = min(ans, 10-digit)
            return ans

        # if (which, one_more) in cache:
        #     return cache[(which, one_more)]
        if cache[which][one_more+1]!=-INF:
            return cache[which][one_more+1]

        # exactly
        ans = digit + dfs(which+1, 0)-one_more
        if abs(one_more) == 1:
            ans = min(ans, 10-digit+dfs(which+1, 0))
        # one more for next
        ans = min(ans, digit + 1 + dfs(which+1, 1)-one_more)
        if abs(one_more) == 1:
            ans = min(ans, 10-digit-1+dfs(which+1, -1))

        # cache[(which, one_more)] = ans
        cache[which][one_more+1]=ans
        return ans


    sys.setrecursionlimit(10**6+10)


    ans = min(1+dfs(0, 1), dfs(0, 0))
    print(ans)

    # pprint(cache)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint
n = input()

# print(len(n))

INF = 10**7

cache = [[-INF]*3 for _ in range(len(n))]


def dfs(which, one_more):
    digit = int(n[which])

    if which + 1 == len(n):
        ans = digit-one_more
        if abs(one_more) == 1:
            ans = min(ans, 10-digit)
        return ans

    # if (which, one_more) in cache:
    #     return cache[(which, one_more)]
    if cache[which][one_more+1]!=-INF:
        return cache[which][one_more+1]

    # exactly
    ans = digit + dfs(which+1, 0)-one_more
    if abs(one_more) == 1:
        ans = min(ans, 10-digit+dfs(which+1, 0))
    # one more for next
    ans = min(ans, digit + 1 + dfs(which+1, 1)-one_more)
    if abs(one_more) == 1:
        ans = min(ans, 10-digit-1+dfs(which+1, -1))

    # cache[(which, one_more)] = ans
    cache[which][one_more+1]=ans
    return ans


sys.setrecursionlimit(10**6+10)


ans = min(1+dfs(0, 1), dfs(0, 0))
print(ans)

# pprint(cache)

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint
n = input()

# print(len(n))

cache = [[-1]*3 for _ in range(len(n))]


def dfs(which, one_more):
    digit = int(n[which])

    if which + 1 == len(n):
        ans = digit-one_more
        if abs(one_more) == 1:
            ans = min(ans, 10-digit)
        return ans

    # if (which, one_more) in cache:
    #     return cache[(which, one_more)]
    if cache[which][one_more+1]!=-1:
        return cache[which][one_more+1]

    # exactly
    ans = digit + dfs(which+1, 0)-one_more
    if abs(one_more) == 1:
        ans = min(ans, 10-digit+dfs(which+1, 0))
    # one more for next
    ans = min(ans, digit + 1 + dfs(which+1, 1)-one_more)
    if abs(one_more) == 1:
        ans = min(ans, 10-digit-1+dfs(which+1, -1))

    # cache[(which, one_more)] = ans
    cache[which][one_more+1]=ans
    return ans


sys.setrecursionlimit(10**6+10)


ans = min(1+dfs(0, 1), dfs(0, 0))
print(ans)

# pprint(cache)

Submission status: Time Limit Exceeded

Solution code:
import sys
from pprint import pprint
n = input()

# print(len(n))

cache = {}


def dfs(which, one_more):
    digit = int(n[which])

    if which + 1 == len(n):
        ans = digit-one_more
        if abs(one_more) == 1:
            ans = min(ans, 10-digit)
        return ans

    if (which, one_more) in cache:
        return cache[(which, one_more)]

    # exactly
    ans = digit + dfs(which+1, 0)-one_more
    if abs(one_more) == 1:
        ans = min(ans, 10-digit+dfs(which+1, 0))
    # one more for next
    ans = min(ans, digit + 1 + dfs(which+1, 1)-one_more)
    if abs(one_more) == 1:
        ans = min(ans, 10-digit-1+dfs(which+1, -1))

    cache[(which, one_more)] = ans
    return ans


sys.setrecursionlimit(10**6+10)


ans = min(1+dfs(0, 1), dfs(0, 0))
print(ans)

# pprint(cache)

Submission status: Time Limit Exceeded

Solution code:
s = input()
keta = len(s)
n = int(s)
infi = 10 ** 10
dp = [[infi] * (2) for _ in range(keta + 1)]
dp[0][0] = 0
s = s[::-1]
for i in range(keta):
    for j in range(2):
        num = int(s[i])
        if j == 1:
            num += 1
        ni = i + 1
        if num == 10:
            nj = 1
            num = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num < 5:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num > 5:
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
        else:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
print(min(dp[keta][0], dp[keta][1] + 1))

Submission status: Time Limit Exceeded

Solution code:
s = input()
keta = len(s)
n = int(s)
infi = 10 ** 10
dp = [0] * (keta + 1)
dp[0] = 0
s = s[::-1] + "0"
kuri = 0
for i in range(keta):
    ni = i + 1
    num = int(s[i])
    if kuri:
        num += 1
        kuri = 0
    if num == 10:
        kuri = 1
        dp[ni] = dp[i]
    elif num < 5:
        dp[ni] = dp[i] + num
    elif num > 5:
        num %= 10
        kuri = 1
        dp[ni] = dp[i] + 10 - num
    else:
        nn = int(s[i + 1])
        if nn < 5:
            dp[ni] = dp[i] + num
        else:
            kuri = 1
            dp[ni] = dp[i] + 10 - num
print(dp[keta] + kuri)

Submission status: Time Limit Exceeded

Solution code:
s = input()
keta = len(s)
n = int(s)
infi = 10 ** 10
dp = [[infi] * (2) for _ in range(keta + 1)]
dp[0][0] = 0
for i in range(keta):
    num = int(s[-i - 1])
    for j in range(2):
        if j == 1:
            num += 1
        ni = i + 1
        if num == 10:
            nj = 1
            num = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num < 5:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
        elif num > 5:
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
        else:
            nj = 0
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num)
            nj = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 10 - num)
print(min(dp[keta][0], dp[keta][1] + 1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
a = [0] + list(map(int, list(input())))
n = len(a)
dp = [[10 ** 9] * 2 for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(n):
    dp[i + 1][0] = min(dp[i][0] + a[i], dp[i][1] + 10 - a[i])
    dp[i + 1][1] = min(dp[i][0] + a[i] + 1, dp[i][1] + 10 - a[i] - 1)
print(dp[n][0])

Submission status: Time Limit Exceeded

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

for i in range(len(N)):
    for j in range(2):
        x = int(N[i])
        x += j
        for k in range(10):
            nexti = i + 1
            nextj = 0
            b = k - x
            if b < 0:
                nextj = 1
                b += 10
            dp[nexti][nextj] = min(dp[nexti][nextj], dp[i][j] + k + b)
print(dp[len(N)][0])

Submission status: Time Limit Exceeded

Solution code:
n=input()
keta=len(n)
n=int(n)
satsu=0

for i in range(keta+1):
	tmp = n % 10
	n = n//10
	if tmp == 5 and n % 10 >= 5:
		satsu += 10 - tmp
		n += 1
	
	elif 0 <= tmp <= 5:
		satsu += tmp
	else:
		satsu += 10 - tmp
		n += 1

print(satsu)

Submission status: Time Limit Exceeded

Solution code:
s = [0] + map(int,list(raw_input()))
dp = [+float('inf')] * len(s)

for j in range(len(s) - 1, -1, -1):
	a = s[j]
	if j+ 1 < len(dp): a += dp[j + 1] 
	dp[j] = min(a, dp[j])

	b = s[j] + 1
	q = 0
	for jj in range(j+1, len(s)):
		q += 9 - s[jj]
		dp[j] = min(dp[j], b + q + 1 +(dp[jj+1] if jj+1 < len(dp) else 0))

print dp[0]

Submission status: Time Limit Exceeded

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

DP[0][0]=int(N[0])
DP[0][1]=10-int(N[0])

#print(DP)
#print(N)
for i in range(1,len(N)):
    DP[i][0]=min(DP[i-1][0]+int(N[i]),DP[i-1][1]+int(N[i])+1)
    DP[i][1]=min(DP[i-1][0]+10-int(N[i]),DP[i-1][1]+10-(int(N[i])+1))
#print(DP)
print(min(DP[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)
N = int(input())
@lru_cache(None)
def f(n):
  if n<10:
    if n<=5:
      return n
    else:
      return 10-n+1
  p,q = divmod(n,10)
  
  return min(f(p)+q, f(p+1)+10-q)
print(f(N))

Submission status: Time Limit Exceeded

Solution code:
N=input()
L=len(N)
ans=[[0 for e in range(2)] for f in range(L)]
k=int(N[L-1])
ans[0][0]=k
ans[0][1]=10-k
if L>1:
 for i in range(1,L):
  k=int(N[L-1-i])
  ans[i][0]=min(ans[i-1][0]+k,ans[i-1][1]+k+1)
  ans[i][1]=min(ans[i-1][0]+10-k,ans[i-1][1]+10-k-1)
print(min(ans[L-1][0],ans[L-1][1]+1))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
lst=[int(d) for d in str(N)]
L=len(lst)
ans=[[0 for e in range(2)] for f in range(L)]
ans[0][0]=lst[L-1]
ans[0][1]=10-lst[L-1]
for i in range(1,L):
 ans[i][0]=min(ans[i-1][0]+lst[L-1-i],ans[i-1][1]+lst[L-1-i]+1)
 ans[i][1]=min(ans[i-1][0]+10-lst[L-1-i],ans[i-1][1]+10-lst[L-1-i]-1)
print(min(ans[L-1][0],ans[L-1][1]+1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(n)
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)
l = len(s)

INF = float('inf')
dp = [[INF,INF] for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    num = int(s[i])
    dp[i+1][0] = min(dp[i][0]+num, dp[i][1]+min(10-num,num+1))
    dp[i+1][1] = min(dp[i][0]+num+1,dp[i][1]+10-num-1)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp0 = [INF for _ in range(len(s)+1)]
dp1 = [INF for _ in range(len(s)+1)]
dp0[0]=0
dp1[0]=1
for i in range(len(s)):
    dp0[i+1] = min(dp0[i]+int(s[i]), dp1[i]+10-int(s[i]), dp1[i]+int(s[i])+1)
    dp1[i+1] = min(dp0[i]+int(s[i])+1,dp1[i]+10-int(s[i])-1)

print(dp0[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+10-int(s[i]), dp[i][1]+int(s[i])+1)
    dp[i+1][1] = min(dp[i][0]+int(s[i])+1,dp[i][1]+10-int(s[i])-1)

print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
n=input()[::-1]
n+="0"
lt=len(n)
dp=[[float('inf') for _ in range(2)] for j in range(lt+1)]
dp[0][0]=0

for i in range(0,lt):
    for j in range(2):
        x=int(n[i])
        x+=j #繰り上がり処理，あとに+11でもOK
        for num in range(0,10):
            ni = i + 1
            nj = 0
            b=num-x
            if b<0:
                b+=10
                nj=1
            dp[ni][nj]=min(dp[ni][nj],dp[i][j]+num+b)

print(dp[lt][0])