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:
N = int(input())
N = list(str(N))
N = [int(i) for i in N]

# print(N)
ans = 0
DP = [0] *2
DP[0] = 0
DP[1] = 1
for i in N:
    a, b = DP[0] ,DP[1]
    DP[0] = a + i if a+i < b +(10-i) else b +(10-i)
    DP[1] = a + i+1 if a + i+1 < b + (9-i) else b + (9-i)

    # print(DP)

print(DP[0] if DP[0] <= DP[1]+1 else DP[1] +1)

Submission status: Time Limit Exceeded

Solution code:
n = input()
s = []
for c in n:
    s.append(int(c))
s.reverse()
l = len(s)
INF = 1000000000


def get_next(c):
    ret = [
        [INF, INF],
        [INF, INF],
    ]
    for a in range(10):
        for b in range(10):
            if a - b == c:
                ret[0][0] = min(ret[0][0], a + b)
            if 10 + a - b == c:
                ret[0][1] = min(ret[0][1], a + b)
            if a - 1 - b == c:
                ret[1][0] = min(ret[1][0], a + b)
            if 10 + a - 1 - b == c:
                ret[1][1] = min(ret[1][1], a + b)
    return ret


dp = [[0 for _ in range(l+1)] for _ in range(2)]

dp[1][0] = INF

for i, c in enumerate(s):
    next_step = get_next(c)
    dp[0][i+1] = min(dp[0][i]+next_step[0][0], dp[1][i]+next_step[1][0])
    dp[1][i+1] = min(dp[0][i]+next_step[0][1], dp[1][i]+next_step[1][1])

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

Submission status: Time Limit Exceeded

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


dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(sys.stdin.readline())

ans = 0
p = [0,0]
now = [0,0]
p[0] = n%10
p[1] = 10 - n%10
n = n//10
ans = min(p[0], p[1] + 1)
for _ in range(10**6+1):
  if n <= 0:break
  now[0] = min(p[0] + n%10, p[1] + n%10 + 1)
  now[1] = min(p[0] + 10 - n%10, p[1] + 9 - n%10)
  ans = min(now[0], now[1] + 1)
  n = n//10
  p[0],p[1] = now[0],now[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 0
p = [0,0]
now = [0,0]
p[0] = n%10
p[1] = 10 - n%10
n = n//10
ans = min(p[0], p[1] + 1)
for _ in range(10**6+1):
  if n <= 0:break
  now[0] = min(p[0] + n%10, p[1] + n%10 + 1)
  now[1] = min(p[0] + 10 - n%10, p[1] + 9 - n%10)
  ans = min(now[0], now[1] + 1)
  n = n//10
  p[0],p[1] = now[0],now[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = 0
p = [0,0]
now = [0,0]
p[0] = n%10
p[1] = 10 - n%10
n = n//10
ans = min(p[0], p[1] + 1)
while n > 0:
  now[0] = min(p[0] + n%10, p[1] + n%10 + 1)
  now[1] = min(p[0] + 10 - n%10, p[1] + 9 - n%10)
  ans = min(now[0], now[1] + 1)
  n = n//10
  p[0],p[1] = now[0],now[1]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(str(input()))
    s.reverse()
    s = [int(c) for c in s]
    s += [0]
    m = len(s)
 
    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり
 
    dp[0][0] = 0
 
    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s = [int(c) for c in s]
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s += ['0']
    s = [int(c) for c in s]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s += ['0']
    s = [int(c) for c in s]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            for a in (0, nd):
                ni = i+1
                nj = 0
                b = a-nd
                if b < 0:
                    nj = 1
                    b += 10
                if dp[ni][nj] >= dp[i][j]+a+b:
                    dp[ni][nj] = dp[i][j]+a+b
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s += ['0']
    s = [int(c) for c in s]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            for a in range(10):
                ni = i+1
                nj = 0
                b = a-nd
                if b < 0:
                    nj = 1
                    b += 10
                if dp[ni][nj] >= dp[i][j]+a+b:
                    dp[ni][nj] = dp[i][j]+a+b
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s += ['0']
    s = [int(c) for c in s]
    m = len(s)

    dp = [[10**18, 10**18] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            for a in range(10):
                ni = i+1
                nj = 0
                b = a-nd
                if b < 0:
                    nj = 1
                    b += 10
                if dp[ni][nj] >= dp[i][j]+a+b:
                    dp[ni][nj] = dp[i][j]+a+b
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(str(n))
s.reverse()
s += ['0']
s = [int(c) for c in s]
m = len(s)

dp = [[10**18, 10**18] for _ in range(len(s)+5)]
# dp[i][0]: 繰り下がりなし
# dp[i][1]: 繰り下がりあり

dp[0][0] = 0

for i in range(m):
    for j in range(2):
        nd = s[i]
        if j == 1:
            nd += 1
        for a in range(10):
            ni = i+1
            nj = 0
            b = a-nd
            if b < 0:
                nj = 1
                b += 10
            dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b)
#print(dp)
print(dp[m][0])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    sN = str(N)
    nl = [int(i) for i in sN]
    nl.reverse()

    ret = 0
    b = nl[0]
    fin = len(nl) - 1
    for i in range(len(nl)):
        if i != fin:
            a = b
            b = nl[i + 1]
            if a >= 10:  # 繰り上がり処理
                a -= 10
                b += 1

            if a <= 4:
                ret += a  # その桁が4以下ならちょうど払う

            if a == 5:  # 1つ上の桁次第
                if b >= 5:
                    b += 1
                    ret += 5
                else:
                    ret += 5

            if a >= 6:  # 1つ上の桁の金で払う
                b += 1
                ret += (10 - a)

        else:
            if b <= 5:
                ret += b
                return ret
            if b >= 6:
                ret += 1 + (10 - b)
                return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    sN = str(N)
    nl = list(map(int, sN))
    nl.reverse()

    ret = 0
    b = nl[0]
    fin = len(nl) - 1
    for i in range(len(nl)):
        if i != fin:
            a = b
            b = nl[i + 1]
            if a >= 10:  # 繰り上がり処理
                a -= 10
                b += 1

            if a <= 4:
                ret += a  # その桁が4以下ならちょうど払う

            if a == 5:  # 1つ上の桁次第
                if b >= 5:
                    b += 1
                    ret += 5
                else:
                    ret += 5

            if a >= 6:  # 1つ上の桁の金で払う
                b += 1
                ret += (10 - a)

        else:
            if b <= 5:
                ret += b
                return ret
            if b >= 6:
                ret += 1 + (10 - b)
                return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    sN = str(N)
    nl = list(map(int, sN))
    nl.reverse()

    ret = 0
    b = nl[0]
    for i in range(len(nl)):
        is_final = False
        if i == len(nl) - 1:
            is_final = True

        if not is_final:
            a = b
            b = nl[i + 1]
            if a >= 10:  # 繰り上がり処理
                a -= 10
                b += 1

            if a <= 4:
                ret += a  # その桁が4以下ならちょうど払う

            if a == 5:  # 1つ上の桁次第
                if b >= 5:
                    b += 1
                    ret += 5
                else:
                    ret += 5

            if a >= 6:  # 1つ上の桁の金で払う
                b += 1
                ret += (10 - a)

        if is_final:
            if b <= 5:
                ret += b
                return ret
            if b >= 6:
                ret += 1 + (10 - b)
                return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret



def main():
    r = solve()
    print(r)


def solve():
    N = iip(False)
    sN = str(N)
    nl = list(map(int, sN))
    nl.reverse()

    ret = 0
    for i in range(len(nl)):
        is_final = False
        if i == len(nl) -1:
            is_final = True

        a = nl[i]
        if not is_final:
            if a >= 10: # 繰り上がり処理
                a -= 10
                nl[i+1] += 1

            if a <= 4:
                ret += a # その桁が4以下ならちょうど払う

            if a == 5: # 1つ上の桁次第
                if nl[i+1] >= 5:
                    nl[i+1] += 1
                    ret += 5
                else:
                    ret += 5

            if a >= 6: #1つ上の桁の金で払う
                nl[i+1] += 1
                ret += (10-a)

        if is_final:
            if a >= 10:
                ret += 1
                a -= 10
                ret += a
                return ret
            if a <= 5:
                ret += a
                return ret
            if a >= 6:
                ret += 1 + (10-a)
                return ret



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))

def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l

def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l




def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# a - n = b
# 101 - 91 = 010

INF = 1001001001
s = input()
# s = "91"
s = s[::-1]
s += "0"
# print("{}".format(s))
n = len(s)
# 漸化式
dp = []
for i in range(n+1):
    dp.append([])
    for j in range(2):
        dp[i].append(INF)
dp[0][0] = 0
for i in range(n):
    for j in range(2):
        x = ord(s[i]) - ord('0')
        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("{}".format(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    N = int(input())

    @lru_cache(None)
    def f(x):
        if 0<=x<=5:
            return x
        elif 6<=x<=9:
            return 5 - x + 6

        y = (x - x % 10) // 10
        return min(f(y) + x%10, f(y+1) + 10 - x%10)


    print(f(N))


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    t = "0" + s
    n = len(t)
    dp = [[float("inf")]*2 for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = int(t[n-i-1]) + j
            if x < 10:
                dp[i+1][0] = min(dp[i+1][0], dp[i][j] + x + 0)
            if 0 < x:
                dp[i+1][1] = min(dp[i+1][1], dp[i][j] + 10 - x)
    print(dp[n][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    s = s[::-1] + "0"
    n = len(s)
    dp = [[float("inf")]*2 for _ in range(n+1)]
    dp[0][0] = 0
    for i, c in enumerate(s):
        for j in range(2):
            x = int(c) + j
            for num in range(10):
                ni = i+1
                nj = 0
                rem = num - x
                if rem < 0:
                    nj = 1
                    rem += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num + rem)
    print(dp[n][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    s = s[::-1] + "0"
    n = len(s)
    dp = [[10**18]*2 for _ in range(2)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = int(s[i]) + j
            if x < 10:
                dp[(i+1)%2][0] = min(dp[(i+1)%2][0], dp[i%2][j] + x + 0)
            if 0 < x:
                dp[(i+1)%2][1] = min(dp[(i+1)%2][1], dp[i%2][j] + 10 - x)
        for j in range(2):
            dp[i%2][j] = 10**18
    print(dp[n%2][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[10**18]*2 for _ in range(2)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            if x < 10:
                dp[(i+1)%2][0] = min(dp[(i+1)%2][0], dp[i%2][j] + x + 0)
            if 0 < x:
                dp[(i+1)%2][1] = min(dp[(i+1)%2][1], dp[i%2][j] + 10 - x)
        for j in range(2):
            dp[i%2][j] = 10**18
    print(dp[n%2][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[float("inf")]*2 for _ in range(2)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            if x < 10:
                dp[(i+1)%2][0] = min(dp[(i+1)%2][0], dp[i%2][j] + x + 0)
            if 0 < x:
                dp[(i+1)%2][1] = min(dp[(i+1)%2][1], dp[i%2][j] + 10 - x)
        for j in range(2):
            dp[i%2][j] = float("inf")
    print(dp[n%2][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[float("inf")]*2 for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            if x < 10:
                dp[i+1][0] = min(dp[i+1][0], dp[i][j] + x + 0)
            if 0 < x:
                dp[i+1][1] = min(dp[i+1][1], dp[i][j] + 10 - x)
    print(dp[n][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input().rstrip()
    s = s[::-1]
    s += "0"
    n = len(s)
    a = [int(c) for c in s]
    dp = [[float("inf")]*2 for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(2):
            x = a[i] + j
            for num in range(10):
                ni = i+1
                nj = 0
                rem = num - x
                if rem < 0:
                    nj = 1
                    rem += 10
                dp[ni][nj] = min(dp[ni][nj], dp[i][j] + num + rem)
    print(dp[n][0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()[::-1]

l = len(s)

dp = [[0]*2 for _ in range(l)]

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

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


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