Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
str_n = input()
n = int(str_n)
k = int(input())

def dfs(A,rest):
    if int(A) <= n and rest == 0:
        num = 1
    elif int(A) <= n:
        num = 0
    else:
        return 0

    if rest == 0:
        num += dfs(A+'0',0)
    else:
        for new in range(10):
            if new == 0:
                num += dfs(A+str(new),rest)
            else:
                num += dfs(A+str(new),rest-1)

    return num

ans = 0
for i in range(1,10):
    ans += dfs(str(i),k-1)
print(ans)
    

Fixed submission:
str_n = input()
keta = len(str_n)
not_zero = int(input())

dp = [[[0]*(not_zero+2) for _ in range(2)] for _ in range(keta+1)]
first = int(str_n[0])
dp[1][1][0] = 1
for k in range(1,10):
    if first == k:
        dp[1][0][1] += 1
    elif first > k:
        dp[1][1][1] += 1

for i in range(1,keta):
    # smallerからsmallerへの遷移
    for j in range(not_zero+1):
        # i桁目をゼロにする
        dp[i+1][1][j] += dp[i][1][j]
        # i桁目でゼロ以外を使う
        dp[i+1][1][j+1] += (dp[i][1][j])*9

    nex = int(str_n[i])
    # sameからsmallerへの遷移
    if not nex == 0:
        for j in range(not_zero+1):
            # i桁目をぜろにする
            dp[i+1][1][j] += dp[i][0][j]
            # i桁目でゼロ以外
            dp[i+1][1][j+1] += (dp[i][0][j]) * (nex-1)
    
    # sameからsameへの遷移
    if nex == 0:
        for j in range(not_zero+1):
            dp[i+1][0][j] = dp[i][0][j]
    else:
        for j in range(not_zero):
            dp[i+1][0][j+1] = dp[i][0][j]

print(dp[keta][1][not_zero] + dp[keta][0][not_zero])

Buggy python submission (verdict: Runtime Error):
import sys
from collections import Counter
H,W,m = map(int,input().split())
h_ls = [0] * H
w_ls = [0] * W
bombers = [[0,0] for _ in range(m)]
for i in range(m):
    h,w = map(int,input().split())
    h_ls[h-1] += 1
    w_ls[w-1] += 1
    bombers[i] = [h-1,w-1]

h_max = max(h_ls)
h_counter = Counter(h_ls)
# Couter使ってみる
h_max_args = [0]*h_counter[h_max]
next_ind = 0
for i in range(H):
    if h_ls[i] == h_max:
        h_max_args[next_ind] = i
        next_ind += 1

w_max = max(w_ls)
w_counter = Counter(w_ls)
w_max_args = [0]*w_counter[w_max]
next_ind = 0
for i in range(W):
    if w_ls[i] == w_max:
        w_max_args[next_ind] = i
        next_ind += 1

bombers = set(bombers)
for h in h_max_args:
    for w in w_max_args:
        if not [h,w] in bombers:
            print(w_max+h_max)
            sys.exit()

print(w_max+h_max-1)


Fixed submission:
str_n = input()
keta = len(str_n)
not_zero = int(input())

dp = [[[0]*(not_zero+2) for _ in range(2)] for _ in range(keta+1)]
first = int(str_n[0])
dp[1][1][0] = 1
for k in range(1,10):
    if first == k:
        dp[1][0][1] += 1
    elif first > k:
        dp[1][1][1] += 1

for i in range(1,keta):
    # smallerからsmallerへの遷移
    for j in range(not_zero+1):
        # i桁目をゼロにする
        dp[i+1][1][j] += dp[i][1][j]
        # i桁目でゼロ以外を使う
        dp[i+1][1][j+1] += (dp[i][1][j])*9

    nex = int(str_n[i])
    # sameからsmallerへの遷移
    if not nex == 0:
        for j in range(not_zero+1):
            # i桁目をぜろにする
            dp[i+1][1][j] += dp[i][0][j]
            # i桁目でゼロ以外
            dp[i+1][1][j+1] += (dp[i][0][j]) * (nex-1)
    
    # sameからsameへの遷移
    if nex == 0:
        for j in range(not_zero+1):
            dp[i+1][0][j] = dp[i][0][j]
    else:
        for j in range(not_zero):
            dp[i+1][0][j+1] = dp[i][0][j]

print(dp[keta][1][not_zero] + dp[keta][0][not_zero])