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

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()

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




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

for i in range(len(N)):
    for j in range(K + 1):
        if i == 0:
            dp[i][1][0] = 1
            dp[i][0][1] = 1
            dp[i][1][1] = N[0] - 1
        else:
            if j == 0:
                dp[i][j][1] = dp[i - 1][j][1]
            else:
                if N[i] == 0:
                    dp[i][j][0] = dp[i - 1][j][0]
                    dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j - 1][1] * 9
                else:
                    dp[i][j][0] = dp[i - 1][j - 1][0]
                    dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j - 1][1] * 9 + dp[i - 1][j - 1][0] * (N[i] - 1) + dp[i - 1][j][0]

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

Solution (Python):
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]


dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            if l[i]==0: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))
            else: dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+(dp1[i-1][j])
print(dp1[-1][-2]+dp2[-1][-2])

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

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

for i in range(kt):
    x = int(n[i])
    dp[i+1][0][0] = 1
    
    for j in range(3):
        if x == 0:
            dp[i+1][1][j+1] = dp[i][1][j+1]
            dp[i+1][0][j+1] = dp[i][0][j] * 9 + dp[i][0][j+1]
        else:
            dp[i+1][1][j+1] = dp[i][1][j]  
            dp[i+1][0][j+1] = dp[i][0][j] * 9 + dp[i][0][j+1] + dp[i][1][j] * (x-1) +  dp[i][1][j+1]
            
print(dp[kt][0][k] + dp[kt][1][k])

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

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

len_N = len(N)

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 j in range(2):
        for k in range(K + 1):
            lim = 9 if j else int(N[i])
            for d in range(lim + 1):
                if d != 0:
                    dp[i + 1][j or d < lim][k + 1] += dp[i][j][k]
                else:
                    dp[i + 1][j or d < lim][k] += dp[i][j][k]
ans = 0
for i in range(2):
    ans += dp[len_N][i][K]
print(ans)

Solution (Python):


def solve():
    S = input()  
    n = len(S)   
    K = int(input())

    
    
    
    
    
    
    dp = [[[0 for _ in range(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):
                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 == 0:
                        
                        if d > nd:
                            
                            continue
                        elif d < nd:
                            
                            nk = 1

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

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


if __name__ == "__main__":
    solve()

Solution (Python):

N = int(input())
K = int(input())
 
from functools import lru_cache
 
@lru_cache(None)
def f(n, K):
    if n <= 10:
        if K == 0:
            return 1
        if K == 1:
            return n
        return 0
    div_n = n//10
    mod_n = n%10
    ans = 0

    ans += f(div_n, K-1) * mod_n
    ans += f(div_n-1, K-1) * (9 - mod_n)
    ans += f(div_n, K)
    return ans
 
print(f(N, K))

Solution (Python):

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

from functools import lru_cache

@lru_cache(None)
def f(n, K):
    if n <= 10:
        if K == 0:
            return 1
        if K == 1:
            return n
        return 0
    div_n = n//10
    mod_n = n%10
    ans = 0
    if K >= 1:
        ans += f(div_n, K-1) * mod_n
        ans += f(div_n-1, K-1) * (9 - mod_n)
    ans += f(div_n, K)
    return ans

print(f(N, K))

Solution (Python):


n=input()
k=int(input())
dp_small=[[0 for i in range(4)] for j in range(101)]
dp_same=[[0 for i in range(4)] for j in range(101)]



for i in range(101):
    dp_small[i][0]=1
dp_small[0][0]=0
dp_same[0][0]=1
for i in range(len(n)):
    a=int(n[i])
    
    if a!=0:
        dp_small[i+1][1]=dp_small[i][1]+9*dp_small[i][0]+(a-1)*dp_same[i][0]+dp_same[i][1]
        dp_small[i+1][2]=dp_small[i][2]+9*dp_small[i][1]+(a-1)*dp_same[i][1]+dp_same[i][2]
        dp_small[i+1][3]=dp_small[i][3]+9*dp_small[i][2]+(a-1)*dp_same[i][2]+dp_same[i][3]

        dp_same[i+1][1]=dp_same[i][0]
        dp_same[i+1][2]=dp_same[i][1]
        dp_same[i+1][3]=dp_same[i][2]       
        
        
        
        
    elif a==0:
        dp_small[i+1][1]=dp_small[i][1]+9*dp_small[i][0]
        dp_small[i+1][2]=dp_small[i][2]+9*dp_small[i][1]
        dp_small[i+1][3]=dp_small[i][3]+9*dp_small[i][2]

        dp_same[i+1][1]=dp_same[i][1]
        dp_same[i+1][2]=dp_same[i][2]
        dp_same[i+1][3]=dp_same[i][3]
        
L=len(n)
sums= dp_small[L][k]+dp_same[L][k]

print(sums)

Solution (Python):
import numpy as np
N = input()
K = int(input())
L = len(N)
dp0 = [[0]*(K+1) for i in range(L+1)]
dp1 = [[0]*(K+1) for i in range(L+1)]
dp0[0][0] = 1
for i in range(1,L+1):
  c = int(N[i-1])
  for j in range(K+1):
    if j==0:
      if c>0:
        dp1[i][j] = dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = 0
      else:
        dp1[i][j] = dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
    else:
      if c>0:
        dp1[i][j] = dp0[i-1][j-1]*(c-1)+dp1[i-1][j-1]*9+dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = dp0[i-1][j-1]
      else:
        dp1[i][j] = dp1[i-1][j-1]*9+dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
print(dp0[-1][-1]+dp1[-1][-1])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    dp = [[0]*4 for _ in range(2)] 
    dp[0][0] = 1
    for a in input():
        a = int(a)
        ndp = [[0]*4 for _ in range(2)]
        for lt, k, d in product([0,1], range(4), range(10)):
            
            if (not lt) and d > a: continue
            nlt = max(lt, d < a)
            
            nk = k + (d>0)
            if nk > 3: continue
            
            ndp[nlt][nk] += dp[lt][k]
        dp = ndp

    k = int(input())
    print(dp[0][k] + dp[1][k])
resolve()

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 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        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 0 != d:
                    nb += 1
                if k < nb:
                    break
                if 0 == nc:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        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 0 != d:
                    nb += 1
                if k < nb:
                    break
                if 0 == nc:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Solution (Python):

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

    l = len(ns)

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

    for i in range(l):
        c = int(ns[i])

        dp_n = [[0, 0] for _ in range(k+1)]

        for j in range(k + 1):
            if c == 0:
                dp_n[j][0] += dp[j][0]
            else:
                dp_n[j][1] += dp[j][0]
                if j+1 <= k:
                    dp_n[j+1][1] += dp[j][0] * (c - 1)
                    dp_n[j+1][0] += dp[j][0]

            dp_n[j][1] += dp[j][1]
            if j+1 <= k:
                dp_n[j+1][1] += dp[j][1] * 9

        dp = dp_n

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


main()

Solution (Python):

def dyn(n,d00,d01,d02,d03,d10,d11,d12,d13):
    D00 = d00 + d10*int(n != 0)
    D10 = d10*int(n==0)
    D01 = d00*9 + d10*(n-1+int(n==0)) + d01 + d11*int(n!=0)
    D11 = d10*(int(n!=0)) + d11*(int(n==0))
    D02 = d01*9 + d11*(n-1+int(n==0)) + d02 + d12*int(n!=0)
    D12 = d11*(int(n!=0)) + d12*(int(n==0))
    D03 = d02*9 + d12*(n-1+int(n==0)) + d03 + d13*int(n!=0)
    D13 = d12*(int(n!=0)) + d13*(int(n==0))
    return D00,D01,D02,D03,D10,D11,D12,D13

N = str(input())
K = int(input())
S = len(N)
D00=0
D01=0
D02=0
D03=0
D10=1
D11=0
D12=0
D13=0

for i in range(S):
    [D00,D01,D02,D03,D10,D11,D12,D13] = dyn(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)
    
if K == 1:
    print(D01+D11)
elif K==2:
    print(D02+D12)
else:
    print(D03+D13)

Solution (Python):
def dyn(n,d00,d01,d02,d03,d10,d11,d12,d13):
    D00 = d00 + d10*int(n != 0)
    D10 = d10*int(n==0)
    D01 = d00*9 + d10*(n-1+int(n==0)) + d01 + d11*int(n!=0)
    D11 = d10*(int(n!=0)) + d11*(int(n==0))
    D02 = d01*9 + d11*(n-1+int(n==0)) + d02 + d12*int(n!=0)
    D12 = d11*(int(n!=0)) + d12*(int(n==0))
    D03 = d02*9 + d12*(n-1+int(n==0)) + d03 + d13*int(n!=0)
    D13 = d12*(int(n!=0)) + d13*(int(n==0))
    return D00,D01,D02,D03,D10,D11,D12,D13

N = str(input())
K = int(input())
S = len(N)
D00=0
D01=0
D02=0
D03=0
D10=1
D11=0
D12=0
D13=0

for i in range(S):
    [D00,D01,D02,D03,D10,D11,D12,D13] = dyn(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)

if K == 1:
    print(D01+D11)
elif K==2:
    print(D02+D12)
else:
    print(D03+D13)

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):
S = input()
K = int(input())

length = len(S)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(length + 1)]
dp[0][0][0] = 1

for i in range(1, length + 1):
    for j in range(2):
        for k in range(K + 1):
            os = int(S[i - 1])
            for x in range(10):
                ni = i
                nj = j
                nk = k
                if x != 0:
                    nk += 1
                if nk > K:
                    continue
                if j == 0:
                    if x > os:
                        continue
                    elif x < os:
                        nj = 1
                dp[ni][nj][nk] += dp[i - 1][j][k]

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

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

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):
        
        
        if k >= 1 and l != 0:
            dp[i][0][k] = dp[i-1][0][k-1]
        elif l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        
        
        dp[i][1][k] = dp[i-1][1][k]

        
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]

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

        

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

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

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):
        
        
        if l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        else:
            if k >= 1:
                
                dp[i][0][k] = dp[i-1][0][k-1]
        

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

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

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

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):
        
        
        if l == 0:
            dp[i][0][k] = dp[i-1][0][k]
        else:
            if k >= 1:
                dp[i][0][k] += dp[i-1][0][k-1]
        

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

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

Solution (Python):
n = input()
m = len(n)
K = int(input())
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):
        
        if l == 0:
            dp[i][0][k] += dp[i-1][0][k]
        else:
            if k >= 1:
                dp[i][0][k] += dp[i-1][0][k-1]
        

        dp[i][1][k] += dp[i-1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]
        if k >= 1:
            dp[i][1][k] += 9*dp[i-1][1][k-1]
            if l != 0:
                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
read = sys.stdin.read
n, k = map(int, read().split())


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


def solve(n, k):
    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
    res += solve(mod, k - 1)
    return res


print(solve(n, k))

Solution (Python):
import sys
read = sys.stdin.read
n, k = map(int, read().split())


def count(digit, k):
    if digit < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return digit
    elif k == 2:
        return digit * (digit - 1) // 2
    else:
        return digit * (digit - 1) * (digit - 2) // 6


def solve(n, k):

    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
    res += solve(mod, k - 1)
    return res


print(solve(n, k))

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

Solution (Python):
from functools import lru_cache
N = int(input())
K = int(input())
@lru_cache(None)
def f(n,k):
  if k<0:
    return 0
  if n<10:
    if k>1:
      return 0
    elif k==1:
      return n
    elif k==0:
      return 1
  a, b = divmod(n,10)
  m = 9*f(a-1,k-1)+f(a,k)+b*(f(a,k-1)-f(a-1,k-1))
  return m
print(f(N,K))

Solution (Python):
import sys
read = sys.stdin.read

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


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


def solve(n, k):
  if n == 0 and k > 0:
    return 0
  if k == 0:
    return 1
  digit = len(str(n))
  res = 0
  if digit > k:
    res += count(digit - 1, k) * (9 ** k)
  a = 10 ** (digit - 1)
  d, mod = n // a, n % a
  res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
  res += solve(mod, k - 1)
  return res


print(solve(n, k))

Solution (Python):
import sys
read = sys.stdin.read

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


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


def solve(n, k):
  digit = len(str(n))
  if digit == 0 and k > 0:
    return 0
  if k == 0:
    return 1
  res = 0
  if digit > k:
    res += count(digit - 1, k) * (9 ** k)
  a = 10 ** (digit - 1)
  d, mod = n // a, n % a
  res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
  res += solve(mod, k - 1)
  return res


print(solve(n, k))

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,c in enumerate(n):
	c=int(c)
	for f in range(2):
		for j in range(k+1):
			for l in range(10*f or c+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])

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

from functools import lru_cache

import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,read().split())
  
@lru_cache(None)
def F(N, K):

    assert N >= 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,m))

Solution (Python):
N = input()
K = int(input())
n0 = int(N[0])


def if_part_zero (N, p1, keta):
  partnum = 0
  beki = keta - 1
  for i in range(p1 - keta + 1, p1 + 1):
    if int(N[i]) > 0:
      return False
  return True


t = 0
if (K == 1):
  t = n0 + (len(N) - 1) * 9

if (K == 2):
  enough = 0
  for i in range(0, len(N) - 1):
    if i > 0:
      pattern1 = 9
      enough = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N)):
      if enough == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
      else:
        pattern2 = int(N[j])
      
      t += (pattern1 - 1) * 9 + pattern2
    
if (K == 3):
  enough1 = 0
  enough2 = 0
  for i in range(0, len(N) - 2):
    if i > 0:
      pattern1 = 9
      enough1 = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N) - 1):
      if enough1 == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
        enough2 = 1
      else:
        pattern2 = int(N[j])
      if pattern1 == 1 and pattern2 == 0:
        continue
      for k in range(j + 1, len(N)):
        if enough1 == 1 or enough2 == 1 or if_part_zero(N, k - 1, k - j - 1) == False:
          pattern3 = 9
        else:
          pattern3 = int(N[k])
        
        
        t += ((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3

print (t)

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

N = len(n)

a = [[0 for _ in range(k+1)] for _ in range(len(n)+1)]
b = [[0 for _ in range(k+1)] for _ in range(len(n)+1)]
b[0][0] = 1

for i, x in enumerate(n):
    a[i+1][0] = a[i][0] + b[i][0]
    for j in range(1, k+1):
        temp = a[i][j-1] * 9 + a[i][j]
        if x > 0:
            temp += b[i][j] + b[i][j-1] * (x-1)
        a[i+1][j] = temp
        if x == 0:
            b[i+1][j] = b[i][j]
        else:
            b[i+1][j] = b[i][j-1]




print(a[N][k] + b[N][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 j in range(K+1):
            for x in range(10 if smaller==1 else int(N[i])+1):
                dp[i+1][smaller or (x < int(N[i]))][j+1 if x!=0 else j]+=dp[i][smaller][j]
print(dp[len(N)][1][K]+dp[len(N)][0][K])

Solution (Python):
from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    m, r = divmod(N,10)
    ans = 0
    if K >= 1:
        ans += solver(m, K-1) * r
        ans += solver(m-1, K-1) * (9-r)
    ans += solver(m, K)
    return ans


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

Solution (Python):
from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    
    m, r = divmod(N,10)
    ans = 0
    if K >= 1:
        
        ans += solver(m, K-1) * r
        ans += solver(m-1, K-1) * (9-r)
    
    ans += solver(m, K)
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = solver(data[0][0], data[1][0])
    print(result)

Solution (Python):
def f(N, K):
    M, R = N // 10, N % 10
    if K == 0:
        return 1
    elif M == 0 and K == 1:
        return R
    elif M == 0 and K != 1:
        return 0
    else:
        return R * f(M, K-1) + (9-R) * f(M-1, K-1) + f(M, K)


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

Solution (Python):
x=input()
L=len(x)
N=[]
for l in range(L):
  N.append(int(x[l]))
N.insert(0,0) 
K=int(input())
dp0=[]
dp1=[]
for l in range(L+1):
  dp0.append([0]*(K+1))
  dp1.append([0]*(K+1))
dp1[0][0]=1
for l in range(1,L+1):
  dp0[l][0]=1
for i in range (1,L+1):
  for j in range(1,K+1):
    if N[i]==0:
      dp0[i][j]=dp0[i-1][j]+9*dp0[i-1][j-1]
      dp1[i][j]=dp1[i-1][j]
    else:
      dp0[i][j]=dp0[i-1][j]+9*dp0[i-1][j-1]+(N[i]-1)*dp1[i-1][j-1]+dp1[i-1][j]
      dp1[i][j]=dp1[i-1][j-1]
print(dp0[L][K]+dp1[L][K])

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

def f(n,k):
  if len(n) == 1:
    if k == 1:
      return n[0]
    else:
      return 0
  else:
    r = n[-1]
    m = n[:-1]
    m2 = m.copy()
    m2[-1] = m2[-1] - 1
    for i in range(len(m)):
      if m2[-i] < 0:
        m2[-i] += 10
        m2[-i-1] = m2[-i-1] - 1
    if k == 1:
      m = n[:-1]
      return f(m,1) + 9
    else:
      return f(m,k) + f(m,k-1) * r + f(m2,k-1) * (9-r)
    
print(f(N,K))

Solution (Python):


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

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

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






keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

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

        if n != 0:
          nj += 1 
        if nj > K: 
          continue 
        if k == 0:
          if n > num:
            continue 
          if n < num:
            nk = 1 

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

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

Solution (Python):
N = input()
K = int(input())
dp= [[[0]*2 for i in range(len(N)+1)] for _ in range(len(N)+1)]
if len(N)<K:
  print(0)
  exit()
dp[0][0][0]=1
for i in range(len(N)):
  for j in range(len(N)):
    if int(N[i])!=0:
      dp[i+1][j+1][1]+=dp[i][j][1]*9+dp[i][j][0]*(int(N[i])-1)
      dp[i+1][j][1] += dp[i][j][1]+dp[i][j][0]
      dp[i+1][j+1][0] += dp[i][j][0] 
    if int(N[i])==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][0] += dp[i][j][0]
print(dp[len(N)][K][0]+dp[len(N)][K][1])

Solution (Python):
import numpy as np

N = input()
K = int(input())
lt,eq = 0,1
dp = np.zeros((101,2,5),dtype=int)

dn = len(N)
dp[0][eq][0] = 1
for i in range(dn):
    di = ord(N[i]) - ord('0')
    for k in range(K+1):
        dp[i+1][lt][k] = dp[i][lt][k] * 1 + dp[i][eq][k] * (1 if di >= 1 else 0)
        if k:
            dp[i+1][lt][k] += dp[i][lt][k-1] * 9 + dp[i][eq][k-1] * max(0,di-1)
        if dp[i][eq][k]:
            dp[i+1][eq][k+(di>0)] = 1

print(int(dp[dn][lt][K] + dp[dn][eq][K]))

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

dp0 = [[0] * (K + 1) for _ in range(L + 1)]
dp1 = [[0] * (K + 1) for _ in range(L + 1)]

dp0[0][0] = 1

n = []
for i in N:
    n.append(int(i))

for i in range(L):
    D = n[i]
    for j in range(K + 1):
        if D == 0:
            dp0[i + 1][j] += dp0[i][j]
            dp1[i + 1][j] += dp1[i][j]
            if j < K:
                dp1[i + 1][j + 1] = dp1[i][j] * 9
        else:
            dp1[i + 1][j] += (dp0[i][j] + dp1[i][j])
            if j < K:
                dp0[i + 1][j + 1] += dp0[i][j]
                dp1[i + 1][j + 1] += (D - 1) * dp0[i][j]
                dp1[i + 1][j + 1] += 9 * dp1[i][j]

print(dp0[L][K] + dp1[L][K])

Solution (Python):






def main(N,K):
    dp0 = [[0] * (K + 1) for _ in range(len(N) + 1)]
    dp1 = [[0] * (K + 1) for _ in range(len(N) + 1)]
    dp0[0][0] = 1

    
    for i, n in enumerate(N):
        for k in range(K + 1):
            
            if n == '0':
                dp0[i+1][k] += dp0[i][k]
                dp1[i+1][k] += dp1[i][k]
                
                if k < K:
                    dp1[i + 1][k + 1] += 9 * dp1[i][k]
            
            else:
                if k < K:
                    dp0[i+1][k+1] += dp0[i][k]
                    dp1[i+1][k+1] += (int(n) - 1) * dp0[i][k]
                    dp1[i+1][k+1] += 9 * dp1[i][k]

                dp1[i+1][k] += dp0[i][k]
                dp1[i+1][k] += dp1[i][k]
    print(dp0[-1][K] + dp1[-1][K])

N = input()
K = int(input())
main(N,K)

Solution (Python):
from functools import lru_cache

@lru_cache(maxsize = None)
def rec(digit, flag, k):
    limit = int(N[digit])
    if k > K:
        return 0
    if digit == len(N) - 1:
        if k == K:
            return 1
        elif k == K - 1:
            return limit if flag else 9
        else:
            return 0
    if flag:
        if limit == 0:
            return rec(digit + 1, 1, k)
        else:
            return rec(digit + 1, 0, k + 1) * (limit - 1) + rec(digit + 1, 1, k + 1) + rec(digit + 1, 0, k)
    else:
        return rec(digit + 1, 0, k + 1) * 9 + rec(digit + 1, 0, k)

N = input()
K = int(input())
print(rec(0, 1, 0))

Solution (Python):
def rec(digit, flag, k):
    limit = int(N[digit])
    if k > K:
        return 0
    if digit == len(N) - 1:
        if k == K:
            return 1
        elif k == K - 1:
            return limit if flag else 9
        else:
            return 0
    if flag:
        if limit == 0:
            return rec(digit + 1, 1, k)
        else:
            return rec(digit + 1, 0, k + 1) * (limit - 1) + rec(digit + 1, 1, k + 1) + rec(digit + 1, 0, k)
    else:
        return rec(digit + 1, 0, k + 1) * 9 + rec(digit + 1, 0, k)

N = input()
K = int(input())
print(rec(0, 1, 0))

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



dp0 = [[0] * (K + 1) for i in range(N_digit + 1)]
dp1 = [[0] * (K + 1) for i in range(N_digit + 1)]
dp0[0][0] = 1

for i, n in enumerate(N):
    for k in range(K + 1):
        if n == '0':
            dp0[i + 1][k] += dp0[i][k]
            dp1[i + 1][k] += dp1[i][k]
            if k < K:
                dp1[i + 1][k + 1] += 9 * dp1[i][k]

        else:
            if k < K:
                dp0[i + 1][k + 1] += dp0[i][k]
                dp1[i + 1][k + 1] += (int(n) - 1) * dp0[i][k]
                dp1[i + 1][k + 1] += 9 * dp1[i][k]

            dp1[i + 1][k] += dp0[i][k]
            dp1[i + 1][k] += dp1[i][k]

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

Solution (Python):
n=int(input())
l=len(str(n))
k=int(input())
dp=[[[0]*(k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][1][0]=1
for pos in range(l):
  num=int(str(n)[pos])
  for i in range(10):
    if i==0:
      for count in range(k+1):
        if num==0:
          dp[pos+1][1][count]+=dp[pos][1][count]
          dp[pos+1][0][count]+=dp[pos][0][count]
        else:
          dp[pos+1][0][count]+=(dp[pos][0][count]+dp[pos][1][count])
    elif i<num:
      for count in range(k):
        dp[pos+1][0][count+1]+=(dp[pos][0][count]+dp[pos][1][count])
    elif i==num:
      for count in range(k):
        dp[pos+1][1][count+1]+=dp[pos][1][count]
        dp[pos+1][0][count+1]+=dp[pos][0][count]
    else:
      for count in range(k):
        dp[pos+1][0][count+1]+=dp[pos][0][count]
print(dp[l][0][k]+dp[l][1][k])

Solution (Python):
from math import factorial
N = int(input())
K = int(input())
S = list(map(int,str(N))) 
ans = 0
digit = len(S)
k = K

def D(i,j): 
    if i >= j:
        return (9**j) * (factorial(i) // (factorial(i - j) * factorial(j)))
    else:
        return 0

if K > len(S):
    print(0)
    exit()

for i in range(digit):
    digit -= 1
    if int(S[i]) == 0:
        if K == len(S):
            print(0)
            exit()
        continue
    ans += D(digit,k)
    k -= 1
    if k == 0:
        ans += S[i]
        break
    ans += (int(S[i]-1))*D(digit,k)
print(ans)