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 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
    for i in range(N-1,-1,-1):
        #print(ans)
        cur = int(S[i])
        if flag:
            cur += 1
        if cur>=6:
            ans += 10-cur
            flag = True
        else:
            ans += cur
            flag = False
    if flag:
        ans += 1
    print(ans)
    return

def examE2():
    S = SI()
    N = len(S)
    dp = [[0]*2 for _ in range(N+2)]
    dp[0][1] = inf
    S = S[::-1]
    S += "0"
    for i in range(N+1):
        s = int(S[i])
        dp[i+1][0] = dp[i][0] + s
        dp[i+1][1] = dp[i][0] + (10-s)
        if s<9:
            dp[i+1][0] = min(dp[i+1][0],dp[i][1] + (s+1))
        dp[i+1][1] = min(dp[i+1][1],dp[i][1] + (10-s-1))
    #print(dp)
    ans = min(dp[-1][0],dp[-1][1])
    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__':
    examE2()

"""
4396817
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())

memo = {0:0,1:1}
def f(price):
    if price in memo:
        return memo[price]
    n = price % 10
    res = min(f(price//10 + 1) + 10-n, f(price//10) + n)
    memo[price] = res
    return res

print(f(N))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N_str=input()
n=len(N_str)
N_str=list(reversed(N_str))
N_str.insert(0,"0")
N_str.insert(n+1,"0")
dp=np.full((n+2,2),np.Inf)
dp[0][0]=0
dp[0][1]=np.Inf


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

                if((dp[i-1][j]+a*2-x)<(dp[ni][nj])):
                
                    dp[ni][nj]=dp[i-1][j]+a*2-x
                else:
                    pass


    
print(int(dp[n+1][0]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# TLE (Python3 3.4.3)
# AC  (PyPy3 (2.4.0))

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    n = int(N[i])

    # 更新後のdp
    ni = i + 1

    # 前の桁で繰り下がりなし
    # 同じだけ払う
    dp[ni][0] = min(dp[ni][0], dp[i][0] + n)

    # 繰り下がりあり
    if n > 0:
        dp[ni][1] = min(dp[ni][1], dp[i][0] + (10 - n))
    else:
        dp[ni][0] = min(dp[ni][0], dp[i][0])

    # 前の桁で繰り下がりあり
    n += 1

    # 同じだけ払う
    if n == 10:
        dp[ni][1] = min(dp[ni][1], dp[i][1])
    else:
        dp[ni][0] = min(dp[ni][0], dp[i][1] + n)

    # 繰り下がりあり
    dp[ni][1] = min(dp[ni][1], dp[i][1] + (10 - n))


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    for j in range(2):
        # 繰り下がりも加味
        n = int(N[i])
        n += j

        # 更新後のdp
        ni = i + 1

        # 同じだけ払う
        if n < 10:
            dp[ni][0] = min(dp[ni][0], dp[i][j] + n)
        else:
            dp[ni][1] = min(dp[ni][1], dp[i][j])

        # 繰り下がりあり
        if n > 0:
            dp[ni][1] = min(dp[ni][1], dp[i][j] + (10 - n))
        else:
            dp[ni][0] = min(dp[ni][0], dp[i][j])


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    for j in range(2):
        # 繰り下がりも加味
        n = int(N[i])
        n += j

        # 更新後のdp
        ni = i + 1

        # 10通りから探索
        for a in range(10):
            nj = 0
            b = a - n

            # 繰り下がりあり
            if b < 0:
                b += 10
                nj = 1

            dp[ni][nj] = min(dp[i][j] + a + b, dp[ni][nj])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#それぞれの桁を考えた時にその桁を一つ多めに払うのかちょうどで払うのかで場合分けする

import math
n=int(input())
k=math.floor(math.log10(n))+1#桁数
n=str(n)#それぞれの桁にアクセスするためにイテラブルにする

#それぞれの桁を見ていくが、そのままと一つ多い状態から引く場合と二つあることに注意
dp=[[-1,-1] for _ in range(k)]
for i in range(k):
    if i==0:
        dp[i][0]=min(1+(10-int(n[i])),int(n[i]))
        dp[i][1]=min(1+(10-int(n[i])-1),int(n[i])+1)
    else:
        dp[i][0]=min(dp[i-1][1]+(10-int(n[i])),dp[i-1][0]+int(n[i]))
        dp[i][1]=min(dp[i-1][1]+(10-int(n[i])-1),dp[i-1][0]+int(n[i])+1)

print(dp[k-1][0])

Submission status: Time Limit Exceeded

Solution code:
n = input()

# 上の段:その桁をピッタリ払った, 下の段:その桁を払わなかった(上の桁で1多く払った)
dp = [[0 for i in range(len(n))] for j in range(2)]

dp[0][0] = int(n[0])
dp[1][0] = 1 + 10 - int(n[0])

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 引かれる数の左からi桁目に+10 & 引く数のi-1桁目に+1 を適宜行う

def calc(x):
    if 0 <= x <= 5:
        return x
    else:
        return 10-x+1

N = I()
S = str(N)
L = len(S)

dp0 = [0]*L
dp1 = [0]*L
dp0[0] = calc(int(S[0]))
dp1[0] = calc(int(S[0])+1)

for i in range(1,L):
    n = int(S[i])
    if n == 0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = min(dp0[i-1]+n, dp1[i-1]+10-n)
    if n == 9:
        dp1[i] = dp1[i-1]
    else:
        dp1[i] = min(dp0[i-1]+n+1, dp1[i-1]+9-n)

print(dp0[-1])

Submission status: Time Limit Exceeded

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

N = [int(x) for x in input().rstrip()][::-1] + [0]
L = len(N)

dp = [[10 ** 18, 10 ** 18] for _ in range(L)]
dp[0] = [N[0], 10 - N[0]]

for i in range(1, L):
    n = N[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(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()
s.append('0')

dp = [[1000000000] * 2 for _ in range(1000005)]
dp[0][0] = 0
n = len(s)
for i in range(n):
    for j in range(2):
        x = int(s[i])
        x += j
        if x < 10:
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][j] + x)
        if x > 0:
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][j] + (10 - x))

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()
s.append('0')

dp = [[1000000000] * 2 for _ in range(1000005)]
dp[0][0] = 0
n = len(s)
for i in range(n):
    for j in range(2):
        x = int(s[i])
        x += j
        for a in range(10):
            nj = 0
            otsuri = a - x
            if otsuri < 0:
                nj = 1
                otsuri += 10
            dp[i + 1][nj] = min(dp[i + 1][nj], dp[i][j] + a + otsuri)

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

Submission status: Time Limit Exceeded

Solution code:
strN = '0' + input()

N = int(strN)
numD = len(strN)

dp = [[float('inf')]*(2) for _ in range(numD+1)]
dp[0][0] = 0
for i, Ni in enumerate(reversed(strN), 1):
    Ni = int(Ni)
    if Ni == 9:
        dp[i][0] = dp[i-1][0] + Ni
    else:
        dp[i][0] = min(dp[i-1][0] + Ni, dp[i-1][1] + Ni + 1)
    dp[i][1] = min(dp[i-1][0] + 10 - Ni, dp[i-1][1] + 9 - Ni)

print(dp[numD][0])

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)



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


def II():
    return int(input())


#N=list(map(int,list(input())[::-1]))
N = list(map(int, list(input())))

dp=[[-1,-1] for i in range(len(N)+1)]
dp[0]=[0,1]
b=0
N.insert(0,0)

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

print(dp[-1][0])

Submission status: Time Limit Exceeded

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

import numpy

def main():
  n = input().strip()[::-1]
  dp = numpy.zeros((len(n), 2), dtype=numpy.int)
  dp[0][0] = int(n[0])
  dp[0][1] = 10 - int(n[0])
  for i, d in enumerate(map(int, n[1:]), 1):
    dp[i][0] = min(dp[i-1][0] + d,      dp[i-1][1] + 1 + d)
    dp[i][1] = min(dp[i-1][0] + 10 - d, dp[i-1][1] + 10 - (d + 1))
  print(min(dp[-1][0], dp[-1][1]+1))  

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

"""
コンテスト後に解説記事を見てAC
"""

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N_str):
    """
    https://betrue12.hateblo.jp/ の通り実装

    上の桁から順番に見ていく
    dp[i][j] =
      上から i 桁目までの硬貨の支払いとお釣りを処理し終わって、
      N の i 桁目までの金額よりも j 枚分多く支払っているときの、
      これまでの支払い・お釣り硬貨の最小合計枚数
    """
    N_str = '0' + N_str
    dp = [[0] * 2 for _ in range(len(N_str))]

    # 0376円のとき

    # dp[1][0] = 0       0円払う(0)
    # dp[1][1] = 1    1000円払う(1)
    #
    # dp[2][0] = 3    0円の状態から300円払う(3)  vs  1000円の状態から700円お釣りをもらう(8)
    # dp[2][1] = 4    0円の状態から400円払う(4)  vs  1000円の状態から600円お釣りをもらう(7)
    #
    # dp[3][0] = 7    300円の状態から追加で70円払う(3+7) vs 400円の状態から30円もらう(4+3)
    # dp[3][1] = 6    300円の状態から追加で80円払う(3+8) vs 400円の状態から20円もらう(4+2)
    #
    # dp[4][0] = 10   370円の状態から追加で6円払う(7+6) vs 380円の状態から4円もらう(6+4)
    # dp[4][1] = 9    370円の状態から追加で7円払う(7+7) vs 380円の状態から3円もらう(6+3)

    for i, ch in enumerate(N_str):
        if i == 0:
            dp[0][0] = 0
            dp[0][1] = 1
        else:
            dp[i][0] = min(dp[i - 1][0] + int(ch),
                           dp[i - 1][1] + 10 - int(ch))
            dp[i][1] = min(dp[i - 1][0] + int(ch) + 1,
                           dp[i - 1][1] + 9 - int(ch))

    return dp[len(N_str) - 1][0]


def wrong(N_str):
    """最初に間違って書いた貪欲
    1の位から見ていき、0~4なら支払い、5~9なら10払ってお釣りをもらう

    N = 65のとき、
    この関数だと70払って5お釣りをもらうことになるが
    実際は100払って35お釣りをもらうべきなので誤り
    """
    N_str = N_str[::-1]
    ans = 0
    prev = 0
    for ch in N_str:
        n = int(ch)
        n += prev
        if n <= 5:
            ans += n
            prev = 0
        else:
            ans += 10 - n
            prev = 1
    ans += prev    
    return ans

# for n in range(1, 101):
#     print()
#     n_str = str(n)
#     w = wrong(n_str)
#     gt = solve(n_str)
#     if w != gt:
#         print("n, gt, wrong = ", n, gt, w)

N_str = input()
print(solve(N_str))

Submission status: Time Limit Exceeded

Solution code:
nn = '0' + input()
ans = 0
dp = [[0 for i in range(2)] for j in range(len(nn))]
dp[0][1] = 1

for i,c in enumerate(nn[1:]):
    cc = int(c)
    zero = dp[i][0] + cc
    one = dp[i][1] + 10 - cc
    dp[i+1][0] = min(zero, one)
    dp[i+1][1] = min(zero + 1, one - (1 if i < len(nn) - 2 else 0))
print(min(dp[len(nn)-1]))
# print(dp)

Submission status: Time Limit Exceeded

Solution code:
nn = '0' + input()
ans = 0
dp = [[0 for i in range(2)] for j in range(len(nn))]
dp[0][1] = 1

for i,c in enumerate(nn[1:]):
    cc = int(c)
    dp[i+1][0] = min(dp[i][0] + cc, dp[i][1] + 10 - cc)
    dp[i+1][1] = min(dp[i][0] + cc + 1, dp[i][1] + 10 - cc - (1 if i < len(nn) - 2 else 0))
print(min(dp[len(nn)-1]))
# print(dp)

Submission status: Time Limit Exceeded

Solution code:

def solve():
  s = input()
  n = len(s)
  dp = [[float("Inf")]*2 for _ in range(n+1)]
  dp[0][0] = 0
  dp[0][1] = 1

  for i in range(0,n):
    number = int(s[i])
    for j in range(2):
      if j==0:
        dp[i+1][0] = min([dp[i][0]+number,dp[i][0]+(10-number)+1,dp[i+1][0]])
        if number != 9:
          dp[i+1][1] = min([dp[i][0]+number+1,dp[i][0]+(10-number),dp[i+1][1]])
      else:
        dp[i+1][0] = min(dp[i][1] +(10-number),dp[i+1][0])
        dp[i+1][1] = min(dp[i][1] + (10-number-1),dp[i+1][1])
        
  #print(dp)
  print(min(dp[n][0],dp[n][1]+1))
solve()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

# ピッタリ払う
dp0 = [INF] * (N + 1)
# 1 多く払う
dp1 = [INF] * (N + 1)

dp0[0] = 0
dp1[0] = 1
for i, c in enumerate(S):
    dp0[i + 1] = min(dp0[i] + int(c), dp1[i] + 10 - int(c))
    dp1[i + 1] = min(dp0[i] + int(c) + 1, dp1[i] + 10 - int(c) - 1)
# print(dp0)
# print(dp1)
print(dp0[-1])

Submission status: Time Limit Exceeded

Solution code:
# 通過の種類は10の100乗 + 1 種類
# 10の(10の100乗)乗の桁数は10の100乗桁 (1グーゴル)
# 10の6乗 = 1000000 (100万)
# 通過の方が圧倒的に大きい

s = input()[::-1]  # 与えられた数を下の桁から見る
length = len(s)
dp = [[0]*2 for _ in range(length+1)]  # j=1を更新するとき、お釣りの部分を格納していることになる（支払った1枚の紙幣は次のタイムステップで更新される）
for i in range(length):
    # 今見ている桁に関して、ちょうど支払うとき
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+int(s[i])+1)

    # 今見ている桁に関して、1つ大きい桁の紙幣を1枚使って支払う
    if i != 0:
        # ここで格納される値はお釣りの部分と考えることができる
        dp[i+1][1] = min(dp[i][0]+10-int(s[i]), dp[i][1]+(10-1)-int(s[i]))
    else:
        dp[i+1][1] = dp[i][0]+10-int(s[i])  # お釣りの部分のみが格納されている

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

Submission status: Time Limit Exceeded

Solution code:
N = input()

a = 0  # not carried
b = 0  # carried
t = int(N[-1]) % 10
a, b = a + t, a + (10 - t)
N = N[:-1]
while len(N) != 0:
    t = int(N[-1]) % 10
    a, b = min(a + t, b + (t + 1)), min(a + (10 - t), b + (10 - (t + 1)))
    N = N[:-1]
print(min(a, b + 1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a = 0  # not carried
b = 0  # carried
t = N % 10
a, b = a + t, a + (10 - t)
N //= 10
while N != 0:
    t = N % 10
    a, b = min(a + t, b + (t + 1)), min(a + (10 - t), b + (10 - (t + 1)))
    N //= 10
print(min(a, b + 1))

Submission status: Time Limit Exceeded

Solution code:
INF = float("inf")
dp = [[0] * 2 for _ in range(1000005)]

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

for i in range(n+1):
    for j in range(2):
        dp[i][j] = INF
dp[0][0] = 0

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

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

Submission status: Time Limit Exceeded

Solution code:
def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    #import numpy as np
    #dp=np.array(dp)
    return(dp[l+1])

s=input()
ans=dp_solver(s)
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    return(dp[l+1][0])

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    seq_flag=False
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if not seq_flag:
            if (num<5) or (num==5 and next_num<5):
                ans+=num
                next_bit=0
                kuri_cal=0
                continue
            seq_s=i
            seq_flag=True
            kuri_cal=10-num
            next_bit+=1
            continue
        #print(kuri_cal)
        if num<5:
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
            seq_flag=False
        elif num>5:
            kuri_cal+=10-num
        else:
            if next_num<5:
                ans+=(kuri_cal+num)
                next_bit=0
                kuri_cal=0
                seq_flag=False
            else:
                kuri_cal+=10-num
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=dp_solver(n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
tmp=input()
#tmp="9"*(10**5)
l=len(tmp)
rev=tmp[::-1]+"0"

dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
dp[0][0]=0
for i in range(l+1):
    for j in range(2):
        num=int(rev[i])
        num+=j
        if num<10:
            dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
        if num>0:
            dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

import numpy as np
#dp=np.array(dp)
print(dp[-1][0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

# Nの価値の物を購入する際に必要な最小紙幣数とおつりの合計枚数
# 入力はN
# 通貨は10のn乗の紙幣のみ

def gen(n):
    digit_value = []
    
    # while(n != 0):
    #     digit_value.append(n % 10)
    #     n //= 10
        
    # n = str(n)
    digit_value = [int(i) for i in str(n)]
    
    digit_value.append(0)
    digit_value.reverse()
    
    return digit_value

# 支払いに必要な最小の紙幣数
def num_payment(money):
    count = 0
    digit_value = gen(money) 
    num_digit = len(digit_value) - 1
    
    for i in range(1, num_digit + 1):
        if(digit_value[-i] <= 4 or (digit_value[-i] == 5 and digit_value[-(i+1)] < 5)):
             count += digit_value[-i]
        else:
            count += (10 - digit_value[-i])
            digit_value[-(i+1)] += 1
    
    return count + digit_value[0]
    

if __name__ == '__main__':
    value = int(input())
    print(num_payment(value))

Submission status: Time Limit Exceeded

Solution code:
def gen(n):
    digit_value = []
    
    # while(n != 0):
    #     digit_value.append(n % 10)
    #     n //= 10
        
    n = str(n)
    digit_value = [int(n[i]) for i in range(len(n))]
    
    digit_value.append(0)
    digit_value.reverse()
    
    return digit_value

# 支払いに必要な最小の紙幣数
def num_payment(money):
    count = 0
    digit_value = gen(money) 
    num_digit = len(digit_value) - 1
    
    for i in range(1, num_digit + 1):
        if(digit_value[-i] <= 4 or (digit_value[-i] == 5 and digit_value[-(i+1)] < 5)):
             count += digit_value[-i]
        else:
            count += (10 - digit_value[-i])
            digit_value[-(i+1)] += 1
    
    return count + digit_value[0]
    

if __name__ == '__main__':
    value = int(input())
    print(num_payment(value))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

# Nの価値の物を購入する際に必要な最小紙幣数とおつりの合計枚数
# 入力はN
# 通貨は10のn乗の紙幣のみ

def gen(n):
    digit_value = []
    
    # while(n != 0):
    #     digit_value.append(n % 10)
    #     n //= 10
        
    n = str(n)
    digit_value = [int(n[i]) for i in range(len(n))]
    
    digit_value.append(0)
    digit_value.reverse()
    
    return digit_value

# 支払いに必要な最小の紙幣数
def num_payment(money):
    count = 0
    digit_value = gen(money) 
    num_digit = len(digit_value) - 1
    
    for i in range(1, num_digit + 1):
        if(digit_value[-i] <= 4):
             count += digit_value[-i]
        elif(digit_value[-i] == 5):
            if(digit_value[-(i+1)] < 5):
                count += digit_value[-i]
            else:
                count += (10 - digit_value[-i])
                digit_value[-(i+1)] += 1
        else:
            count += (10 - digit_value[-i])
            digit_value[-(i+1)] += 1
    
    return count + digit_value[0]
    

if __name__ == '__main__':
    value = int(input())
    print(num_payment(value))

Submission status: Time Limit Exceeded

Solution code:
def gen(n):
    digit_value = []
    
    while(n != 0):
        digit_value.append(n % 10)
        n //= 10
    
    digit_value.append(0)
    digit_value.reverse()
    
    return digit_value

# 支払いに必要な最小の紙幣数
def num_payment(money):
    count = 0
    digit_value = gen(money) 
    num_digit = len(digit_value) - 1
    
    for i in range(1, num_digit + 1):
        if(digit_value[-i] <= 4):
             count += digit_value[-i]
        elif(digit_value[-i] == 5):
            if(digit_value[-(i+1)] < 5):
                count += digit_value[-i]
            else:
                count += (10 - digit_value[-i])
                digit_value[-(i+1)] += 1
        else:
            count += (10 - digit_value[-i])
            digit_value[-(i+1)] += 1
    
    return count + digit_value[0]

if __name__ == '__main__':
    value = int(input())
    print(num_payment(value))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32

def solve(N: int):
    # from functools import lru_cache
    # # abc154を参考にメモ化で出すとTLE
    # @lru_cache(None)
    # def f(n: int):
    #     if 0 <= n <=5:
    #         return n
    #     elif 6 <= n < 10:
    #         return 10-n+1

    #     q, r = divmod(n, 10)
    #     # print(q, r)
    #     return min(
    #         f(q)+r,
    #         f(q+1)+10-r
    #     )
    # print(f(N))

    # N=36を考える
    l = list(map(int, list(str(N))))
    dp = 0,1
    for i in l:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

def solve(N: int):
    # from functools import lru_cache
    # # abc154を参考にメモ化で出すとTLE
    # @lru_cache(None)
    # def f(n: int):
    #     if 0 <= n <=5:
    #         return n
    #     elif 6 <= n < 10:
    #         return 10-n+1

    #     q, r = divmod(n, 10)
    #     # print(q, r)
    #     return min(
    #         f(q)+r,
    #         f(q+1)+10-r
    #     )
    # print(f(N))

    # N=36を考える
    l = list(map(int, list(str(N))))
    dp = 0,1
    for i in l:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

def solve(N: int):
    from functools import lru_cache
    # abc154を参考にメモ化で出すとTLE
    @lru_cache(None)
    def f(n: int):
        if 0 <= n <=5:
            return n
        elif 6 <= n < 10:
            return 10-n+1

        q, r = divmod(n, 10)
        # print(q, r)
        return min(
            f(q)+r,
            f(q+1)+10-r
        )
    # print(f(N))

    # N=36を考える
    l = list(map(int, list(str(N))))
    dp = 0,1
    for i in l:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int):
    from functools import lru_cache

    @lru_cache(None)
    def f(n: int):
        if 0 <= n <=5:
            return n
        elif 6 <= n < 10:
            return 10-n+1

        q, r = divmod(n, 10)
        # print(q, r)
        return min(
            f(q)+r,
            f(q+1)+10-r
        )

    print(f(N))

    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 sys
inf = sys.maxsize

n = int(input())
l = len(str(n))
m = [int(str(n)[i]) for i in range(l)]

'''
a = []
for i in range(l):
    if m[i] <= 5:
        a.append(0)
    elif m[i] > 5:
        a.append(1)

for i in range(l):
    if i < l-1 and a[i+1] == 1 and m[i] == 5:
        a[i] = 1

p = []
for i in range(l):
    if a[i] == 0:
        if i < l-1 and a[i+1] == 1:
            p.append(m[i]+1)
        else:
            p.append(m[i])
    elif a[i] == 1:
        p.append(0)

pp = ''
for i in range(l):
    pp += str(p[i])
if pp[0] == '0':
    pp = '1' + pp
pp = int(pp)
oo = pp - n
print(pp)
print(oo)
ppp = [int(str(pp)[i]) for i in range(len(str(pp)))]
ooo = [int(str(oo)[i]) for i in range(len(str(oo)))]

print(sum(ppp) + sum(ooo))
'''
dp = [0, 1] #dp[0]: ちょうど dp[1]: 1多い

for i in m:
    dp0 = dp[0]
    dp1 = dp[1]
    dp[0] = min(dp0 + i, dp1 + (10 - i))
    dp[1] = min(dp0 + i + 1, dp1 + (10 - i) - 1)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
s += "0"
n = len(s)
INF = 10 ** 18
dp = [[INF for _ in range(2)] for _ in range(n + 5)]
"""
dp[i][j] = 下からi桁目まで決めて繰り下がりがjの時の最小値, i = 0 to N, j = 0 or 1
"""
dp[0][0] = 0

# print(s)

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



print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]
s += "0"
n = len(s)
INF = 10 ** 18
dp = [[INF for _ in range(2)] for _ in range(n + 5)]
"""
dp[i][j] = 下からi桁目まで決めて繰り下がりがjの時の最小値, i = 0 to N, j = 0 or 1
"""
dp[0][0] = 0

# print(s)

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

print(dp[n][0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

# N は払わなければならない金額
# a は払う金額
# b はおつり

# a を決めていく（配る）dp

S = list(str(N))
S.reverse()
S += "0"
S = list(map(int, S))
n = len(S)

# i 桁目まで決め（1 <= i）、
# 前の桁で繰り下がりがあった（j = 1）かなかった（j = 0）かが決まれば、
# 最小値が決定する
INF = 1001001001
dp = [[INF, INF] for _ in range(n + 5)]
dp[0][0] = 0 # 何にも決めてないから 0

# dpを埋める
for i in range(n):
	for j in range(2):
		x = S[i] # x とは、N_i を指す
		x += j
		# a を決めていくdpだからAに関するforを回す
		for a in range(10):
			ni = i + 1
			nj = 0 # 次の i と j
			b = a - x # b = a - N
			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:
N = input()

flag = 0
res = 0
while len(N) > 0:
	n = int(N[len(N)-1])

	if flag == 2:
		if n <= 4:
			flag = 0
			res += n
		elif n == 5:
			flag = 1
			res += 4
		elif n >= 6:
			flag = 1
			res += 9 - n
	else:
		if flag == 1:
			n += 1
		if n == 5:
			flag = 2
			res += 5
		elif n > 5:
			flag = 1
			res += 10 - n
		else:
			flag = 0
			res += n
		
	N = N[:len(N)-1]

if flag == 1:
	print(res + 1)
else:
	print(res)