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

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])
            
            result %= (10**9+7)

    return result


def f(x,k,small):    
    d = len(x)
    
    if d == 0:        
        if k==0:
            return 1
        else:   
            return 0
    
    
    if d<k:
        return 0

    if k==0:
        return 1

    
    

    if small:
        
        return (9**(k))*cmb(d, k)

    
    if x[0]==0:
        return f(x[1:],k,False)
    zero = f(x[1:],k,True)
    aida=f(x[1:],k-1,True)*(x[0]-1)
    eq = f(x[1:], k-1,False)
    
    return zero+aida+eq

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

print(f(N,K,False))

Solution (Python):
Nstr=input()
N=int(Nstr)
K=int(input())
x=len(Nstr)
dp0=[[0]*(K+1) for i in range(x+1)]
dp1=[[0]*(K+1) for i in range(x+1)]

dp1[0][0]=1

for i in range(1,x+1):
  dp0[i][0]=dp0[i-1][0]+dp1[i-1][0]
  for j in range(1,K+1):
    if Nstr[i-1]!='0':
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
    else:
      dp1[i][j]=dp1[i-1][j]
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)

    
  '''  
  if Nstr[i-1]!='0':
    for j in range(1,K+1):
      dp1[i][j]=dp1[i-1][j-1]
      dp0[i][j]+=(dp1[i-1][j-1]*(int(Nstr[i-1])-1)+dp1[i-1][j])
  else:
    for j in range(1,K+1):
      dp1[i][j]=dp1[i-1][j]
  for j in range(1,K+1):
    dp0[i][j]+=(dp0[i-1][j]+dp0[i-1][j-1]*9)
  '''
print(dp0[x][K]+dp1[x][K])

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):
    N=int(n[i-1])
    for j in range(k+1):
        DP[i][1][j] +=DP[i-1][1][j]
        if N!=0:DP[i][1][j] +=DP[i-1][0][j]
        else:DP[i][0][j] +=DP[i-1][0][j]
        if j!=0:
            DP[i][1][j] +=9*DP[i-1][1][j-1]
            if N!=0:
                DP[i][0][j] +=DP[i-1][0][j-1]
                DP[i][1][j] +=(N-1)*DP[i-1][0][j-1]

print(DP[m][0][k]+DP[m][1][k])

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

Solution (Python):
N = int(input())
K = int(input())
from functools import lru_cache

@lru_cache(maxsize=100000000000)
def dp(n, k): 
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

Solution (Python):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

def main():
    N = rs()
    K = ri()
    a = [int(c) for c in N]
    dp = [[0] * (K + 1) for i in range(2)]

    dp[1][0] = 1
    dp[1][1] = a[0] - 1
    dp[0][1] = 1

    for i in range(1,len(a)):
        ndp = [[0] * (K + 1) for i in range(2)]

        for k in range(K+1):
            if k + 1 <= K:
                ndp[1][k + 1] += 9 * dp[1][k] 
            ndp[1][k] += dp[1][k] 
        
        for k in range(K+1):
            if a[i] == 0:
                ndp[0][k] += dp[0][k] 
            else:
                ndp[1][k] += dp[0][k] 
                if k + 1 <= K:
                    ndp[1][k + 1] += (a[i] - 1) * dp[0][k] 
                    ndp[0][k + 1] += dp[0][k]
        
        dp = ndp
    print(dp[0][K] + dp[1][K])
    


if __name__ == "__main__":
    main()

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

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

for l in range(n):
    for m in range(k + 1):
        for o in range(2):
            nd = int(s[l])
            for d in range(10):
                nl, nm, no = l + 1, m, o
                if d != 0:
                    nm += 1
                if nm > k:
                    continue
                if 0 == o:
                    if d > nd:
                        continue
                    if d < nd:
                        no = 1
                dp[nl][nm][no] += dp[l][m][o]
print(sum(dp[-1][-1]))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

    for i in range(n_len):
        ni = int(N[i])
        for isLess in [0, 1]:
            for not_0 in range(K+1):
                num = 10 if isLess else ni + 1
                dp[i+1][isLess or 0 < ni][not_0] += dp[i][isLess][not_0]
                for j in range(1, num):
                    dp[i+1][isLess or j < ni][not_0+1] += dp[i][isLess][not_0]

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

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
K = int(input())
from functools import lru_cache

@lru_cache(maxsize=1000)
def dp(n, k): 
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

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

dig=len(str(N))

dp=[[[0,0,0,0] for _ in range(2)] for i in range(dig+1)]


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


for i in range(1,dig):
    for j in range(2):
        if j==0:
            dp[i+1][j][0]=dp[i][j][0]
            dp[i+1][j][1]+=dp[i][j][0]*9+dp[i][j][1]
            dp[i+1][j][2]+=dp[i][j][1]*9+dp[i][j][2]
            dp[i+1][j][3]+=dp[i][j][2]*9+dp[i][j][3]
        if j==1:
            if N[i]=="0":
                for k in range(4):
                    dp[i+1][j][k]=dp[i][j][k]
            else:
                
                dp[i+1][j][1]=dp[i][j][0]
                dp[i+1][j][2]=dp[i][j][1]
                dp[i+1][j][3]=dp[i][j][2]
                
                
                n=int(N[i])
                dp[i+1][j-1][1]+=dp[i][j][0]*(n-1) + dp[i][j][1]
                dp[i+1][j-1][2]+=dp[i][j][1]*(n-1) + dp[i][j][2]
                dp[i+1][j-1][3]+=dp[i][j][2]*(n-1) + dp[i][j][3]
                
            
ans=dp[-1][0][K]+dp[-1][1][K]
print(ans)

Solution (Python):
dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(105)]

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

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, nj, nk = i + 1, j, k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if 0 == k:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
print(dp[n][K][0] + dp[n][K][1])

Solution (Python):
N = int(input())
K = int(input())
def dp(n, k): 
  if k == 0:
    return 1
  elif n == 0:
    return 0
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    m, fdigit = divmod(n,10)
    if m >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

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


dp1 = [[0] * (K+1) for _ in range(L+1)]
dp2 = [[0] * (K+1) for _ in range(L+1)]
for i in range(L+1):
    dp1[i][0] = 1
    for j in range(1, K+1):
        dp1[i][j] = dp1[i-1][j] + dp2[i-1][j]
        dp2[i][j] = 9 * (dp1[i-1][j-1] + dp2[i-1][j-1])
ans = dp1[L][K] + dp2[L][K]
d = K
for i in range(L):
    if N[i] != '0':
        ans -= dp2[L-i][d] * (9-int(N[i])) // 9
        d -= 1
    else:
        ans -= dp2[L-i][d]
    if d == 0:
        break
print(ans)

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

Solution (Python):



def ans(n,k):
  s=str(n)
  a=len(s)
  b=int(s[0])
  if(k==1):
    return 9*(a-1)+b
  elif(k==2):
    return int(81*(a-1)*(a-2)/2)+9*(b-1)*(a-1)+ans(n-b*10**(a-1),1)
  else:
    return int(729*(a-1)*(a-2)*(a-3)/6)+int(81*(b-1)*(a-1)*(a-2)/2)+ans(n-b*10**(a-1),2)

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

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


digit_N=len(N_str)


dp_eq=[]
dp_ne=[]
for i in range(digit_N):
  dp_eq.append([0]*(K+1))
  dp_ne.append([0]*(K+1))


dp_eq[0][1]=1
dp_ne[0][1]=int(N_str[0])-1
for i in range(digit_N):
  dp_ne[i][0]=1

for j in range(1,digit_N):
  digit=int(N_str[j])
  for k in range(1,K+1):
    if digit==0:
      dp_ne[j][k]=dp_ne[j-1][k]+9*dp_ne[j-1][k-1]
      dp_eq[j][k]=dp_eq[j-1][k]
    else:
      dp_ne[j][k]=dp_ne[j-1][k]+9*dp_ne[j-1][k-1]+dp_eq[j-1][k]+(digit-1)*dp_eq[j-1][k-1]
      dp_eq[j][k]=dp_eq[j-1][k-1]
    
print(dp_ne[-1][K]+dp_eq[-1][K])

Solution (Python):
s=input()+"9";n=len(s);X=[0]*4;Y=[0]*4;
while n:
 n-=1;k=4
 while k:k-=1;a=int(s[n]);Y[k],X[k]=(X[k]+(a-1)*X[k-1]+Y[k-1]if a else Y[k],X[k]+9*X[k-1])if k else (1,1)
print(Y[int(input())])

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

X = str(N)

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

for i in range(len(X)):
    D = int(X[i])
    for j in range(2):
        for k in range(K + 1):
            for d in range((9 if j == 1 else D) + 1):
                if k + int(d != 0) <= K:
                    dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k] 
print(dp[-1][0][-1]+dp[-1][1][-1])

Solution (Python):
def main():
    a = input()
    b = int(input())
    n = len(a)

    dp = [[[0 for _ in range(2)] for _ in range(b+1)] for _ in range(n+1)]
    dp[0][0][0] = 1

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

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


main()

Solution (Python):
import math

def comb(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) / 6

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) * math.pow(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 int(zero + aida + icchi)

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

print(solve(0, K, False))

Solution (Python):
s=input()+"9";n=len(s);X=[(0,0)]*4;
while n:
 n-=1;k=4
 while k:k-=1;a=int(s[n]);X[k]=(X[k][0]+9*X[k-1][0],X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if a else X[k][1])if k else(1,1)
print(X[int(input())][1])

Solution (Python):
n=int(input())
m=len(str(n))
k=int(input())
N=[int(i) for i in str(n)]
dp0=[[0]*(k+1) for _ in range(m+1)]
dp1=[[0]*(k+1) for _ in range(m+1)]
dp1[0][0]=1
for i,e in enumerate(str(n)):
    e = int(e)
    for j in range(k+1):
        dp1[i+1][j]+=dp1[i][j]*(e==0)
        dp0[i+1][j]+=dp0[i][j]+dp1[i][j]*(e!=0)
        if j<k:
            dp1[i+1][j+1]+=dp1[i][j]*(e!=0)
            dp0[i+1][j+1]+=dp0[i][j]*9+dp1[i][j]*max(0,e-1)
print(dp1[m][k]+dp0[m][k])

Solution (Python):
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  X[k]=(X[k][0]+9*X[k-1][0],X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if a else X[k][1])if k else(1,1)
print(X[int(input())][1])

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

Solution (Python):
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  X[k]=(X[k][0]+9*X[k-1][0]if k else 1,(X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if k else 1)if a else X[k][1])
print(X[int(input())][1])

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):
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  if k>j+1:X[k]=(0,0)
  else:X[k]=(X[k][0]+9*X[k-1][0]if k else 1,(X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if k else 1)if a else X[k][1])
print(X[int(input())][1])

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

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

print(ans)

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

dp0=[[0]*(k+2) for i in range(len(n)+1)]

dp1=[[0]*(k+2) for i in range(len(n)+1)]
dp1[0][0]=1


for i in range(len(n)):
    for j in range(k+1):
        x=int(n[i])
        if x!=0:
            
            dp0[i+1][j]+=dp0[i][j]+dp1[i][j]
            
            dp0[i+1][j+1]+=dp0[i][j]*9
            if dp1[i][j]!=0:
                dp0[i+1][j+1]+=x-dp1[i][j]
            dp1[i+1][j+1]+=dp1[i][j]
        else:
            
            dp0[i+1][j]+=dp0[i][j]
            dp1[i+1][j]+=dp1[i][j]
            
            dp0[i+1][j+1]+=dp0[i][j]*9

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

Solution (Python):



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

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




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


for l in range(L):
    a = int(N[l])
    for isless in [0, 1]:
        for k in range(4):
            for num in range(10):
                
                if num < a:
                    if num != 0:
                        dp[l+1][k+1][1] += dp[l][k][isless]
                    else:
                        dp[l+1][k][1] += dp[l][k][isless] 
                
                
                elif num == a or isless:
                    if num != 0:
                        dp[l+1][k+1][isless] += dp[l][k][isless]
                    else:
                        dp[l+1][k][isless] += dp[l][k][isless]




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

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


cnt=0
for l in range(1,L):
    if int(N[l-1])!=0:
        cnt+=1
    if cnt>3:
        break
    else:
        dp[0][cnt][l]=1










for i in range(1,L):
    for j in range(1,4):
        dp[1][j][i]+=dp[1][j-1][i-1]*9
        dp[1][j][i]+=dp[1][j][i-1]
        if int(N[i-1])>0:
            dp[1][j][i]+=dp[0][j][i-1]
            dp[1][j][i]+=dp[0][j-1][i-1]*(int(N[i-1])-1)
            

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

Solution (Python):
from functools import lru_cache

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

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

print(dp(N, K))

Solution (Python):
s=input()*2;n=len(s)/2
def f(i,t,k):
 if k>n-i:return 0
 a=max(t,int(s[i]));i+=1;
 if t:return f(i,9,k)+a*f(i,9,k-1)if k else 1
 else:return(f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,0,k-1)if k else 1)if a else f(i,0,k)
print(f(0,0,int(input())))

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

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(10001)]

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
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

ans = dp[n][K][0] + dp[n][K][1]

print(ans)

Solution (Python):
s=input();n=len(s)
def f(i,t,k):
 if k>n-i:return 0
 a=max(t,int(s[i]));i+=1;
 return(f(i,9,k)+(a-1)*f(i,9,k-1)+f(i,t,k-1)if k-1 else a+(n-i)*9)if a else f(i,t,k)
print(f(0,0,int(input())))

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

n = [int(i) for i in input()]
l = len(n)
k = int(input())
count = 0
for i in range(l):
  if n[i] > 0:
    
    count += 9 ** k * comb(l-i-1, k)
    
    if k >= 1:
      count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
    else:
      break
    
    k -= 1
  if i == l-1 and k == 0:
    count += 1
print(count)

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

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

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

for i in range(len(N)):
  n = int(N[i])
  for j in range(K+1):
    for ltn in range(2):
      for x in range(10 if ltn else n+1):
        if j + (x > 0) > K : continue
        dp[i+1][j + (x > 0)][ltn | (x < n)] += dp[i][j][ltn]

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

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

n = len(s)

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


for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])
            for 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 = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

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

count = len(N)

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

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

for i in range(count):
    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 = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

L=len(str(N))
ans=0
if L-1>=K:
    ans=cmb(L-1,K)*(9**K)

List=[]
for i in range(1,10):
    List.append(i*10**(L-1))

import sys
if K==1:
    for i in List:
        if i<=N:
            ans+=1
        else:
            print(ans)
            sys.exit()
    print(ans)
elif K==2:
    for i in List:
        for j in range(L-1):
            for k in range(1,10):
                T=i+k*10**j
                if T<=N:
                    ans+=1
                else:
                    print(ans)
                    sys.exit()
    print(ans)
elif K==3:
    for i in List:
        for j in range(L):
            for k in range(j+1,L-1):
                T=i+9*10**j+9*10**k
                if T<=N:
                    ans+=81
                else:
                    for l in range(1,10):
                        for m in range(1,10):
                            T=i+m*10**j+l*10**k
                            if T<=N:
                                ans+=1
                            else:
                                continue
    print(ans)
else:
    print(0)

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

def rec(N,K):
    if K==0:
        return 1

    if len(N)<K:
        return 0
    
    lsb=int(N[-1])

    if len(N)==1:
        return lsb
   
    return rec(N[:-1],K-1)*(lsb)+rec(str(int(N[:-1])-1),K-1)*(9-lsb)+rec(N[:-1],K)
    
print(rec(N,K))

Solution (Python):


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

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

    for i, c in enumerate(S):  
        for j in range(K + 1):  
            for k in range(2):  
                nd = int(c)
                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 > nd: continue  
                        if d < nd: nk = 1  
                    dp[ni][nj][nk] += dp[i][j][k]

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


if __name__ == '__main__':
    main()

Solution (Python):
n,k=open(0)
k=int(k)
d=[1]+[0]*7
for n in map(int,n[:-1]):
  p=[0]*8
  for i in range(n):
    if i<1:
      for j in range(4):
        p[j+4]+=d[j]
    else:
      for j in range(3):
        p[j+5]+=d[j]
  for i in range(10):
    if i<1:
      for j in range(4):
        p[j+4]+=d[j+4]
    else:
      for j in range(3):
        p[j+5]+=d[j+4]
  if n<1:
    for i in range(4):
      p[i]+=d[i]
  else:
    for i in range(3):
      p[i+1]+=d[i]
  d=p
print(sum(d[k::4]))

Solution (Python):
n,k=open(0)
k=int(k)
d=[1]+[0]*7
for n in map(int,n[:-1]):
  p=[0]*8
  for i in range(n):
    if i<1:
      for j in range(4):
        p[j+4]+=d[j]
    else:
      for j in range(3):
        p[j+5]+=d[j]
  for i in range(10):
    if i<1:
      for j in range(4):
        p[j+4]+=d[j+4]
    else:
      for j in range(3):
        p[j+5]+=d[j+4]
  if n<1:
    for i in range(4):
      p[i]+=d[i]
  else:
    for i in range(3):
      p[i+1]+=d[i]
  d=p
print(sum(d[k::4]))

Solution (Python):
from functools import lru_cache
N = int(input())
K = int(input())

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

print(f(N, K))

Solution (Python):
import sys
input = sys.stdin.readline
n = input().strip()
k = int(input())
l = len(n)

dp = [[[0] * (k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][1][0] = 1
for i, s in enumerate(n, start=1):
    s = int(s)
    for j in range(10):
        if j == 0:
            if j < s:
                for x in range(k+1):
                    dp[i][0][x] += dp[i-1][0][x] + dp[i-1][1][x]
            elif j == s:
                for x in range(k+1):
                    for y in range(2):
                        dp[i][y][x] += dp[i-1][y][x]
        elif j < s:
            for x in range(k):
                dp[i][0][x+1] += dp[i-1][0][x] + dp[i-1][1][x]
        elif j == s:
            for x in range(k):
                for y in range(2):
                    dp[i][y][x+1] += dp[i-1][y][x]
        else:
            for x in range(k):
                dp[i][0][x+1] += dp[i-1][0][x]
print(dp[-1][0][k] + dp[-1][1][k])

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

def search(d, k, isLess):
    if k == K:
        return 1
    if d == len(N):
        return 0

    ret = search(d + 1, k, isLess or int(N[d]) > 0)

    if k < K:
        if isLess:
            ret += search(d + 1, k + 1, True) * 9
        elif int(N[d]) > 0:
            ret += search(d + 1, k + 1, True) * (int(N[d]) - 1) + search(d + 1, k + 1, False)

    return ret

ans = search(0, 0, False)
print(ans)

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 i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    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):
import numpy as np

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

keta = len(S)

ans = 0
if keta < K:
    print(ans)
    exit()

dp = np.zeros((keta+2,4,2), dtype = int)
dp[0][0][0] = 1
for i in range(keta):
    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
                    if d < nd: nk=1
                dp[ni][nj][nk] += dp[i][j][k]

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

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

MOD = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


for i in range(2, 10 ** 6):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)


def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD

def rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    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))