Problem:


Score : 500 points

Problem Statement

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

1 \leq N < 10^{100}

1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

19

The following 19 integers satisfy the condition:

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Sample Input 2

25
2

Sample Output 2

14

The following 14 integers satisfy the condition:

11,12,13,14,15,16,17,18,19,21,22,23,24,25

Sample Input 3

314159
2

Sample Output 3

937

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300



Sample input:
100
1


Sample output:
19

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
def zeroTrim(s):
    while s[0] == '0':
        if len(s) == 1:
            break
        s = s[1:]
    return s

N = input()
K = int(input())

def calc(N, K):
    digit = len(N)
    res = 0

    if K == 1:
        if digit > 1:
            res += (digit - 1) * 9
        res += int(N[0])
    elif K == 2:
        if digit > 2:
            res += 9 * 9 * (digit - 1) * (digit - 2) // 2
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 1)
        res += calc(zeroTrim(N[1:]), 1)
    else:
        if digit > 3:
            res += 9 * 9 * 9 * (digit - 1) * (digit - 2) * (digit - 3) // 6
        
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 2)
        res += calc(zeroTrim(N[1:]), 2)
    return res

print(calc(N, K))

Submission status: Runtime Error

Solution code:
s=input()
m=int(input())
n=len(s)
if n==1:
  print([0,int(s)][k==1])
  exit()
dp=[[[0]*2 for _ in range(m+1)] for _ in range(n)]
dp[0][0][1]=1
dp[0][1][1]=int(s[0])-1
dp[0][1][0]=1
for i in range(1,n):
  for j in range(m+1):
    if j:
      dp[i][j][1]+=9*dp[i-1][j-1][1]
      if s[i]!='0':
        dp[i][j][0]+=dp[i-1][j-1][0]
        dp[i][j][1]+=(int(s[i])-1)*dp[i-1][j-1][0]
    if s[i]=='0':dp[i][j][0]+=dp[i-1][j][0]
    dp[i][j][1]+=dp[i-1][j][1]
    if s[i]!='0':dp[i][j][1]+=dp[i-1][j][0]
print(sum(dp[-1][-1]))

Submission status: Runtime Error

Solution code:
s=input()
m=int(input())
n=len(s)
if n==1:
  print([0,int(s)][k==1])
  exit()
dp=[[[0]*2 for _ in range(m+1)] for _ in range(n)]
dp[0][0][1]=1
dp[0][1][1]=int(s[0])-1
dp[0][1][0]=1
for i in range(1,n):
  for j in range(m+1):
    if j:
      dp[i][j][1]+=9*dp[i-1][j-1][1]
      if s[i]!='0':
        dp[i][j][0]+=dp[i-1][j-1][0]
        dp[i][j][1]+=(int(s[i])-1)*dp[i-1][j-1][0]
    if s[i]=='0':dp[i][j][0]+=dp[i-1][j][0]
    dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][0]
print(sum(dp[-1][-1]))

Submission status: Runtime Error

Solution code:
N = [0] + list(map(int, input()))
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [[[0] * (K+2) for _ in range(2)] for _ in range(n)]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
    for k in range(K+1):
        if N[i] != 0:
            DP[i][0][k+1] += DP[i-1][0][k]
            DP[i][1][k] += DP[i-1][0][k]
            DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
        else:
            DP[i][0][k] += DP[i-1][0][k]
            DP[i][1][k] += DP[i-1][1][k]
            DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

Submission status: Runtime Error

Solution code:
N = [0] + list(map(int, input()))
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (K+2) for _ in range(2)] for _ in range(n)
]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
  for k in range(K+1):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

Submission status: Runtime Error

Solution code:
A = list(map(int,list(input())))
N = len(A)
K = int(input())
dp = [[[[0 for _ in range(100)]] for _ in range(2)] for _ in range(N+1)]
dp[1][0][1] = 1
for i in range(2,N+1):
    for j in range(100):
        dp[i][1][j] = dp[i-1][1][j-1]*9
        if A[i-1]==0:
            dp[i][0][j] = dp[i-1][0][j]
        else:
            dp[i][0][j] = dp[i-1][0][j-1]
            dp[i][1][j] += dp[i-1][0][j-1]*(A[i-1]-1)*(A[i-1]>1)+dp[i-1][0][j]*(A[i-1]==1)
print(dp[N][0][K]+dp[N][1][K])

Submission status: Runtime Error

Solution code:
import math

N = input()
K = int(input())

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

answer = 0
len_N = len(N)
# 最上位桁
for i in range(min(3, len(N), K)):
    if len_N > K:
        answer += combinations_count(len(N) - (i + 1), K - i) * (9 ** (K - i))
    answer += combinations_count(len(N) - (i + 1), K - (i + 1)) * (9 ** (K - (i + 1))) * max(0, int(N[i]) - 1)

print(answer + 1)

Submission status: Runtime Error

Solution code:
import math

N = input()
K = int(input())

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

answer = 0
len_N = len(N)
# 最上位桁
for i in range(min(3, len(N), K)):
    if len_N + 1 >= K:
        answer += combinations_count(len(N) - (i + 1), max(0, K - i)) * (9 ** (K - i))
    answer += combinations_count(len(N) - (i + 1), max(0, K - (i + 1))) * (9 ** (K - (i + 1))) * max(0, int(N[i]) - 1)

print(answer + 1)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
k=int(input())
a=math.log10(n)
if k==1:
    print(int((a//1)*9+n//(10**(a//1))))
elif k==2:
    if 1<=n<=10:
        print(0)
    else:
        b=a//1
        c=81*(1/2)*b*(b-1)
        d=math.log10(n%10**b)
        print(int(c+9*b*(n//10**b-1)+(d//1)*9+(n%10**b)//(10**(d//1))))
else:
    if 1<=n<=110:
        print(0)
    else:
        sumnum=0
        b=int(a//1)
        num=0
        for i in range(2,b):
            num+=math.factorial(i)//2
        sumnum+=num*729
        sumnum+=(n//10**b-1)*81*(1/2)*b*(b-1)
        if 0<=n%10**b<=10:
            print(int(sumnum))
        else:
            d=math.log10(n%10**b)
            e=d//1
            sumnum+=81*(1/2)*e*(e-1)
            f=math.log10((n%10**b)%10**e)
            print(int(sumnum+9*e*(n%10**b//10**e-1)+(f//1)*9+(n%10**b%10**e)//(10**(f//1))))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N = input()
    l = len(N)
    K = int(input())

    ans = 0
    # 最上位K桁が0の場合
    # l-K_C_K * 9^K
    if K == 1:
        ans += (l-1) * 9
    elif K == 2:
        ans += (l-1) * (l-2) * 81 // 2
    else:
        ans += (l-1) * (l-2) * (l-3) * 729 // 6

    if K == 1:
        # 最上位の数以外0
        ans += int(N[0])
    elif K == 2:
        # 最上位1桁が0ではなく,残りl-1桁中1桁だけ0以外（Nより大きくならないように注意）
        ans += int(N[0]) * (l-1) * 9 - (9 - int(N[1]))
    else:
        # 最上位1桁が0ではなく,残りl-1桁中2桁だけ0以外（Nより大きくならないように注意）
        ans += int(N[0]) * (l-1) * (l-2) * 81 // 2 - (99 - int(N[1:3]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())
ln = len(n) + 1

dp=[[[0]* (ln) for _ in range(2)] for i in range(ln)]
dp[0][0][0] = 1
for i in range(len(n)):
  for smaller in range(2):
    x = int(n[i])
    t = 9 if smaller else x
    for j in range(t+1):
      for knum in range(ln-1):
        if j == 0:
          dp[i+1][int(smaller or j < x)][knum] += dp[i][smaller][knum]
        else:
          dp[i+1][int(smaller or j < x)][knum+1] += dp[i][smaller][knum]
print(dp[-1][0][k]+dp[-1][1][k])

Submission status: Runtime Error

Solution code:
N=int(input())
strN = str(N)
K=int(input())
d = len(strN)

# define functions to simplify
def N_(i):
  return int(strN[i])

# n choose 2 or 3
def C2(n):
  return n*(n-1)//2

def C3(n):
  return n*(n-1)*(n-2)//6

# 0ではない桁が先頭に並ぶ場合、並ばない場合等に場合分け。
if K==1:
  print(int(strN[0]) + 9*(d-1))
elif K == 2:
  sum1 = N_(1) + (N_(0)-1)*9 + N_(0)*9*(d-2)
  sum2 = 9*9*C2(d-1)
  print(sum1+sum2)
else:
  sum1 = (N_(0)-1)*9*9*(d-2) + (N_(1)-1)*9*(d-2) + N_(2) + 9*(d-3)
  sum2 = N_(0)*9*9*C2(d-2)
  sum3 = 9*9*9*C3(d-1)
  print(sum1+sum2+sum3)

Submission status: Runtime Error

Solution code:
n= int(input())
k= input()
ans = 0
L = [0]*(n+1)

for i in range(1,n+1):
    f = str(i)
    e = list(f)
    b = len(e) - e.count('0')
    L[i] = b
print(L.count(int(k)))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
K = int(input())

def calk1(n):
    m = int(math.log10(n))
    num = m * 9
    num += n//(10**m)
    return num

def calk2(n):
    m = int(math.log10(n))
    num = m * (m - 1) // 2 * 9**2
    num += (n//(10**m)-1) * m * 9
    num += calk1(n - (n//(10**m)*10**m))
    return num

def calk3(n):
    m = int(math.log10(n))
    num = m * (m - 1) * (m - 2) // 6 * 9**3
    num += (n//(10**m)-1) * (m * (m - 1) // 2 * 9**2)
    num += calk2(n - (n//(10**m)*10**m))
    return num
if n < 10 ** (K - 1): print(0)
else:
    if K == 1: print(calk1(n))
    elif K == 2: print(calk2(n))
    else: print(calk3(n))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
K = int(input())

def calk1(n):
    m = int(math.log10(n))
    num = m * 9
    num += n//(10**m)
    return num

def calk2(n):
    m = int(math.log10(n))
    num = m * (m - 1) // 2 * 9**2
    num += (n//(10**m)-1) * m * 9
    num += calk1(n - (n//(10**m)*10**m))
    return num

def calk3(n):
    m = int(math.log10(n))
    num = m * (m - 1) * (m - 2) // 6 * 9**3
    num += (n//(10**m)-1) * (m * (m - 1) // 2 * 9**2)
    num += calk2(n - (n//(10**m)*10**m))
    return num
    
if K == 1: print(calk1(n))
elif K == 2: print(calk2(n))
else: print(calk3(n))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

n = input()
k = int(input())

dl = [[None] * (len(n) + 1) for _ in range(len(n) + 1)]
de = [[None] * (len(n) + 1) for _ in range(len(n) + 1)]


def n_num_e(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        if i == 0:
            return 1
        else:
            return 0
    elif de[d][i] is not None:
        return de[d][i]
    else:
        if int(n[d - 1]) == 0:
            result = n_num_e(d - 1, i)
        else:
            result = n_num_e(d - 1, i - 1)
        de[d][i] = result
        return result


def n_num_l(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        return 0
    elif dl[d][i] is not None:
        return dl[d][i]
    else:
        if int(n[d - 1]) == 0:
            ne = 0
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl
        else:
            ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl

        dl[d][i] = result
        return result


answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())

dl = [[None] * (len(n) + 1) for _ in range(len(n) + 1)]
de = [[None] * (len(n) + 1) for _ in range(len(n) + 1)]


def n_num_e(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        if i == 0:
            return 1
        else:
            return 0
    elif de[d][i] is not None:
        return de[d][i]
    else:
        if int(n[d - 1]) == 0:
            result = n_num_e(d - 1, i)
        else:
            result = n_num_e(d - 1, i - 1)
        de[d][i] = result
        return result


def n_num_l(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        return 0
    elif dl[d][i] is not None:
        return dl[d][i]
    else:
        if int(n[d - 1]) == 0:
            ne = 0
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl
        else:
            ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl

        dl[d][i] = result
        return result


answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())
@lru_cache(None)
def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))

Submission status: Runtime Error

Solution code:
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])

Submission status: Runtime Error

Solution code:
n=input()
k=int(input())
l=len(n)

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

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

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=n[i]
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])

Submission status: Runtime Error

Solution code:
n=input()
k=int(input())
l=len(n)

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

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

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=n[i]
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
print(dp[l-1][k][0]+dp[l-1][k][1])

Submission status: Runtime Error

Solution code:
n=input()
k=int(input())
l=len(n)
dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
for i in range(1,L):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now=0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=dp[b][j][1]*9
  dp[i][1][1]+=9
print(dp[l-1][k][0]+dp[l-1][k][1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N = int(input())
K = int(input())
DP = [[0] * (K * 10) for _ in range(N * 10)]

@lru_cache(None)
def calc(a, b):
    if a < 10:
        if b == 0:
            return 1
        if b == 1:
            return a
        else:
            return 0
    if DP[a][b] != 0:
        return DP[a][b]
    x = a % 10
    if b >= 1:
        ans = x * calc(a // 10, b - 1) + (9 - x) * calc(a // 10 - 1, b - 1)
    ans += calc(a//10, b)
    DP[a][b] = ans
    return ans

print(calc(N, K))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    s = input()
    K= int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    keta=len(s)
    dp=[[[0,0] for _ in range(keta+1)] for _ in range(keta+1)]
    #dp[i][j][k]前からi桁目まで決め、j個の条件を満たす桁を含み、k=1:i文字目まで一致 k=0:対象の数以下

    dp[0][0][0]=1
    for i in range(0,keta):
        ni=i+1
        nd=int(s[i])
        for j in range(0,keta):
            for k in range(0,2):  
                for d in range(10): 
                    nj=j
                    nk=k
                    if d!=0:nj+=1
                    if k==0:
                        if d>nd:break
                        if d<nd:nk=1
                    dp[ni][nj][nk]+=dp[i][j][k]

    ans=dp[keta][K][1]+dp[keta][K][0]
        #与えられた数未満で条件を満たすもの+与えられた数が条件を満たす場合1
    print(ans)
    #print(dp)


    
    

        
    



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    s = input()
    K= int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    keta=len(s)
    dp=[[[0,0] for _ in range(keta+1)] for _ in range(keta+1)]
    #dp[i][j][k]前からi桁目まで決め、j個の条件を満たす桁を含み、k=1:i文字目まで一致 k=0:対象の数以下

    dp[0][0][0]=1
    for i in range(0,keta):
        ni=i+1
        nd=int(s[i])
        for j in range(0,keta):
            for k in range(0,2):
                nj=j
                nk=k
                for d in range(10): 
                    if d!=0:nj+=1
                    if k==0:
                        if d>nd:break
                        if d<nd:nk=1
                    dp[ni][nj][nk]+=dp[i][j][k]

    ans=dp[keta][K][0]+dp[keta][K][0]
        #与えられた数未満で条件を満たすもの+与えられた数
    print(ans)



    
    

        
    



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
S = input()
k = int(input())

n = len(S)
S0 = int(S[0])
if k == 1:
    print(9*(n-1) + S0)
elif k == 2:
    x = sum(x for x in range(1, n-1))
    for i in range(1, n):
        if S[i] != '0':
            break
    Si = int(S[i])
    print(x*81 + (S0-1)*(n-1)*9 + (n-1-i)*9 + Si)
else:
    exit(1)

Submission status: Runtime Error

Solution code:
S = input()
k = int(input())
n = len(S)

S0 = int(S[0])
if k == 1:
  print(9*(n-1) + S0)
elif k == 2:
  exit(1)
  S1 = int(S[1])
  s = sum(x for x in range(1, n-1))
  print(s*81 + (S0-1)*(n-1)*9 + (n-2)*9 + S1)
else:
  exit(1)

Submission status: Runtime Error

Solution code:
S = input()
k = int(input())
n = len(S)

S0 = int(S[0])
if k == 1:
  print(9*(n-1) + S0)
elif k == 2:
  S1 = int(S[1])
  s = sum(x for x in range(1, n-1))
  print(s*81 + (S0-1)*(n-1)*9 + (n-2)*9 + S1)
else:
  exit(1)

Submission status: Runtime Error

Solution code:
import functools
N = int(input())
K = int(input())

@functools.lru_cache(user_function)
def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

Submission status: Runtime Error

Solution code:
import functiontool
N = int(input())
K = int(input())

@functools.lru_cache(user_function)
def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

Submission status: Runtime Error

Solution code:

N = int(input())
K = int(input())

@lru_cache
def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from scipy.special import comb
sys.setrecursionlimit(10**4)


def f(S, i, k):
    # ここに来るのは繰り下がりが発生していない状態...
    if k == 0:
        # 以降は0を選び続けるしかない
        return 1
    if len(S) <= i:
        # 走破したのにK個使いきれていない
        return 0
    n = int(S[i])
    if n == 0:
        # 注目する桁が0の場合、0を選ぶしかない
        return f(S, i+1, k)
    # 注目する桁の数値nより小さい値を選べば、以降は繰り下げで選び放題
    ret = (n - 1) * comb(len(S)-i-1, k-1, exact=True) * pow(9, k-1)
    ret += comb(len(S)-i-1, k, exact=True) * pow(9, k)
    # 注目する桁の数値nを選んだ場合、繰り下げができない状態が続行    
    ret += f(S, i+1, k-1)
    return ret

def solve(S: str, K: int):
    return f(S, 0, K)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    print(solve(N, K))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from scipy.special import comb

def f(S, i, k):
    # ここに来るのは繰り下がりが発生していない状態...
    if k == 0:
        # 以降は0を選び続けるしかない
        return 1
    if len(S) <= i:
        # 走破したのにK個使いきれていない
        return 0
    n = int(S[i])
    if n == 0:
        # 注目する桁が0の場合、0を選ぶしかない
        return f(S, i+1, k)
    # 注目する桁の数値nより小さい値を選べば、以降は繰り下げで選び放題
    ret = (n - 1) * comb(len(S)-i-1, k-1, exact=True) * pow(9, k-1)
    ret += comb(len(S)-i-1, k, exact=True) * pow(9, k)
    # 注目する桁の数値nを選んだ場合、繰り下げができない状態が続行    
    ret += f(S, i+1, k-1)
    return ret

def solve(S: str, K: int):
    return f(S, 0, K)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    print(solve(N, K))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
typedef long long int lld;
typedef unsigned long long int llu;
#define INF (lld)(9223372036854775807)
#define IINF (int)(2147483647)

using namespace std;

vector<lld> v;
lld l, k;

lld f(lld d, lld c, bool m) {
  if (l == d) {
    return c == 0;
  }
  lld s = f(d + 1, c, m && v[d] == 0);
  if (c == 0) {
    return s;
  }
  if (m) {
    if (v[d] == 0) {
      return s;
    }
    return s + (v[d] - 1) * f(d + 1, c - 1, false) + f(d + 1, c - 1, true);
  } else {
    return s + 9 * f(d + 1, c - 1, false);
  }
}

int main(void) {
  string n;
  cin >> n >> k;
  l = n.length();
  v = vector<lld>(l);
  for (lld i = 0; i < l; i++) {
    v[i] = n.c_str()[i] - '0';
  }
  cout << f(0, k, true) << "\n";
}

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())
import math
digit = math.floor(math.log10(int(n))) + 1
dp0 = [[0 for i in range(k+1)] for j in range(digit+1)]
dp1 = [[0 for i in range(k+1)] for j in range(digit+1)]

dp1[1][1] = 1
dp0[1][1] = int(n[0])-1
for i in range(1, digit+1):
    dp0[i][0] = 1

for i in range(2, digit+1):
    for j in range(1, k+1):
        num = int(n[i-1])
        if num == 0:
            dp0[i][j] = dp0[i-1][j-1]*9 + dp0[i-1][j]
            dp1[i][j] = dp1[i-1][j] 
        else:
            dp0[i][j] = dp0[i-1][j-1]*9 + dp0[i-1][j] + dp1[i-1][j-1] * (num-1) + dp1[i-1][j]
            dp1[i][j] = dp1[i-1][j-1]

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    if len(N) < K:
        print(0)

    if K == 1:
        print(N[0] + 9 * (len(N)-1))
    elif K == 2:
        count = 0
        for i in range(1, len(N)-1):
            count += 81 * i
        count += (N[0]-1) * 9 * (len(N)-1)

        count += 9 * (len(N)-2)

        count += N[1]
        print(count)
    else:
        count = 0
        for i in range(2, len(N)-1):
            count += 729 * i*(i-1)//2
        count += (N[0]-1) * 81 * (len(N)-1) * (len(N)-2) // 2

        count += 81 * (len(N)-2) * (len(N)-3) // 2

        count += (N[1]-1) * 9 * (len(N)-2)

        count += 9 * (len(N)-3)

        count += N[2]
        print(count)

main()

Submission status: Runtime Error

Solution code:
import math
import itertools

n = int(input())
k = int(input())

if (n < 99 and k == 3) or (n < 9 and k == 2):
    print(0) 

else:
    f = len(str(n))

    #f-1桁以内に収まる数

    en = 1
    for i in range(k):
        en *= f-1-i

    de = math.factorial(k)


    s = en // de * pow(9, k)

    #print(s)
    #f桁目によって絞る

    kami = int(str(n)[0])

    en_2 = 1
    for i in range(k-1):
        en_2 *= f-1-i

    de_2 = math.factorial(k-1)


    s += (en_2 // de_2 * pow(9, k-1)) * (kami-1)


    #以下上1桁は同じ数字

    keta = list(range(f-1))
    num = list(range(1,10))

    b =  kami * pow(10, f-1)
    m = 0

    if k == 1:
        s += 1
    elif k == 2:
        s += 9*(f-2) + int(str(n)[1])
    else:
        kami2 = int(str(n)[1])

        en_3 = (f-2)*(f-3)

        de_3 = 2


        s += (en_3 // de_3 * pow(9, k-1))  + kami2 * 9 * (f-2)

    print(s)

Submission status: Runtime Error

Solution code:
import math
import itertools

n = int(input())
k = int(input())

f = len(str(n))

#f-1桁以内に収まる数

en = 1
for i in range(k):
    en *= f-1-i

de = math.factorial(k)


s = en // de * pow(9, k)

#print(s)
#f桁目によって絞る

kami = int(str(n)[0])

en_2 = 1
for i in range(k-1):
    en_2 *= f-1-i

de_2 = math.factorial(k-1)


s += (en_2 // de_2 * pow(9, k-1)) * (kami-1)


#以下上1桁は同じ数字

keta = list(range(f-1))
num = list(range(1,10))

b =  kami * pow(10, f-1)
m = 0

if k == 1:
    s += 1
elif k == 2:
    s += 9*(f-2) + int(str(n)[1])
else:
    kami2 = int(str(n)[1])

    en_3 = (f-2)*(f-3)

    de_3 = 2


    s += (en_3 // de_3 * pow(9, k-1))  + kami2 * 9 * (f-2)

print(s)

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())
L = len(N)

dp = [[[0 for j in range(L + 1)] for i in range(L + 1)] for _ in range(2)]
dp[0][0][0] = 1

for i in range(L):
    Ni = int(N[i])
    for j in range(L):
        if Ni == 0:
            dp[0][i + 1][j + 0] += dp[0][i][j + 0] * 1
            dp[0][i + 1][j + 1] += dp[0][i][j + 0] * 0
            dp[1][i + 1][j + 0] += dp[0][i][j + 0] * 0 + dp[1][i][j + 0] * 1
            dp[1][i + 1][j + 1] += dp[0][i][j + 0] * 0 + dp[1][i][j + 0] * 9
        else:
            dp[0][i + 1][j + 0] += dp[0][i][j + 0] * 0
            dp[0][i + 1][j + 1] += dp[0][i][j + 0] * 1
            dp[1][i + 1][j + 0] += dp[0][i][j + 0] * 1 + dp[1][i][j + 0] * 1
            dp[1][i + 1][j + 1] += dp[0][i][j + 0] * (Ni - 1) + dp[1][i][j + 0] * 9
#print(dp[0])
#print(dp[1])

print(dp[0][L][K] + dp[1][L][K])