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

Solution (Python):
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K+1) for _ in range(2)] for _ in range(m+1)]
dp[0][0][0] = 1

for i in range(1, m+1):
    l = int(N[i-1])
    for k in range(K+1):
        dp[i][1][k] += dp[i-1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]
        else:
            dp[i][0][k] += dp[i-1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i-1][1][k-1]
            if l != 0:
                dp[i][0][k] += dp[i-1][0][k-1]
                dp[i][1][k] += (l - 1) * dp[i-1][0][k-1]
print(dp[m][0][K] + dp[m][1][K])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def main():
    n = input().rstrip()
    k = int(input())
    dp = [[[0 for equal_n      in range(2)]
              for cnt_not_zero in range(k + 1)]
              for digit        in range(len(n) + 1)]
    dp[0][0][1] = 1
    for digit in range(len(n)):
        for cnt_not_zero in range(k+1):
            for equal_n in reversed(range(2)):
                std_val = int(n[digit])
                for target_val in range(10):
                    target_digit = digit + 1
                    target_cnt_not_zero = cnt_not_zero
                    if target_val != 0:
                        target_cnt_not_zero += 1
                    if target_cnt_not_zero > k:
                        continue
                    target_equal_n = equal_n
                    if equal_n == 1:
                        if target_val > std_val:
                            continue
                        if target_val < std_val:
                            target_equal_n = 0
                    dp[target_digit][target_cnt_not_zero][target_equal_n] += dp[digit][cnt_not_zero][equal_n]
    print(dp[len(n)][k][1] + dp[len(n)][k][0])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def main():
    n = input().rstrip()
    k = int(input())
    dp = [[[0 for l in range(2)] for j in range(k + 1)] for i in range(len(n) + 1)]
    dp[0][0][0] = 1
    for i in range(len(n)):
        for j in range(k+1):
            for l in range(2):
                x = int(n[i])
                for d in range(10):
                    n_i = i+1
                    n_j = j
                    n_l = l
                    if d != 0:
                        n_j += 1
                    if n_j > k:
                        continue
                    if l == 0:
                        if d > x:
                            continue
                        if d < x:
                            n_l = 1
                    dp[n_i][n_j][n_l] += dp[i][j][l]
    print(dp[len(n)][k][0] + dp[len(n)][k][1])

if __name__ == '__main__':
    main()

Solution (Python):
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if d != 0:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Solution (Python):
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if d != 0:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Solution (Python):
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if d != 0:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines





from functools import lru_cache

def main():
	n=int(input())
	k=int(input())
	
	@lru_cache(None)
	def f(n,k):
		if n<10:
			if k==0:
				return 1
			if k==1:
				return n
			return 0
		q, r = divmod(n, 10)
		ret = 0
		if k>=1:
			ret+=f(q,k-1)*r
			ret+=f(q-1,k-1)*(9-r)
		ret+=f(q,k)
		return ret
	print(f(n,k))
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines





from functools import lru_cache

def main():
	n=int(input())
	k=int(input())
	
	@lru_cache(None)
	def f(n,k):
		if n<10:
			if k==0:
				return 1
			if k==1:
				return n
			return 0
		q, r = divmod(n, 10)
		ret = 0
		if k>=1:
			ret+=f(q,k-1)*r
			ret+=f(q-1,k-1)*(9-r)
		ret+=f(q,k)
		return ret
	print(f(n,k))
	
if __name__ == "__main__":
	main()

Solution (Python):
s = input()
k = int(input())
n = len(s)
dp = [[[0] * (k + 1) for i in range(2)] for i in range(n + 1)]
dp[0][0][0] = 1


for i in range(n):
    for j in range(2):
        for l in range(k + 1): 
            c = int(s[i])
            if j == 1:  
                dp[i + 1][j][l] += dp[i][j][l]  
                if l < k:  
                    dp[i + 1][j][l + 1] += dp[i][j][l] * 9  
            else:  
                if c == 0:
                    
                    dp[i + 1][0][l] += dp[i][j][l]
                else:
                    dp[i + 1][1][l] += dp[i][j][l]  
                    if l < k: 
                        dp[i + 1][1][l + 1] += dp[i][j][l] * \
                            (c - 1)  
                        dp[i + 1][0][l + 1] += dp[i][j][l]  
print(dp[n][1][k]+dp[n][0][k])

Solution (Python):
from itertools import product
n = input()
k = int(input())
dp = [[[0] * (k + 2) for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0][0] = 1
for i, j, l in product(range(len(n)), range(2), range(k + 1)):
    for x in range(10):
        if j == 0 and x > int(n[i]):
            continue
        dp[i + 1][0 if j == 0 and x == int(n[i]) else 1][l + 1 if x != 0 else l] += dp[i][j][l]
print(dp[len(n)][0][k] + dp[len(n)][1][k])

Solution (Python):
S = str(input())
K = int(input())
dp = [[[0, 0] for _ in range(4)] for _ in range(105)]
dp[0][0][0] = 1




for i in range(len(S)):
	nxt_d = int(S[i])
	for j in range(4):
		for k in range(2):
			
			for d in range(10):
				nxt_i = i + 1
				nxt_j = j
				nxt_k = k
				if d != 0: 
					nxt_j += 1
				if nxt_j > K: 
					continue
				if k == 0: 
					if d > nxt_d: continue
					if d < nxt_d: nxt_k = 1
				dp[nxt_i][nxt_j][nxt_k] += dp[i][j][k]
ans = dp[len(S)][K][0] + dp[len(S)][K][1]

print(ans)

Solution (Python):
n = int(input())
N = len(str(n))
k = int(input())
s = [int(i) for i in str(n)]
dpi = [[0]*(k+1) for _ in range(N+1)]
dpj = [[0]*(k+1) for _ in range(N+1)]
dpi[0][0] = 1
for i in range(N):
    for j in range(k+1):
        dpi[i+1][j] += dpi[i][j]*(s[i]==0)
        dpj[i+1][j] += dpj[i][j]+dpi[i][j]*(s[i]>0)
        if j < k:
            dpi[i+1][j+1]+=dpi[i][j]*(s[i]>0)
            dpj[i+1][j+1]+=dpj[i][j]*9+dpi[i][j]*max(0,s[i]-1)
print(dpi[N][k]+dpj[N][k])

Solution (Python):
import sys
import math
import itertools

nums = list(map(int, list(input())))
k = int(input())

dp0 = [[0 for _ in range(3)] for _ in range(len(nums))]
dp1 = [[0 for _ in range(3)] for _ in range(len(nums))]

dp0[0][0] = nums[0] - 1
dp1[0][0] = 1

for i in range(1, len(nums)):
	if nums[i] > 0:
		dp0[i][0] = dp0[i - 1][0] + dp1[i - 1][0] + 9
		dp0[i][1] = dp0[i - 1][1] + dp1[i - 1][1] + dp0[i - 1][0] * 9 + dp1[i - 1][0] * (nums[i] - 1)
		dp0[i][2] = dp0[i - 1][2] + dp1[i - 1][2] + dp0[i - 1][1] * 9 + dp1[i - 1][1] * (nums[i] - 1)
		dp1[i][0] = 0
		dp1[i][1] = dp1[i - 1][0] 
		dp1[i][2] = dp1[i - 1][1]
	else:
		dp0[i][0] = dp0[i - 1][0] + 9
		dp0[i][1] = dp0[i - 1][1] + dp0[i - 1][0] * 9
		dp0[i][2] = dp0[i - 1][2] + dp0[i - 1][1] * 9
		dp1[i][0] = dp1[i - 1][0] 
		dp1[i][1] = dp1[i - 1][1] 
		dp1[i][2] = dp1[i - 1][2]


print(dp0[-1][k-1] + dp1[-1][k-1])

Solution (Python):

s = input()


not_zero = int(input())


n = len(s)





dp = [[[0] * 4 for i in range(2)] for j in range(105)]


dp[0][0][0] = 1

for i in range(n):
    for j in range(2):
        for k in range(4):
            nd = int(s[i])
            for d in range(10):
                
                ni = i + 1
                nj = j
                nk = k

                
                if d != 0:
                    nk += 1
                
                if nk > not_zero:
                    continue
                
                if j == 0:
                    
                    if d > nd:
                        continue
                    
                    if d < nd:
                        nj = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Solution (Python):
n_str = input()
k = int(input())

def k1(n_str):
	n_str = str(int(n_str))
	n_len = len(n_str)
	return 9*(n_len-1) + int(n_str[0])

def k2(n_str):
    s = 0
    n_str = str(int(n_str))
    n_len = len(n_str)
    if n_len < 2:
        return 0
    s += k2('9'*(n_len - 1))
    s += k1('9'*(n_len - 1)) * (int(n_str[0]) - 1)
    s += k1(n_str[1:])
    return s
                      
def k3(n_str):
    s = 0
    n_str = str(int(n_str))
    n_len = len(n_str)
    if n_len < 3:
        return 0
    s += k3('9'*(n_len - 1))
    s += k2('9'*(n_len - 1)) * (int(n_str[0]) - 1)
    s += k2(n_str[1:])
    return s

if k == 1:
    print(k1(n_str))
elif k == 2:
    print(k2(n_str))
elif k == 3:
    print(k3(n_str))

Solution (Python):
import math

N=input().replace('\n','')
K=int(input().replace('\n',''))

def C(n,k):
    return (math.factorial(n)//math.factorial(n-k))//math.factorial(k)

def calc(n,k):
    if n<k or k<0:
        return 0
    return (9**k)*C(n,k)

s=0
l=len(N)
counter=0
for i,num in enumerate(N):
    if (K-counter)==0:
        s+=1
        break
    if int(num)==0:
        continue
    if i==l-1:
        s+=(int(num))*calc(l-i-1,K-counter-1)
    else:
        s+=(int(num)-1)*calc(l-i-1,K-counter-1)
    s+=calc(l-i-1,K-counter)
    counter+=1

print(s)

Solution (Python):
n = int(input())
N = len(str(n))
k = int(input())
s = [int(i) for i in str(n)]
dpi = [[0]*(k+1) for _ in range(N+1)]
dpj = [[0]*(k+1) for _ in range(N+1)]
dpi[0][0] = 1
for i in range(N):
    for j in range(k+1):
        dpi[i+1][j] += dpi[i][j]*(s[i]==0)
        dpj[i+1][j] += dpj[i][j]+dpi[i][j]*(s[i]>0)
        if j < k:
            dpi[i+1][j+1]+=dpi[i][j]*(s[i]>0)
            dpj[i+1][j+1]+=dpj[i][j]*9+dpi[i][j]*max(0,s[i]-1)
print(dpi[N][k]+dpj[N][k])

Solution (Python):
from itertools import product

dp = [[[0 for k in range(2)] for j in range(5)] for i in range(105)]

s = input()
n = len(s)
K = int(input())




dp[0][0][0] = 1

for i, j, k in product(range(n), range(0,4),(0,1)):
  nd=int(s[i])

  for d in range(0,10):
    ni,nj,nk=i+1,j,k
    
    if d!=0:
      nj+=1
    
    if nj>K:
      continue
    
    if k==0:
    
      if d>nd:
        continue
    
      elif d<nd:
        nk=1

    dp[ni][nj][nk]+=dp[i][j][k]

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

Solution (Python):
n=input()
keta=len(n)
k=int(input())


dp=[[[0]*2 for _ in range(4)] for _ in range(keta +1 )]
dp[0][0][0]=1
for i in range(keta):
    for j in range(4):
        for smaller in range(2):
            nd = int(n[i]) 
            for d in range(10):
                
                ni=i+1
                nj=j
                nsmaller=smaller
                
                
                
                if d!=0:
                    nj+=1
                if nj > k:
                    continue  
                
                if smaller ==0:  
                    if d > nd:
                        continue
                    if d <nd:
                        nsmaller=1
                
                dp[ni][nj][nsmaller]+=dp[i][j][smaller]
ans = dp[keta][k][0]+dp[keta][k][1]
print(ans)

Solution (Python):
n = input()
k = int(input())
dp0 = [0] * 4
dp1 = [1,0,0,0]
for i in n:
  i = int(i)
  pdp0,pdp1,dp0 = dp0,dp1,[0]*4
  if i != 0:
    dp1 = [0] + pdp1[:-1]
  else:
    dp1 = pdp1
  dp0[0] = pdp0[0]+(i!=0)*pdp1[0]
  for j in range(1,4):
    dp0[j] = 9*pdp0[j-1] + pdp0[j] + (i!=0)*(i-1)*pdp1[j-1] + (i!=0)*pdp1[j]
print(dp0[k]+dp1[k])

Solution (Python):
N = int(input())
K = int(input())
memo = {}

def F(N, K):
    """
    F(N, K) = (1以上N以下で0でない桁がちょうどK個なものの個数)
    Nを一の桁から見ていくことで再帰で求める
    （例）F(314,3) = F(31,2)*4 + F(30,2)*5 + F(31,3)
                      = {F(3,1) + F(2,1)*8 + F(3,2)} * 4
                            + {F(2,1)*9 + F(3,2)} * 5
                            + {F(3,2) + F(2,2)*8 + F(3,3)}
                      = ...
    """
    r = int(str(N)[-1])
    M = (N - r) // 10
    if K == 0 and N >= 0:
        return 1
    elif K == 0 and N <= -1:
        return 0
    elif N <= 0:
        return 0
    else:
        return F(M, K-1) * r + F(M-1, K-1) * (9-r) + F(M, K)

print(F(N, K))

Solution (Python):
from collections import defaultdict
from functools import lru_cache

N = input().strip()
K = int(input().strip())
lenN = len(N)


@lru_cache(maxsize=None)
def f(keta, flag, k):
    if keta == lenN-1:
        if k == K:
            return 1
        else:
            return 0
    
    
    nketa = keta + 1
    maxi = int(N[nketa]) if flag else 9
    res = 0
    for i in range(maxi+1):
        nflag = flag and (int(N[nketa]) == i)
        nk = k if i == 0 else k + 1
        if nk > K:
            continue
        res += f(nketa, nflag, nk)
    
    return res

print(f(-1, True, 0))

Solution (Python):
from collections import defaultdict

N = input().strip()
K = int(input().strip())
lenN = len(N)

memo = defaultdict(lambda :defaultdict(lambda :defaultdict(int)))
def f(keta, flag, k):
    if keta == lenN-1:
        if k == K:
            return 1
        else:
            return 0
    if keta in memo and flag in memo[keta] and k in memo[keta][flag]:
        return memo[keta][flag][k]
    nketa = keta + 1
    maxi = int(N[nketa]) if flag else 9
    res = 0
    for i in range(maxi+1):
        nflag = flag and (int(N[nketa]) == i)
        nk = k if i == 0 else k + 1
        if nk > K:
            continue
        res += f(nketa, nflag, nk)
    memo[keta][flag][k] = res
    return res

print(f(-1, True, 0))

Solution (Python):
import numpy as np

N = input().strip()
K = int(input().strip())
lenN = len(N)

dp = np.zeros((lenN+1, 2, 4))
dp[0][1][0] = 1
for keta in range(lenN):
    for flag in range(2):
        for k in range(K+1):
            for i in range(10):
                nk = k
                nflag = flag
                if flag:
                    if i > int(N[keta]):
                        continue
                    if i < int(N[keta]):
                        nflag = 0
                if i != 0:
                    nk = k + 1
                if nk > K:
                    continue
                dp[keta+1][nflag][nk]+=dp[keta][flag][k]

print(int(dp[lenN][0][K] + dp[lenN][1][K]))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def combinations(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return combinations(n-1,r-1) + combinations(n-1,r)

def main():
    n = input().rstrip()
    k = int(input())
    if k == 1:
        print((int(n[0]) - 1) + 9 * (len(n) -  1) + 1)
    elif k == 2:
        a = (int(n[0]) - 1) * 9 * (len(n) - 1)
        b = int(combinations(len(n) - 1, 2) * 9*9)
        c = 0
        for i in range(1, len(n)):
            if n[i] != '0':
                c = int(n[i]) + 9 * (max(len(n) - i - 1, 0))
                break
        print(a + b + c)
    elif k == 3:
        a_a = 0
        a_b = 0
        a_c = 0
        for i in range(1, len(n)):
            if n[i] != '0':
                for j in range(i+1, len(n)):
                    if n[j] != '0':
                        a_a = int(n[j]) + 9 * (max(len(n) - j - 1, 0))
                        break
                a_b = (int(n[i]) - 1) * 9 * (max(len(n) - i - 1, 0))
                a_c = combinations(len(n) - i - 1, 2) * 9 * 9
                break
        b = (int(n[0]) - 1) * combinations(len(n) - 1, 2) * 9 * 9
        c = combinations(len(n) - 1, 3) * 9 * 9 * 9
        print((a_a + a_b + a_c) + b + c)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

N = input().strip()
K = int(input().strip())
lenN = len(N)

memo = defaultdict(lambda :defaultdict(lambda :defaultdict(int)))
def f(keta, flag, k):
    if keta == lenN-1:
        if k == K:
            return 1
        else:
            return 0
    if keta in memo and flag in memo[keta] and k in memo[keta][flag]:
        return memo[keta][flag][k]
    nketa = keta + 1
    maxi = int(N[nketa]) if flag else 9
    res = 0
    for i in range(maxi+1):
        nflag = flag and (int(N[nketa]) == i)
        nk = k if i == 0 else k + 1
        if nk > K:
            continue
        res += f(nketa, nflag, nk)
    memo[keta][flag][k] = res
    return res

print(f(-1, True, 0))

Solution (Python):



def main():
    s = list(input())
    n = len(s)
    large_k = int(input())
    
    
    
    
    
    
    dp = [[[0 for k in range(2)] for j in range(4)] for i in range(105)]
    
    dp[0][0][0] = 1

    
    
    
    
    for i in range(n):
        for j in range(4):
            for k in range(2):
                
                nd = int(s[i])

                
                for digit in range(10):
                    ni, nj, nk = i + 1, j, k

                    
                    
                    
                    if digit != 0:
                        nj += 1

                    
                    if nj > large_k:
                        continue

                    
                    if k == 0:
                        
                        if digit > nd:
                            continue
                        
                        elif digit < nd:
                            nk = 1

                    dp[ni][nj][nk] += dp[i][j][k]

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


if __name__ == '__main__':
    main()

Solution (Python):
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 1
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

n = int(input())
k = int(input())
print(solve(n,k))

Solution (Python):



def main():
    s = list(input())
    n = len(s)
    large_k = int(input())
    dp = [[[0 for k in range(2)] for j in range(4)] for i in range(105)]
    dp[0][0][0] = 1

    
    
    for i in range(n):
        for j in range(4):
            for k in range(2):
                nd = int(s[i])

                for digit in range(10):
                    ni, nj, nk = i + 1, j, k

                    if digit != 0:
                        nj += 1
                    if nj > large_k:
                        continue
                    if k == 0:
                        if digit > nd:
                            continue
                        if digit < nd:
                            nk = 1

                    dp[ni][nj][nk] += dp[i][j][k]

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


if __name__ == '__main__':
    main()

Solution (Python):



N = input()
K = int(input())
L = len(N)
"""
dp[i][j][k]：Nを頭からi桁まで見たとき、残りの使える0以外の個数がj個で、そこまでの値がNのi-1桁目までより小さい/同じ（小さいとk=1）時のi桁目までのとりうる個数
"""
dp = [[[0 for _ in range(2)] for _ in range(K+1)] for _ in range(L+1)]
dp[0][K][0] = 1

for i in range(L):
    digit = int(N[i])
    for num_rest_non_zero in range(K+1):
        for flag_less in range(2):
            """
            ・先頭はN[0]以下の値で決める
            ・もし現時点でNより小さいなら、次のi桁目は0以外の数字を使える個数に余裕があれば、
            i桁目に1~9まで使うこともできるし、0を使うこともできる
            ・既に0以外を使える個数がなくなって（使い切って）いれば、0をあてるしかない
            ・i-1桁目までがNと一致している（flag_less = 0）であれば、nのi桁目以下の値からしか選べない
            """

            
            if i == 0:
                d = digit
            elif num_rest_non_zero == 0:
                d = 0
            elif flag_less == 1:
                d = 9
            else:
                d = digit

            for num in range(d+1):
                
                if flag_less == 0 and num == digit:
                    flag_less_nxt = 0
                else:
                    flag_less_nxt = 1

                
                if num != 0:
                    dp[i+1][num_rest_non_zero-1][flag_less_nxt] += dp[i][num_rest_non_zero][flag_less]
                else:
                    
                    dp[i+1][num_rest_non_zero][flag_less_nxt] += dp[i][num_rest_non_zero][flag_less]


print(sum(dp[L][0]))

Solution (Python):
s = input()
n = len(s)
K = int(input())





dp = [[[0 for i in range(2)] for j in range(4)] for k in range(105)]



dp[0][0][1] = 1


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

res = dp[n][K][0] + dp[n][K][1]
print(res)

Solution (Python):

import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s


@lru_cache(maxsize=None)
def f(num,k):
    if(num==0 and k==0):return 1
    elif(num<=0 or k<0):return 0
    else:
        r=num-(num//10)*10
        m=num//10
        return f(m,k-1)*r+f(m-1,k-1)*(9-r)+f(m,k)
s=int(input())
k=int(input())
print(f(s,k))

Solution (Python):
n = input().strip()
k = int(input().strip())
le = len(n)
dp = [[[0] * 2 for _ in range(5)] for _ in range(101)]
dp[0][0][0] = 1

for i in range(le):
    for cnt in range(4):
        for smaller in range(2):
            fig = int(n[i])
            for d in range(10):
                tmp1 = i + 1
                tmp2 = cnt
                tmp3 = smaller
                if d != 0:
                    tmp2 += 1
                if k < cnt:
                    continue
                if smaller == 0:
                    if fig < d:
                        continue
                    elif d < fig:
                        tmp3 = 1
                dp[tmp1][tmp2][tmp3] += dp[i][cnt][smaller]
print(dp[le][k][0] + dp[le][k][1])

Solution (Python):

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


def K_is_one(n):
    p = len(str(n))
    q = int(str(n)[0])
    return q + 9*(p-1)

def K_is_two(n):
    p = len(str(n))
    q = int(str(n)[0])
    if p == 1:
        return 0
    elif p == 2:
        return n - K_is_one(n)
    else:
        r = int(str(n)[1:])
        temp = 0
        for i in range(1, p-1):
            temp += 9*K_is_one(int("9"*i))
        temp += (q-1) * K_is_one(int("9"*(p-1))) + K_is_one(r)
        return temp

def K_is_three(n):
    p = len(str(n))
    q = int(str(n)[0])
    if p == 1:
        return 0
    elif p == 2:
        return 0
    else:
        r = int(str(n)[1:])
        temp = 0
        for i in range(1, p-1):
            temp += 9*K_is_two(int("9"*i))
        temp += (q-1) * K_is_two(int("9"*(p-1))) + K_is_two(r)
        return temp

if K == 1:
    print(K_is_one(N))
elif K == 2:
    print(K_is_two(N))
else:
    print(K_is_three(N))

Solution (Python):


N = input()
K = int(input())
dp = [[[0 for _ in range(K+2)] for _ in range(2)] for _ in range(len(N) + 1)]

dp[0][0][0] = 1

for i in range(len(N)):
    for smaller in range(2):
        for k in range(K+1):
            
            for x in range(10 if smaller == 1 else int(N[i]) + 1):
                dp[i + 1][smaller == 1 or x < int(N[i])][k + 1 if x != 0 else k] += dp[i][smaller][k]
print(dp[len(N)][0][K] + dp[len(N)][1][K])

Solution (Python):


N = input()
K = int(input())
dp = [[[0 for _ in range(K+2)] for _ in range(2)] for _ in range(len(N) + 1)]

dp[0][0][0] = 1

for i in range(len(N)):
    for smaller in range(2):
        for k in range(K+1):
            for x in range(10 if smaller == 1 else int(N[i]) + 1):
                dp[i + 1][smaller == 1 or x < int(N[i])][k + 1 if x != 0 else k] += dp[i][smaller][k]
print(dp[len(N)][0][K] + dp[len(N)][1][K])

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    K=I()
    N=len(S)
    dp = [[[0]*2 for _ in range(K+1)]for _ in range(N+1)] 
    dp[0][0][0] = 1
    for i in range(N):
        for count_not_zero in range(K+1):
            for less in range(2):
                if less:
                    upper = 10
                else:
                    upper = int(S[i])+1
                for j in range(upper):
                    try:
                        dp[i+1][count_not_zero + (j!=0)][less or (j<int(S[i]))] += dp[i][count_not_zero][less]
                    except:
                        pass
    print(sum(dp[-1][K]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
sys.setrecursionlimit(10 ** 7)




S = input()
K = int(input())
N = len(S)


dp = [[[0] * 2 for _ in range(4)] for _ in range(N + 1)]


dp[0][0][0] = 1


for i in range(N):
    for j in range(4):
        for k in range(2):
            
            d = int(S[i])

            
            for nextd in range(10):
                
                nextj = j
                nextk = k

                
                if nextd != 0:
                    nextj += 1
                
                if nextj > K:
                    continue

                
                
                if k == 0:
                    if d < nextd:
                        continue
                    elif nextd < d:
                        nextk = 1

                        
                dp[i + 1][nextj][nextk] += dp[i][j][k]


ans = dp[N][K][0] + dp[N][K][1]
print(ans)

Solution (Python):
N = int(input())
K = int(input())
L = len(str(N))
dp1 = [[0 for _ in range(K+1)] for _ in range(L+1)]
dp2 = [[0 for _ in range(K+1)] for _ in range(L+1)]
count = 0
for i in range(L+1):
    dp1[i][0] = 0
count = 0
for i, c in enumerate(str(N)):
    c = int(c)
    if i == 0:
        dp1[i+1][0] = 1
        dp1[i+1][1] = c-1
        dp2[i+1][1] = 1
        count = 1
        continue

    for j in range(0, K+1):
        if c == 0:
            dp2[i+1][j] += dp2[i][j]
        else:
            if j != K:
                dp2[i+1][j+1] += dp2[i][j]
    for j in range(0, K+1):
        if c != 0:
            dp1[i+1][j] += dp2[i][j]
        dp1[i+1][j] += dp1[i][j]


        if j != K:
            if count >= K:
                dp1[i+1][j+1] += dp2[i][j] * 9
                dp1[i+1][j+1] += dp1[i][j] * 9
            else:
                dp1[i+1][j+1] += dp2[i][j]*max(0, (c-1))
                dp1[i+1][j+1] += dp1[i][j]*9
    
    
print(dp1[-1][-1] + dp2[-1][-1])