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()
keta=len(N)
K=int(input())
seiyaku=[[0 for a in range(120)] for b in range(keta+2)]
museiyaku=[[0 for a in range(120)] for b in range(keta+2)]
seiyaku[0][0]=1
seiyaku[0][0]=1
for i in range(keta):
 a=int(N[i])
 for j in range(keta+1):
  if a==0:
   seiyaku[i+1][j]=seiyaku[i][j]
   museiyaku[i+1][j+1]+=museiyaku[i][j]*9
   museiyaku[i+1][j]+=museiyaku[i][j]
  else:
   seiyaku[i+1][j+1]=seiyaku[i][j]
   museiyaku[i+1][j]+=seiyaku[i][j]
   museiyaku[i+1][j+1]+=seiyaku[i][j]*(a-1)
   museiyaku[i+1][j+1]+=museiyaku[i][j]*9
   museiyaku[i+1][j]+=museiyaku[i][j]
print(seiyaku[keta][K]+museiyaku[keta][K])

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

n1,n2,n3=int(n[-1]),0,0
a1,a2,a3=9,0,0
for i in n[-2::-1]:
    i=int(i)
    if i!=0:
        n1,n2,n3=i+a1,(i-1)*a1+n1+a2,(i-1)*a2+n2+a3
    a1,a2,a3=9+a1,9*a1+a2,9*a2+a3
print([n1,n2,n3][k-1])

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

n1,n2,n3=int(n[-1]),0,0
a1,a2,a3=9,0,0
for i in n[-2::-1]:
    i=int(i)
    if i!=0:
        n1,n2,n3=i+a1,(i-1)*a1+n1+a2,(i-1)*a2+n2+a3
    a1,a2,a3=9+a1,9*a1+a2,9*a2+a3
print([n1,n2,n3][k-1])

Solution (Python):






def main():
    N = input()
    K = int(input())
    L = len(N)
    
    
    
    
    dp = [[[0]*2 for j in range(K+1)] for i in range(L+1)]
    dp[0][0][0] = 1
    for i in range(L):
        n = int(N[i])
        for j in range(K+1):
            for st in range(2):
                for x in range(10):
                    i_ = i+1
                    j_ = j
                    st_ = st
                    if x != 0:
                        j_ += 1
                    if j_ > K:
                        continue
                    if st_ == 0 and x > n:
                        continue
                    if st_ == 0 and x < n:
                        st_ = 1
                    dp[i_][j_][st_] += dp[i][j][st]

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

if __name__ == '__main__':
    main()

Solution (Python):






def main():
    N = input()
    K = int(input())
    L = len(N)
    
    
    
    
    dp = [[[0]*2 for j in range(K+1)] for i in range(L+1)]
    dp[0][0][0] = 1
    for i in range(L):
        n = int(N[i])
        for j in range(K+1):

            
            dp[i+1][j][1] += dp[i][j][1]
            
            if j+1<=K:
                dp[i+1][j+1][1] += dp[i][j][1]*9


            
            if n == 0:
                
                dp[i+1][j][0] += dp[i][j][0]
            
            else:
                
                dp[i+1][j][1] += dp[i][j][0]
                
                if j+1<=K:
                    dp[i+1][j+1][1] += dp[i][j][0]*(n-1)
                
                if j+1<=K:
                    dp[i+1][j+1][0] += dp[i][j][0]



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


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n = input()
    k = int(input())

    dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(len(n) + 1)]
    dp[0][0][0] = 1
    for i in range(len(n)):
        dp[i + 1][0][1] = 1
        for j in range(k):
            if n[i] == '0':
                dp[i + 1][j + 1][0] = dp[i][j + 1][0]
                dp[i + 1][j + 1][1] = dp[i][j + 1][1] + dp[i][j][1]*9
            else:
                dp[i + 1][j + 1][0] = dp[i][j][0]
                dp[i + 1][j + 1][1] = dp[i][j + 1][0] + dp[i][j][0]*(int(n[i]) - 1) + dp[i][j + 1][1] + dp[i][j][1]*9
    print(sum(dp[-1][-1]))
if __name__ == '__main__':
    main()

Solution (Python):
n = list(map(int, list(input())))
k = int(input())

dp = [[0,0,0] for _ in range(len(n))]
counter = 0

for i in range(len(n)):
    dp[i][0] += dp[i-1][0] + 9*(counter > 0)
    dp[i][1] += dp[i-1][0]*9 + dp[i-1][1]
    dp[i][2] += dp[i-1][1]*9 + dp[i-1][2]
    if n[i] > 0:
        if counter >= 1 and counter <= 3:
            dp[i][counter-1] += 1
        counter += 1
        if counter <= 3:
            dp[i][counter-1] += n[i]-1

print(dp[len(n)-1][k-1]+(counter==k))

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

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


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])

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

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


DP[0][0][0] = 1

for i in range(1, n):
  for k in range(4):
    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])

Solution (Python):
n="0"+input()
k=int(input())
dp=[[[0]*5,[0]*5] for _ in range(len(n))]
dp[0][1][0]=1
for i in range(1,len(n)):
    x=int(n[i])
    for j in range(4):
        if dp[i-1][1][j]:
            dp[i][1][j+(x!=0)]=1
            if x>1:
                dp[i][0][j+1]+=(x-1)
                dp[i][0][j]+=1
            elif x==1:
                dp[i][0][j]+=1
        if dp[i-1][0][j]:
            dp[i][0][j]+=dp[i-1][0][j]
            dp[i][0][j+1]+=(dp[i-1][0][j]*9)
    dp[i][0][0]=1

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

Solution (Python):
def comb(n, k):
    nu, de = 1, 1
    for i in range(k):
        de *= n - i
        nu *= i + 1
    return de // nu


def ans(N, K):
    if K == 0:
        return 1
    N = str(int(N))
    if len(N) < K or int(N) == 0:
        return 0
    ret = sum([9 ** K * comb(max(dig - 1, 1), K - 1)
               for dig in range(K, len(N))])
    ret += (int(N[0]) - 1) * 9 ** (K - 1) * comb(len(N) - 1, K - 1)
    return ret + ans(N[1:], K - 1)


N = input()
K = int(input())
print(ans(N, K))

Solution (Python):
N = int(input())
K = int(input())


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def contain_one(n):
    a = 100
    max_num = 10**a

    while 1:
        if n // max_num == 0:
            a -= 1
            max_num = 10**a
        else:
            break

    return 9*a+(n//max_num)


def contain_two(n):
    if n <=10:
        return 0

    a = 100
    max_num = 10**a

    while 1:
        if n // max_num == 0:
            a -= 1
            max_num = 10**a
        else:
            break

    cnt = 0
    
    for i in range(1, a):
        cnt += 9*9*i

    
    tmp = n // max_num
    cnt += 9*a*(tmp-1)

    
    tmp = n % max_num
    
    if tmp != 0:
        cnt += contain_one(tmp)

    return cnt


def contain_three(n):
    if n <=100:
        return 0

    a = 100
    max_num = 10**a

    while 1:
        if n // max_num == 0:
            a -= 1
            max_num = 10**a
        else:
            break

    cnt = 0
    
    for i in range(2, a):
        if i == 2:
            cnt += 9**2 * 9
        else:
            
            cnt += 9**2 * 9 * cmb(i, i-2)
            
            
            
            


    tmp = n // max_num
    if a == 2:
        cnt += 9**2 * (tmp-1)
    else:
        cnt += 9**2 * (tmp-1) * cmb(a, a-2)


    tmp = n % max_num
    if tmp != 0:
        cnt += contain_two(tmp)

    return cnt


if K == 1:
    print(contain_one(N))
elif K == 2:
    print(contain_two(N))
else:
    print(contain_three(N))

Solution (Python):
s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) 
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) == 0:
    print(tasumae)
    exit()
if len(doko) == 1:
    ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + com(l-1-doko[0],2)*(9**2) + tasumae
    print(ans)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

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 j in range(k+1):
        dp[i][1][j]+=dp[i-1][1][j] 
        if l!=0:
            dp[i][1][j]+=dp[i-1][0][j]  
        else:
            dp[i][0][j]+=dp[i-1][0][j]      
        if j-1>=0:
            dp[i][1][j]+=9*dp[i-1][1][j-1]
            if l!=0:
                dp[i][0][j]+=dp[i-1][0][j-1]
                dp[i][1][j]+=(l-1)*dp[i-1][0][j-1]
print(dp[m][0][k]+dp[m][1][k])

Solution (Python):
import sys


def main():
    N = input()
    K = int(input())
    
    dp = [[0]*4 for _ in range(2)]
    dp[1][0] = 1
    
    for st in N:
        num = int(st)
        use = [[0]*4 for _ in range(2)]
        if num == 0:
            for i in range(4):
                use[0][i] += dp[0][i]
                use[1][i] += dp[1][i]
                if i != 3:
                    use[0][i+1] += dp[0][i]*9
        else:
            for i in range(4):
                use[0][i] += dp[0][i]+dp[1][i]
                if i != 3:
                    use[1][i+1] += dp[1][i]
                    use[0][i+1] += dp[0][i]*9
                    use[0][i+1] += dp[1][i]*(num-1)
        dp = use
    
    print(dp[0][K]+dp[1][K])

if __name__ == "__main__":
    main()

Solution (Python):
n=input()
k=int(input())
dp0=[[0]*(k+1) for _ in range(len(n))]
dp1=[[0]*(k+1) for _ in range(len(n))]
for i in range(len(n)):
  dp0[i][0]=1
if len(n)==1:
  dp0[0][1]=int(n)
else:
  dp0[0][1]=int(n[0])-1
  dp1[0][1]=1
  for i in range(1,len(n)):
    num=int(n[i])
    for j in range(k):
      dp0[i][j+1]=dp0[i-1][j+1]+dp0[i-1][j]*9+dp1[i-1][j]*max(num-1,0)
    if num==0:
      for j in range(1,k+1):
        dp1[i][j]=dp1[i-1][j]
    else:
      for j in range(k):
        dp1[i][j+1]=dp1[i-1][j]
        dp0[i][j+1]+=dp1[i-1][j+1]
      dp1[i][1]=0
print(dp0[len(n)-1][k]+dp1[len(n)-1][k])

Solution (Python):

def main():
    A = list(input())
    N = len(A)
    K = int(input())

    DP0 = [[0] * (K+1) for _ in range(N+1)]
    DP1 = [[0] * (K+1) for _ in range(N+1)]

    DP0[0][0] = 1
    
    for i in range(1, N+1):
        for k in range(0, K+1):
            if k >= 1:
                DP0[i][k] = (int(A[i-1]) == 0) * DP0[i-1][k] + (int(A[i-1]) >= 1) * DP0[i-1][k-1]
                DP1[i][k] = DP0[i-1][k-1]*max(int(A[i-1])-1, 0) + DP0[i-1][k]*(int(A[i-1]) >= 1) + DP1[i-1][k-1]*9 + DP1[i-1][k]
            else:
                DP0[i][k] = (int(A[i-1]) == 0) * DP0[i-1][k]
                DP1[i][k] = DP0[i-1][k]*(int(A[i-1]) >= 1) + DP1[i-1][k]
            
            
            

    print(DP0[N][K] + DP1[N][K])

if __name__ == "__main__":
    main()

Solution (Python):
from math import log
def solve(N, K):
    if N == 0:
        return 0
    if N == 1:
        if K == 1:
            return 1
        return 0
    num = int(log(N, 10))
    if K == 1:
        res = 9 * num + N//(10**num)
        return res
    if K == 2:
        res = 9 ** 2 * (num*(num-1))//2 
        res += (N//(10**num) - 1)*num*9
        res += solve(N - N//(10**num)*(10**num), 1)
        return res
    if K == 3:
        res = 9 ** 3 * (num*(num-1)*(num-2))//6
        res += (N//(10**num) - 1)*(num*(num-1))*81//2
        res += solve(N - N//(10**num)*(10**num), 2)
        return res
N = int(input())
K = int(input())
print(solve(N, K))

Solution (Python):
n=int(input())
K=int(input())
m=len(str(n))
N=list(map(int,str(n)))
dp=[[[0,0]for j in range(K+1)]for i in range(m+1)]
dp[0][0][0]=1
for i in range(1,1+m):
    for j in range(K+1):
        for k in range(10):
            if k==0:
                if N[i-1]==k:
                    dp[i][j][0]+=dp[i-1][j][0]
                elif N[i-1]>k:
                    dp[i][j][1]+=dp[i-1][j][0]
                dp[i][j][1]+=dp[i-1][j][1]
            else:
                if j<K:
                    if N[i-1]==k:
                        dp[i][j+1][0]+=dp[i-1][j][0]
                    elif N[i-1]>k:
                        dp[i][j+1][1]+=dp[i-1][j][0]
                    dp[i][j+1][1]+=dp[i-1][j][1]

print(sum(dp[-1][K]))

Solution (Python):
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
K = ri()

nums = list(map(int, list(str(N))))
L = len(nums)
dp = [ [[0]*2 for _ in range(K+2)] for _ in range(L+1)]

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

for i in range(L):
	for j in range(K+1):
		for k in range(2):
			for d in range(10):
				ni, nj, nk = i+1, j, k
				if d > 0:
					nj += 1
				if nj > K: continue
				if k == 0:
					if d < nums[i]:
						nk = 1
					elif d > nums[i]:
						continue
				dp[ni][nj][nk] += dp[i][j][k]
print(sum(dp[L][K]))

Solution (Python):
N = input()[::-1] 
K = int(input())


n = len(N) - 1


dp = [[1, 0, 0, 0]] + [[0 for _ in range(5)] for _ in range(n + 1)]

for i in range(1, n + 1):
    dp[i][0] = 1
    for j in [1, 2, 3]:
        dp[i][j] = sum([9 * dp[ii][j - 1] for ii in range(0, i)])


nzd = [0] * (n + 2)  
for i in range(n, -1, -1):
    nzd[i] = nzd[i + 1] + int(N[i] != '0')

ans = 0
for i in range(0, n):
    if N[n - i] == '0': continue
    
    ans += dp[n - i][max(-1, K - nzd[n - i + 1])]

    
    ans += (int(N[n - i]) - 1) * dp[n - i][max(-1, K - nzd[n - i + 1] - 1)]


if nzd[1] == K:
    ans += 1
elif nzd[1] == K - 1:
    ans += int(N[0])

print(ans)

Solution (Python):
n = list(map(int, list(input())))
k = int(input())
le = len(n)
dp = [[[0] * (le + 2) for _ in range(2)] for _ in range(le + 1)]
dp[0][0][0] = 1
for i in range(1, le + 1):
    for j in range(2):
        for s in range(le + 1):
            m = 10
            if j == 0:
                m = n[i - 1] + 1
            for t in range(m):
                x, y = 1, s
                if j == 0 and t == m - 1:
                    x = 0
                if not t == 0:
                    y += 1
                dp[i][x][y] += dp[i - 1][j][s]
ans = dp[le][0][k] + dp[le][1][k]
print(ans)

Solution (Python):
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))

def answer(n,k):
    ans = 0
    
    if n=='':
        return 0
    
    if n[0]=='0':
        ans += answer(n[1:],k)
    else:
        
        if len(n) > k:
            ans += combination(len(n)-1,k) * 9**k
        
        if len(n)>k-1:
            ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
        
        if k>1:
            ans += answer(n[1:],k-1)
        else:
            ans += 1
    return ans

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

print(answer(n,k) if len(n)>=k else 0)

Solution (Python):
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))

def answer(n,k):
    ans = 0
    if k>1:
        if n=='':
            return 0
        
        if n[0]=='0':
            ans += answer(n[1:],k)
        else:
            
            if len(n)>k:
                ans += combination(len(n)-1,k)*9**k
            
            if len(n)>k-1:
                ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
            
            ans += answer(n[1:],k-1)
    else:
        if n=='':
            return 0
        if n[0]=='0':
            ans += answer(n[1:],k)
        else:
            if len(n)>1:
                ans += combination(len(n)-1,1)*9
            ans += int(n[0])
    return ans

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

print(answer(n,k) if len(n)>=k else 0)

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


dp = [[[0]*2 for j in range(100+2)] for i in range(n_l+1)]
dp[0][0][0] = 1

for i in range(1,n_l+1) :
  m = int(n[i-1])
  for s in range(2) :
    for j in range(100+1) :
      if s == 0 :
        for num in range(m+1) :
          if num == m :
            if num == 0 :
              dp[i][j][0] += dp[i-1][j][0]
            else :
              dp[i][j+1][0] += dp[i-1][j][0]
          else :
            if num == 0 :
              dp[i][j][1] += dp[i-1][j][0]
            else :
              dp[i][j+1][1] += dp[i-1][j][0]
      else :
        for num in range(10) :
          if num == 0 :
            dp[i][j][1] += dp[i-1][j][1]
          else :
            dp[i][j+1][1] += dp[i-1][j][1]
            
print(dp[n_l][k][0]+dp[n_l][k][1])

Solution (Python):
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 in range(len(n)):
    for j in range(2):
        digit = 9 if j else int(n[i])
        for k in range(K + 1):
            for d in range(digit + 1):
                if d != 0:
                    dp[i + 1][j or d < digit][k + 1] += dp[i][j][k]
                else:
                    dp[i + 1][j or d < digit][k] += dp[i][j][k]

ans = 0
for j in range(2):
    ans += dp[-1][j][K]
print(ans)

Solution (Python):


def main():
    n = input()
    l = len(n)
    k = int(input())
    dp0 = [0 for j in range(4)]
    dp1 = [0 for j in range(4)]
    dp1[0] = 1
    for i in range(l):
        d = int(n[i])
        if d == 0:
            for j in [3, 2, 1]:
                dp0[j] += dp0[j - 1] * 9
        else:
            for j in [3, 2, 1]:
                dp0[j] += dp0[j - 1] * 9
                dp0[j] += dp1[j - 1] * max(0, d - 1)
                dp0[j] += dp1[j]
            dp0[0] += dp1[0]
            dp1 = [0] + dp1[0:3]
    print(dp0[k] + dp1[k])

if __name__ == "__main__":
    main()

Solution (Python):


from copy import deepcopy

def main():
    n = input()
    l = len(n)
    k = int(input())
    dp0 = [0 for j in range(4)]
    dp1 = [0 for j in range(4)]
    dp1[0] = 1
    for i in range(l):
        dppre0 = deepcopy(dp0)
        dppre1 = deepcopy(dp1)
        d = int(n[i])
        if d == 0:
            for j in [1, 2, 3]:
                dp0[j] += dppre0[j - 1] * 9
        else:
            for j in [1, 2, 3]:
                dp0[j] += dppre0[j - 1] * 9
                dp0[j] += dppre1[j - 1] * max(0, d - 1)
            for j in [0, 1, 2, 3]:
                dp0[j] += dppre1[j]
            dp1 = [0 for j in range(4)]
            for j in [1, 2, 3]:
                dp1[j] = dppre1[j - 1]
    print(dp0[k] + dp1[k])

if __name__ == "__main__":
    main()

Solution (Python):
N = list(map(int, input()))
K = int(input())

DP_conf = [[0] * (K+1) for _ in range(len(N))]
DP_unco = [[0] * (K+1) for _ in range(len(N))]

DP_conf[0][0] = 1
DP_conf[0][1] = N[0] - 1
DP_unco[0][0] = 0
DP_unco[0][1] = 1

for i in range(1,len(N)):
	for j in range(K+1):
		if j > i+1:
			break
		
		if j == 0:
			DP_conf[i][j] = 1
			DP_unco[i][j] = 0

		else:
			DP_conf[i][j] = DP_conf[i-1][j] + DP_conf[i-1][j-1] * 9
			if N[i] > 0:
				DP_conf[i][j] += DP_unco[i-1][j] + DP_unco[i-1][j-1] * (N[i] - 1)
				DP_unco[i][j] = DP_unco[i-1][j-1]
			else:
				DP_unco[i][j] = DP_unco[i-1][j]

print(DP_conf[-1][K] + DP_unco[-1][K])

Solution (Python):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if int('1' * K) > N:
	print(0)
	sys.exit()

N = str(N)
L = len(N)

def C(a,b):
	out = 1
	for _ in range(b):
		out *= a
		a -= 1
	for bb in range(1,b+1):
		out //= bb
	return out 

def solve(N,n,K):
	if K == 0:
		return 1
	if int('1' * K) > int(N):
		return 0

	ans = 0
	
	for i in range(1,n):
		if K - 1 > i - 1:
			continue
		else:
			ans += 9 * C(i-1, K-1) * (9 ** (K-1))
	
	
	head = int(N[0])
	ans += (head - 1) * C(n-1, K-1) * (9 ** (K-1))

	
	sh_N = ''
	for i in range(1,n):
		if N[i] != '0':
			sh_N = N[i:]
			break
	
	if sh_N != '':
		sh_n = len(sh_N)
		ans += solve(sh_N, sh_n, K-1)
	else:
		if K == 1:
			ans += 1

	return ans

answer = solve(N,L,K)

print(answer)

Solution (Python):
n = list(map(int, list(input())))
k = int(input())
ln = len(n)

if ln < k:
    print(0)
    exit()


def comb(n, r):
    m = 1
    for i in range(n-r+1, n+1):
        m *= i
    for i in range(1, r+1):
        m //= i
    return m

ans = 0


if ln > k:
    ans += comb(ln-1, k) * (9 ** k)


ans += comb(ln-1, k-1) * (9**(k-1)) * (n[0]-1)

if k == 1:
    ans += 1

elif k == 2:
    for i in range(1, ln):
        if n[i] != 0:
            ans += comb(ln-i-1, k-1) * (9**(k-1))
            ans += comb(ln-i-1, k-2) * (9**(k-2)) * (n[i]-1)
            ans += 1
            break

else:
    for i in range(1, ln):
        if n[i] != 0:
            ans += comb(ln-i-1, k-1) * (9**(k-1))
            ans += comb(ln-i-1, k-2) * (9**(k-2)) * (n[i]-1)
            for j in range(i+1, ln):
                if n[j] != 0:
                    ans += comb(ln-j-1, k-2) * (9**(k-2))
                    ans += comb(ln-j-1, k-3) * (9**(k-3)) * (n[j]-1)
                    ans += 1
                    break
            break

print(ans)

Solution (Python):
N = input()
K = int(input())

memo = [[[0 for _ in range(4)] for _ in range(2)] for _ in range(len(N))]

N_size = len(N)

def dfs(i=0,small=0,k = K):
    if k == 0: return 1
    if i > N_size - 1: return 0
    if memo[i][small][k] > 0: return memo[i][small][k]

    ret = 0
    dgt = int(N[i])

    if small == 1:
        ret += dfs(i+1,1,k-1) * 9
        ret += dfs(i+1,1,k)
    else:
        if dgt == 0:
            ret += dfs(i+1,0,k)
        else:
            ret += dfs(i+1,1,k)
            ret += dfs(i+1,1,k-1) * (dgt-1)
            ret += dfs(i+1,0,k-1)

    memo[i][small][k] = ret
    return ret

print(dfs())

Solution (Python):
N = input()
K = int(input())

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

for i in range(len(N)):
    dgt = int(N[i])
    for k in range(K+1):
        dp[i+1][1][k+1] += dp[i][1][k] * 9
        dp[i+1][1][k] += dp[i][1][k]

        if dgt > 0:
            dp[i+1][1][k+1] += dp[i][0][k] * (dgt-1)
            dp[i+1][1][k] += dp[i][0][k]

            dp[i+1][0][k+1] = dp[i][0][k]
        else:
            dp[i+1][0][k] = dp[i][0][k]

print(dp[len(N)][0][K] + dp[len(N)][1][K])

Solution (Python):
def DP(n, k):
    if k == 0:
        return 1
    elif n < 10 and k == 1:
        return n
    elif n < 10 and k != 0:
        return 0
    else:
        q, r = n//10, n % 10
        return DP(q, k)+r*DP(q, k-1)+(9-r)*DP(q-1, k-1)


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

Solution (Python):
def main():
    n = input()
    digit = len(n)
    
    k = int(input())
    dp0 = [[0]*k for _ in range(digit)]
    dp0[0][0] = int(n[0])-1
    
    dp1 = [[0]*k for _ in range(digit)]
    dp1[0][0] = 1
    
    c = 1
    flag1 = True
    flag2 = True
    flag3 = False
    flag4 = False
    flag5 = True
    for i in range(1, digit):
        if n[i] != "0":
            c += 1
        for j in range(k):
            if j > i or j > k:
                continue
            if j == 0:
                dp0[i][j] = 9+dp0[i-1][j]
                if c == 1:
                    dp1[i][j] = 1
                else:
                    if flag1:
                        dp0[i][j] += 1
                        flag1 = False
            if j == 1:
                dp0[i][j] = dp0[i-1][j-1]*9+dp0[i-1][j]
                if flag3:
                    dp0[i][j] += dp1[i-1][j-1]*9
                else:
                    dp0[i][j] += dp1[i-1][j-1]*max([(int(n[i])-1), 0])
                    if c >= 2:
                        flag3 = True
                
                if c == 2:
                    dp1[i][j] = 1
                if flag2 and c == 3:
                    dp0[i][j] += 1
                    flag2 = False
                
            if j == 2:
                dp0[i][j] = dp0[i-1][j-1]*9+dp0[i-1][j]
                
                if flag4:
                    dp0[i][j] += dp1[i-1][j-1]*9
                else:
                    dp0[i][j] += dp1[i-1][j-1]*max([(int(n[i])-1), 0])
                    if c >= 3:
                        flag4 = True

                if c == 3:
                    dp1[i][j] = 1
                if flag5 and c == 4:
                    dp0[i][j] += 1
                    flag5 = False
                    
    print(dp0[digit-1][k-1]+dp1[digit-1][k-1])

if __name__ == "__main__":
    main()

Solution (Python):
N=input()
l=len(N)
K=int(input())
dp=[[[0 for i in range(4)] for i in range(2)] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for c in range(4):
            lim=9 if smaller else int(N[i])
            for d in range(lim+1):
                if(c!=3):
                    dp[i+1][smaller or d<lim][c+(d!=0)]+=dp[i][smaller][c]
                else:
                    if(d==0):
                        dp[i+1][smaller or d<lim][c]+=dp[i][smaller][c]

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

Solution (Python):



N = list(input())
N = list(map(int, N))
K = int(input())


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


for keta in range(len(N)): 
    for smaller in range(2): 
        limit = 0
        if smaller==0:
            limit = N[keta]
        else:
            limit = 9
        for n in range(limit + 1):
            
            if n==0:
                for x in range(4):
                    dp[keta+1][smaller or n<limit][x] += dp[keta][smaller][x]
            else:
                for x in range(2, -1, -1):
                    dp[keta+1][smaller or n<limit][x+1] += dp[keta][smaller][x]


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

Solution (Python):
N = list(input())
K = int(input())

d = len(N)

def f(j,k):
    if j < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return 9*j
    elif k == 2:
        return 81*j*(j-1)//2
    elif k == 3:
        return 729*j*(j-1)*(j-2)//6

b = 0
ans = 0

for i in range(d):
    if b == K:
        break
    else:
        if int(N[i]) != 0:
            ans += f(d-(i+1),K-b) + (int(N[i])-1)*f(d-(i+1),K-b-1)
            b += 1
        else:
            continue

if b == K:
    print(ans+1)
else:
    print(ans)

Solution (Python):
n = input()
k = int(input())
dp = [[[0 for i in range(k+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(k+1):
      for i in range(10):
        if b ==1:
          if c ==k:  
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
          else:
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
            else:
              dp[a+1][1][c+1] += dp[a][1][c]
        else:
          if int(n[a]) > i:
            if c == k:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
              else:
                dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i:
            if c == k:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
              else:
                dp[a+1][0][c+1] += dp[a][0][c]
            
            
print(dp[-1][0][-1] + dp[-1][1][-1])

Solution (Python):
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
  if k == 1:
    print(int(n))  
  if k >= 2:
      print(0)
else:
  print(dp[-1][0][k] + dp[-1][1][k])

Solution (Python):
S = input()
L = len(S)
K = int(input())

dp = [[[0,0] for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(S):
    c = int(c)
    for k in reversed(range(K+1)):
        for d in range(10):
            nk = k + (d>0)
            if nk > K: continue
            dp[i+1][nk][1] += dp[i][k][1]
            if d > c: continue
            dp[i+1][nk][int(c>d)] += dp[i][k][0]
print(sum(dp[-1][-1]))

Solution (Python):
s,k=input(),int(input())
n=[int(i) for i in s]
l=len(s)
dp=[[[0]*(k+1),[0]*(k+1)] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for x in range(10 if smaller else n[i]+1):
            if x==0:
                for y in range(k+1):
                    dp[i+1][smaller or x<n[i]][y]+=dp[i][smaller][y]
            else:
                for y in range(k):
                    dp[i+1][smaller or x<n[i]][y+1]+=dp[i][smaller][y]
print(dp[-1][0][-1]+dp[-1][1][-1])

Solution (Python):

import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()

@lru_cache(None)
def solve(N, K):
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    q, r = divmod(N, 10)
    ret = 0
    if K > 0:
        ret += solve(q, K-1) * r
        ret += solve(q-1, K-1) * (9-r)
    ret += solve(q, K)  
    return ret

answer = solve(N, K)
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

n, k = map(int, read().split())


@lru_cache()
def check(n, k):
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    a, b = divmod(n, 10)
    cnt = 0
    if k >= 1:
        cnt += check(a, k - 1) * b
        cnt += check(a - 1, k - 1) * (9 - b)
    cnt += check(a, k)
    return cnt


print(check(n, k))