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



iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for k in range(min(i+1, K+1)):
            dp0, dp1 = dp[i], dp[i+1]

            dp1[1][k+1] += 9 * dp0[1][k]
            dp1[1][k]   +=     dp0[1][k]

            x, y = N[i], dp0[0][k]
            if x == 0:
                dp1[0][k] += y
            else:
                dp1[1][k] += y
                dp1[0][k+1] += y
                dp1[1][k+1] += (x-1) * y
        

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

if __name__ == "__main__":
    resolve()

Solution (Python):



iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for k in range(i+1):
            dp0, dp1 = dp[i], dp[i+1]

            dp1[1][k+1] += 9 * dp0[1][k]
            dp1[1][k]   +=     dp0[1][k]

            x, y = N[i], dp0[0][k]
            if x == 0:
                dp1[0][k] += y
            else:
                dp1[1][k] += y
                dp1[0][k+1] += y
                dp1[1][k+1] += (x-1) * y
        

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

if __name__ == "__main__":
    resolve()

Solution (Python):



iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for less in range(2):
            for k in range(i+1):
                for x in range(10 if less else N[i] + 1):
                    
                    dp[i+1][less or x < N[i]][k + (1 if x else 0)] += dp[i][less][k]
        

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

if __name__ == "__main__":
    resolve()

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



dp0=[[0]*(m+1) for _ in range(m+1)]
dp1=[[0]*(m+1) for _ in range(m+1)]
dp1[0][0]=1
for i in range(1,m+1):
    dp0[i][0]=1

for i in range(m):
    for j in range(m):
        if N[i]=='0':
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]
            dp1[i+1][j+1]=dp1[i][j+1]
        else:
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]+ dp1[i][j]*(int(N[i])-1)+dp1[i][j+1]
            dp1[i+1][j+1]=dp1[i][j]
            
if m<K:
    print(0)
else:
    print(dp0[-1][K]+dp1[-1][K])

Solution (Python):



iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for less in range(2):
            for k in range(size):
                for x in range(10 if less else N[i] + 1):
                    
                    dp[i+1][less or x < N[i]][k + (1 if x else 0)] += dp[i][less][k]
        

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

if __name__ == "__main__":
    resolve()

Solution (Python):
N = int(input())
K = int(input())
 
def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])
 
def keta2(n):
    if n < 10:
      return 0
    s = str(n)
    cnt = [0] * 101
    for i in range(2, 101):
        cnt[i] = 9 * 9 * (i - 1)
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta1(10 ** (len(s) - 1) - 1) + keta1(int(s[1:]))
    return res
 
def keta3(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(3, 101):
        cnt[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta2(10 ** (len(s) - 1) - 1) + keta2(int(s[1:]))
    return res
 
if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    if r == 1:
        return n
    elif r == 2:
        return n * (n-1) // 2
    else:
        return n * (n-1) * (n-2) // (3 * 2) 

def rec(i, k, isSmaller):
    if k == 0:
        return 1

    if i == N:
        return 0
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

Solution (Python):
from scipy.misc import comb

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

L = len(N)

if N.count("0") > L - K:
    integer = int(N)
    N = str(integer - integer % 10 - 1)

L = len(N)

if L < K or N[0] == "-":
    print(0)
    quit()

M = ["0"] * L
count = 0
for i in range(L):
    count += bool(int(N[i]))
    M[i] = N[i]
    if count == K:
        M = "".join(M)
        break

index = 0
ans = 0
count = 0
while index < L:
    if int(M[index]):
        count += 1
        n = L - index - 1
        k = K - count + 1
        digit = int(M[index]) - (count != K)
        ans += comb(n, k, exact=True) * 9 ** k + \
               digit * comb(n, k - 1, exact=True) * 9 ** (k - 1)
    index += 1

print(int(ans))

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


def combination(n,k):
    if n == 0:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n*(n-1)/2
    else:
        return n*(n-1)*(n-2)/6



def dp(i,k,is_small): 
    if i == L: 
        return 1 if k == 0 else 0
    if k == 0:
        return 1
    if is_small:
        return combination((L-i),k)*9**k
    else:
        if N[i] == '0': 
            return dp(i+1,k,False) 
        else:
            zero = dp(i+1,k,True) 
            aida = dp(i+1,k-1,True) * (int(N[i])-1)
            icchi = dp(i+1,k-1,False) 
            return zero + aida + icchi
        

L = len(N)
print(int(dp(0,K,False)))

Solution (Python):
N=input()
K=int(input())
m=len(N)
 
dp0=[[0]*(m+1) for _ in range(m+1)]
dp1=[[0]*(m+1) for _ in range(m+1)]
dp1[0][0]=1
for i in range(1,m+1):
    dp0[i][0]=1
    
for i in range(m):
    for j in range(m):
        if N[i]=='0':
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]
            dp1[i+1][j+1]=dp1[i][j+1]
        else:
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]+dp1[i][j]*(int(N[i])-1)+dp1[i][j+1]
            dp1[i+1][j+1]=dp1[i][j]
if m<K:
  print(0)
else:
  print(dp0[-1][K]+dp1[-1][K])

Solution (Python):
import sys
from io import StringIO

def resolve():
    s=input().strip()
    k=int(input().strip())

    dp = [[[0 for a in range(2)] for b in range(5)]for c in range(105)]

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

    keta=1
    for a in s:
        for b in range(4):
            for c in range(2): 
                n=int(a)
                for d in range(10):
                    if c==0 and d > n:
                        
                        continue

                    b2 = b
                    if d != 0:
                        b2 += 1
                    
                    c2=c
                    if c==0 and n != d:
                        c2 = 1

                    dp[keta][b2][c2]+=dp[keta-1][b][c]
        keta+=1

    ans = dp[len(s)][k][0] + dp[len(s)][k][1]

    print(ans)

    return

resolve()

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

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

for i in range(1,len(N)+1):
    for j in range(4):
        for k in range(2):
            if k == 0 and j != 0:
                if N[i-1] == "0":
                    dp[i][j][k] = dp[i-1][j-1][0] * 9 + dp[i-1][j][0]
                else:
                    dp[i][j][k] = dp[i-1][j-1][0] * 9 + dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j-1][1]*(int(N[i-1])-1)
            if k == 0 and j == 0:
                dp[i][j][k] = dp[i-1][j][0] + dp[i-1][j][1]

            if k == 1 and j != 0:
                if N[i-1] == "0":
                    dp[i][j][k] = dp[i-1][j][1]
                else:
                    dp[i][j][k] = dp[i-1][j-1][1]

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

Solution (Python):
from functools import lru_cache

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

@lru_cache(None)
def rec(n, k):
    if k == 0:
        return 1
    if n < 10:
        if k == 1:
            return n
        else:
            return 0


    m,d = divmod(n,10)

    ret = 0
    ret += d * rec(m,k-1) 
    ret += (9-d)*rec(m-1,k-1) 
    ret += rec(m,k) 

    return ret

print(rec(N,K))

Solution (Python):
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))]




dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 
        dp[i][0][1] = dp[i-1][0][0] 
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] 
        dp[i][1][1] = dp[i-1][0][0]*(int(n[i])-1)+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(int(n[i])-1)+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(int(n[i])-1)+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] 
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))




N = input()
K = I()
l = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(l + 1)]
dp[0][False][0] = 1
for i in range(1, l + 1):
    N_i = int(N[i - 1])
    for smaller in [True, False]:  
        for j in range(K + 1):
            for d in range((9 if smaller else N_i) + 1):
                if j + (0 if d == 0 else 1) <= K:
                    dp[i][smaller or d < N_i][j + (0 if d == 0 else 1)] += dp[i - 1][smaller][j]

print(dp[l][True][K] + dp[l][False][K])

Solution (Python):
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))] 

dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 
        dp[i][0][1] = dp[i-1][0][0] 
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] 
        dp[i][1][1] = dp[i-1][0][0]*(max(0,int(n[i])-1))+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(max(0,int(n[i])-1))+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(max(0,int(n[i])-1))+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] 
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])

Solution (Python):
from math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

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

    ans = func(N, K)

    print(ans)

def func(N, K):
    N = N.lstrip('0')
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    if l >= K:
        ret += func('9'* l, K)

    
    

    return ret
    

if __name__ == '__main__':
    main()

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

from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))



def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, False)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Solution (Python):
s=input()
K=int(input())
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 j in range(K+1):
        for k in range(2):
            nd=int(s[i])
            for d in range(10):
                ni,nj,nk=i+1,j,k
                if d!=0:
                    nj+=1
                if nj>K:
                    continue
                if nk==0:
                    if nd<d:
                        continue
                    if nd>d:
                        nk=1
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[n][K][0]+dp[n][K][1])

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

helper = {}


def fun(digit, remaining_non_zero, edge_case):
    if str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case) in helper.keys():
        return helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)]

    if remaining_non_zero < 0:
        return 0
    if digit == 0 and remaining_non_zero == 0:
        return 1
    if digit == 0 and remaining_non_zero >= 1:
        return 0

    if edge_case == True:
        ans = 0
        for i in range(nlist[len(nlist) - digit] + 1):
            if i == 0:
                if nlist[len(nlist) - digit] == 0:
                    ans += fun(digit - 1, remaining_non_zero, True)
                else:
                    ans += fun(digit - 1, remaining_non_zero, False)
            elif i == nlist[len(nlist) - digit]:
                ans += fun(digit - 1, remaining_non_zero - 1, True)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)] = ans
        return ans
    if edge_case == False:
        ans = 0
        for i in range(10):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)] = ans
        return ans

print(fun(len(nlist), k, True))

Solution (Python):


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

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


count=1
for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=max((dp[i][j]-1)*9+int(n[i+1]),0) if j==count else dp[i][j]*9
    if int(n[i+1])!=0:
        count+=1
    dp[i+1][K]+=dp[i][K]
    
print(dp[-1][-1])

Solution (Python):
N = input()
L = len(N)
K = int(input())
dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(L + 1)]
dp[0][0][1] = 1
for i, x in zip(range(L), map(int, N)):
    for k in range(K):
        dp[i+1][k][0] += dp[i][k][0]  
        if x == 0:
            dp[i+1][k][1] += dp[i][k][1]
        elif x > 0:
            dp[i+1][k][0] += dp[i][k][1]
        
        for d in range(1, 10):
            dp[i+1][k+1][0] += dp[i][k][0]
            if d == x:
                dp[i+1][k+1][1] += dp[i][k][1]
            elif d < x:
                dp[i+1][k+1][0] += dp[i][k][1]
    dp[i+1][K][0] += dp[i][K][0]  
    if x == 0:
        dp[i+1][K][1] += dp[i][K][1]
    elif x > 0:
        dp[i+1][K][0] += dp[i][K][1]
print(sum(dp[-1][K]))

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

L = len(str(N))
N2 = list(str(N))
dp1 = [[0 for i in range(L+1)] for j in range(3+1)]
dp2 = [[0 for i in range(L+1)] for j in range(3+1)]
dp1[0]=[1]*(L+1)
temp = 0
for i in range(L):
    
    if (N2[i] != "0" and temp <= K-1):
        temp += 1
        dp2[min(temp,K)][i+1] += 1
    elif (N2[i] == "0" and dp2[min(temp,K)][i] == 1):
        dp2[min(temp,K)][i+1] += 1


dp1[1][1] = int(N2[0])-1
for i in range(1,K+1):
    for j in range(2,L+1):
        if (N2[j-1] != "0" and i == 1 ):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 2):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 3):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        else:
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]

print(dp1[K][-1]+dp2[K][-1])

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

dp = [[[0 for a in range(k+1)] for b in range(2)] for c in range(l+5)]

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


for a in range(l) :
    for b in range(2) :
        for c in range(k+1) :
            for d in range(10) :
                na = a
                nb = b
                nc = c
                if b == 0 :
                    if d > int(n[a]) :
                        continue
                    if d < int(n[a]) :
                        nb = 1
                if c == k and d > 0 :
                    continue
                if d != 0 :
                    nc += 1
                
                dp[na+1][nb][nc] += dp[a][b][c]



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

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

sN=str(N)
keta=len(sN)


dp=[[[0]*2 for __ in range(K+1)] for _ in range(keta+1)]
dp[0][0][1]=1

for i in range(keta):
    for j in range(K+1):
        for k in range(2):
            for n in range(10):
                if k==1 and n>int(sN[i]): break
                ni=i+1
                nj=j if n==0 else j+1
                if nj>K: continue
                nk=1 if k==1 and n==int(sN[i]) else 0
                dp[ni][nj][nk]+=dp[i][j][k]

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

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

dp = [[[0]*2 for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(N):
    c = int(c)
    for k in range(K+1):
        for less in range(2):
            for d in range(10):
                nk = k + (d>0)
                if nk > K: continue
                if less == 0 and d > c: continue
                nxless = not(less==0 and d==c)
                dp[i+1][nk][nxless] += dp[i][k][less]
print(sum(dp[-1][-1]))

Solution (Python):
def f(n, k):
    
    
    
    
    n = str(n)
    L = len(n)

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

    for i in range(L):
        D = int(n[i])
        for smaller in range(2):
            for j in range(k+1):
                for d in range((9 if smaller else D)+1):
                    dp[i+1][smaller or (d < D)][j + (d != 0)] += dp[i][smaller][j]

    return dp[L][0][k] + dp[L][1][k]


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

    print(f(N, K))


if __name__ == "__main__":
    main()

Solution (Python):

import sys


def solve(N: int, K: int):
    n = len(str(N))
    dp = [[[0]*2 for _ in range(5)] for _ in range(n+1)]
    
    number = str(N)
    dp[0][0][0] = 1

    for i in range(n):
        for j in range(4):
            if number[i] == "0":
                
                dp[i+1][j][0] += dp[i][j][0]

                
                dp[i+1][j+1][1] += dp[i][j][1]*9
                dp[i+1][j][1] += dp[i][j][1]        

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

                
                dp[i+1][j+1][1] += dp[i][j][1]*9
                dp[i+1][j][1] += dp[i][j][1]

                
                dp[i+1][j+1][1] += dp[i][j][0]*(int(number[i])-1)
                dp[i+1][j][1] += dp[i][j][0]

    print(sum(dp[n][K]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    solve(N, K)

if __name__ == '__main__':
    main()

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))



N = input()
K = I()
l = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(l + 1)]
dp[0][False][0] = 1
for i in range(1, l + 1):
    N_i = int(N[i - 1])
    for smaller in [True, False]:  
        for j in range(K + 1):
            for d in range((9 if smaller else N_i) + 1):
                if j - (0 if d == 0 else 1) >= 0:
                    dp[i][smaller or d < N_i][j] += dp[i - 1][smaller][j - (0 if d == 0 else 1)]

print(dp[l][True][K] + dp[l][False][K])

Solution (Python):

from functools import lru_cache

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


@lru_cache(None)
def F(N, K):
    
    """N以下で0でないものがちょうどK個。0を含める"""
    
    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))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = input()
K = INT()
L = len(n)





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

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

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

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

sN=str(N)
keta=len(sN)


dp=[[[0]*2 for __ in range(K+1)] for _ in range(keta+1)]
dp[0][0][1]=1

for i in range(1,keta+1):
    for j in range(K+1):
        if sN[i-1]=='0':
            dp[i][j][1] = dp[i-1][j][1]
        elif j>0:
            dp[i][j][1] = dp[i-1][j-1][1]
        dp[i][j][0] = dp[i-1][j][0]
        if sN[i-1]!='0':
            dp[i][j][0] += dp[i-1][j][1]
        if j>0:
            dp[i][j][0] += dp[i-1][j-1][1]*(max(0,int(sN[i-1])-1))
            dp[i][j][0] += dp[i-1][j-1][0]*9

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

Solution (Python):
NN = 2020202
MOD = 10**9+7
INF = float("inf")

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

dp0 = [[0] * 4 for _ in range(len_n)]  
dp1 = [[0] * 4 for _ in range(len_n)]  
dp0[0][1] = 1
dp1[0][1] = int(N[0]) - 1
for i in range(len_n):
    dp1[i][0] = 1

for i in range(1, len_n):
    cur = int(N[i])
    for k in range(1, 4):
        if cur == 0:
            dp0[i][k] = dp0[i - 1][k]
            dp1[i][k] = dp1[i - 1][k] + 9*dp1[i - 1][k-1]

        else:
            dp0[i][k] = dp0[i - 1][k - 1]
            dp1[i][k] = dp1[i - 1][k] + 9*dp1[i - 1][k-1] + (cur - 1)*dp0[i - 1][k-1] + dp0[i - 1][k]

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

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

k = int(input())

keta = len(str(n))

dp = [[[0 for j in range(k+2)] for _ in range(2)]  for i in range(keta)]

s = str(n)



x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(k+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    
    
    




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

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

k = int(input())

keta = len(str(n))

dp = [[[0 for j in range(k+2)] for _ in range(2)]  for i in range(keta)]

s = str(n)



x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(k+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    
    
    




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

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

k = int(input())

keta = len(str(n))

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

s = str(n)



x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(k+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    
    
    




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

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

k = int(input())

keta = len(str(n))

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

s = str(n)



x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(keta+1):
        dp[i][0][j] += dp[i - 1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][1][j + 1] += dp[i - 1][1][j]
            dp[i][0][j]     += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    
    
    




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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()
K = INT()

dp_co = [[0 for _ in range(3 + 1)] for _ in range(len(N) + 1)]
dp_unco = [[0 for _ in range(3 + 1)] for _ in range(len(N) + 1)]
dp_co[0][0] = 1

for i in range(len(N)):
	for j in range(4):
		for k in range(2):
			for num in range(10):
				n_i, n_j, n_k = i + 1, j, k
				if num != 0:
					n_j += 1
				if n_j > K:
					continue
				if k == 0:
					if num > int(N[i]):
						continue
					if num == int(N[i]):
						k = 0
					if num < int(N[i]):
						n_k = 1
				if n_k == 0:
					dp_co[n_i][n_j] += dp_co[i][j]
				if n_k == 1:
					if k == 0:
						dp_unco[n_i][n_j] += dp_co[i][j]
					else:
						dp_unco[n_i][n_j] += dp_unco[i][j]						

ans = dp_co[len(N)][K] + dp_unco[len(N)][K]
print(ans)

Solution (Python):


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

from collections import defaultdict
dd = defaultdict(int)



def rep(NN,KK):
    if KK<0:
        return 0
    
    ha=NN*10+KK
    if dd[ha]!=0:
        return dd[ha]
    
    if NN<0:
        return 0
    
    if NN==0:
        if KK==0:
            return 1
        return 0
        
    
    na=NN//10
    nb=NN%10
    if nb==0:
        dd[ha]=rep(na,KK)+rep(na-1,KK-1)*9
        return dd[ha]
    else:
        dd[ha]=rep(na,KK)+rep(na,KK-1)*nb+rep(na-1,KK-1)*(9-nb)
        return dd[ha]
    
print(rep(N,K))

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

def c(n,k):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k == 2:
		return n*(n-1)//2
	else:
		return n*(n-1)*(n-2)//6
def f(N, K):
	if N == 0 and K > 0:
		return 0

	if K == 0:
		return 1
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit-1, K) * (9 ** K)
	a = 10**(digit-1)
	d = N // a
	ret += (d-1) * c(digit-1, K-1) * (9 ** (K-1))
	ret += f(N - d*a, K-1)

	return ret

print(f(N,K))