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 main():
    n = input()
    k = int(input())

    print(tmp(n, k))

def tmp(x, k):
    
    if len(x) < k:
        return 0
    
    if k <= 0:
        return 1
    if len(x) == k == 1:
        return int(x)
    else:
        int_x = list(map(int, list(x)))
        next_x = str(int(x[1:]))

        
        a = tmp(next_x, k-1)
        
        b = (int_x[0]-1) * pow(9, k-1) * combination(len(x)-1, k-1)
        
        c = pow(9, k) * combination(len(x)-1, k)

        return a + b + c

def combination(n, k):
    m = 1
    l = 1
    for i in range(n, n-k, -1):
        m = m * i

    for j in range(k, 0, -1):
        l = l * j
    
    return int(m / l)

if __name__ == "__main__":
    main()

Solution (Python):
from functools import lru_cache
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


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


@lru_cache(None)
def rec(i, k, yn):
    if k == 0:
        return 1
    elif i == n:
        return 0
    if n - i < k:
        return 0

    if yn:
        
        return cmb(n - i, k) * pow(9, k)
    else:
        if N[i] == 0:
            return rec(i + 1, k, False)
        else:
            a = rec(i + 1, k, True)
            b = rec(i + 1, k - 1, True) * (N[i] - 1)
            c = rec(i + 1, k - 1, False)
            return a + b + c


answer = rec(0, K, False)
print(answer)

Solution (Python):
N = input()
K = int(input())
N = "0" + N
K = int(K)

L = len(N)

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

for i in range(1, L):
    d = int(N[i])
    
    for k in range(0, K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if d != 0:
            dp[i][1][k] += dp[i - 1][0][k]

    for k in range(1, K + 1):
        dp[i][1][k] += dp[i - 1][1][k - 1] * 9
        if d != 0:
            dp[i][1][k] += dp[i - 1][0][k - 1] * (d - 1)
            dp[i][0][k] += dp[i - 1][0][k - 1]
        else:
            dp[i][0][k] += dp[i - 1][0][k]

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

Solution (Python):
import sys


def main():
    N = str(input())
    K = int(input())
    
    l = len(N)
    dpa = [[0 for _ in range(K+1)] for _ in range(l)]
    dpb = [[0 for _ in range(K+1)] for _ in range(l)]
    
    dpa[0][0],dpa[0][1],dpb[0][1] = 1,int(N[0])-1,1
    for i in range(1,l):
        dpa[i][0] = 1
        num = int(N[i])
        if num == 0:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j]
                dpb[i][j] = dpb[i-1][j]
        else:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j] + dpb[i-1][j-1]*(num-1) + dpb[i-1][j]
                dpb[i][j] = dpb[i-1][j-1]

    print(dpa[l-1][K]+dpb[l-1][K])

if __name__ == "__main__":
    main()

Solution (Python):
import sys

import copy

def main():
    N = str(input())
    K = int(input())
    
    l = len(N)
    dpa = [[0 for _ in range(K+1)] for _ in range(l)]
    dpb = copy.deepcopy(dpa)
    
    dpa[0][0],dpa[0][1],dpb[0][1] = 1,int(N[0])-1,1
    for i in range(1,l):
        dpa[i][0] = 1
        num = int(N[i])
        if num == 0:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j]
                dpb[i][j] = dpb[i-1][j]
        else:
            for j in range(K):
                j += 1
                dpa[i][j] = dpa[i-1][j-1]*9 + dpa[i-1][j] + dpb[i-1][j-1]*(num-1) + dpb[i-1][j]
                dpb[i][j] = dpb[i-1][j-1]

    print(dpa[l-1][K]+dpb[l-1][K])

if __name__ == "__main__":
    main()

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

n = len(s)

dp = [[[0] * 2 for _ in range(4)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(4):
        for k in range(2):
            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):
import itertools
import sys
import numpy as np
from collections import deque
from itertools import combinations
from functools import lru_cache
sys.setrecursionlimit(10**9)

@lru_cache(None)
def solve(N,K):
    
    if N <= 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0

    if K < 0 or len(str(N)) < K:
        return 0

    ans = 0
    m, last = divmod(N,10)
    ans += solve(m,K-1) * last + solve(m-1,K-1) * (9 - last) + solve(m,K)

    return ans


def main():
    N,K = map(int,[input(),input()])

    print(solve(N,K))

if __name__ == "__main__":
  main()

Solution (Python):
import sys
sys.setrecursionlimit(500)


def calc(N, K):
    if len(N) < K or K <= 0:
        return 0
    tmp = 9 - int(N[0])
    for i in range(K-1):
        tmp *= 9 * (len(N) - 1 - i)
    for i in range(K-1):
        tmp //= (i+1)
    if N[0] != "0":
        return tmp + calc(N[1:], K-1)
    else:
        return tmp + calc(N[1:], K)


def main():
    N = input()
    K = int(input())
    if len(N) < K:
        print(0)
        return
    ans = 1
    for i in range(K):
        ans *= 9 * (len(N) - i)
    for i in range(K):
        ans //= (i+1)
    ans -= calc(N, K)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
def permutations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // factorial(n - r)
def combinations_count(n, r):
    if not n>=r>=0 or n<0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())
length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if K-count3 >=1:count+=combinations_count(length-1-i,K-count3)*(9**(K-count3))
        if K-count3-1 >=0:count+=combinations_count(length-1-i,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        count3+=1
    if K-count3==0:
        count+=1
        
        break
print(count)

Solution (Python):
N=input()
K=int(input())
S="0"*(100-len(N))+N
DP=[[[0]*2 for _ in range(K+2)] for _ in range(101)]

DP[0][0][0] = 1
for i in range(100):
  for j in range(K+1):
    
    if S[i]=='0':
      DP[i+1][j][0]+=DP[i][j][0]
      
    
    else:
      DP[i+1][j+1][0]+=DP[i][j][0]
    
    
    DP[i+1][j][1]+= DP[i][j][1]
    if int(S[i])>0:
      
      DP[i+1][j][1]+=DP[i][j][0]
      
    
    DP[i+1][j+1][1] += DP[i][j][1]*9+DP[i][j][0]*(max(0, int(S[i])-1))
print(sum(DP[-1][K]))

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

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

Solution (Python):
import math

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def count(num_str,k):
    digits = len(num_str)
    if digits == 0:
        return 0
    else:
        if k == 0:
            
            return 1
        if num_str[0] == '0':
            
            return count(num_str[1:],k)
        else:
            if digits == 1 and k == 1:
                
                return int(num_str)
            elif digits == 1 and k > 1:
                
                return 0
            if digits >= k+1:
                count_0 = combinations_count(digits-1,k)*(9**k)
            else:
                count_0 = 0
            count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
            
        return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(n),k))

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

Nstr = str(N)

l = len(Nstr)

DP = [[[0]*2 for j in range(K+1)] for i in range(l+1)]

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

for i in range(l):
    if int(Nstr[i])==0:
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0]
            DP[i+1][j][1] += DP[i][j][1]
            if j>0:
                DP[i+1][j][0] += 9*DP[i][j-1][0]
    else:
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0]+DP[i][j][1]
            if j>0:
                DP[i+1][j][0] += (int(Nstr[i])-1)*DP[i][j-1][1]+9*DP[i][j-1][0]
                DP[i+1][j][1] += DP[i][j-1][1]

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

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

Nstr = str(N)
Nlen = len(Nstr)

'''------dp設定-------
dp[i][j][k] 
dp[][][] 
i:桁数
j:非0の数を使った回数
k: 0:それまでの桁数は、Nと同じ
   1:それまでの桁数で、Nより小さいが確定
配るdpで更新
'''


dp = [[[0 for i3 in range(2)] for i2 in range(K+1)] for i1 in range(Nlen+1)]
dp[0][0][0] = 1


for i in range(Nlen):
    for j in range(4):
        for k in range(2):
            nd = int(Nstr[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]

print(dp[Nlen][K][0]+dp[Nlen][K][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 in range(m):
  for j in range(k+1):
    dp1[i+1][j]+=dp1[i][j]*(N[i]==0)
    dp0[i+1][j]+=dp0[i][j]+dp1[i][j]*(N[i]>0)
    if j<k:
      dp1[i+1][j+1]+=dp1[i][j]*(N[i]>0)
      dp0[i+1][j+1]+=dp0[i][j]*9+dp1[i][j]*max(0,N[i]-1)
print(dp1[m][k]+dp0[m][k])

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

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

dp[0][0][0]=1
keta=int(n[0])
dp[1]=[[0,1],[1,keta-1],[0,0],[0,0]]
  
for i in range(1,m):
  keta=int(n[i])
  dp[i+1][0][0]+=dp[i][0][0]*(keta==0)
  dp[i+1][0][1]+=(dp[i][0][0]*(keta>0)+dp[i][0][1])
  for j in range(3):
    dp[i+1][j+1][0]+=dp[i][j][0]*(keta!=0)+dp[i][j+1][0]*(keta==0)
    dp[i+1][j+1][1]+=(dp[i][j][0]*max(keta-1,0)+dp[i][j][1]*9
                      +dp[i][j+1][0]*(keta>0)+dp[i][j+1][1])
    
                    
print(dp[m][k][0]+dp[m][k][1])

Solution (Python):


from math import factorial

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

def cmb(a, b):
    c = a - b
    if c < b:
        b = c
    if b == 0: return 1

    ans = 1
    for i in range(b):
        ans *= a - i

    return ans // factorial(b)

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

    n10 = 10 ** (K-1)
    if N < n10:
        return 0

    n10 *= 10
    n9 = 9 ** K

    ans = 0
    a = n10
    i = 0
    while a < N:
        a *= 10; i += 1
    a //= 10; i -= 1
    if i >= 0:
        ans = cmb(i+K, K) * n9
        

    n, b = divmod(N, a)
    if n > 1:
        ans += (n - 1) * cnt(a-1, K - 1)
    ans += cnt(b, K - 1)


    return ans

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

    print(cnt(N, K))

if __name__ == "__main__":
    resolve()

Solution (Python):
from functools import lru_cache
N = int(input())
K = int(input())
@lru_cache(None)
def F(N,K):

  if N<10:
    if K==0:
      return 1
    if K==1:
      return N
    return 0
  p, q = divmod(N,10)
  ret = 0
  if K>0:
    ret += F(p,K-1) * q
    ret += F(p-1,K-1) * (9-q)
  ret += F(p,K)
  return ret
print(F(N,K))

Solution (Python):
N = int(input())
K = int(input())
A = 0
keta = len(str(N))
if K ==1:
    A = 9*(keta-1)
if K ==2:
    A = 9*9*(keta-1)*(keta-2)//2
if K ==3:
    A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
nc = 1

while nc <= 3 and keta >=1:
        
    T = N//(10**(keta-1))%10

    if T == 0:
        keta -=1
    else:
        if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
            A = A + (T)
        if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
            A = A + int((T-1)*9*(keta-1))
        if (nc==2 and K==2) or (nc==3 and K==3):
            A = A + 9*(keta-1)
        if (nc==1 and K ==3):
            A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
        if (nc==2 and K==3):
            A = A + int(9*9*(keta-1)*(keta-2)/2)
        nc +=1
        keta -=1

        
print(A)

Solution (Python):





def solv(N, K):
    
    
    if K == 0:
        
        return 1
    
    if len(N) < K:
        
        return 0

    
    count = 0

    
    
    
    if N[0] > 1:
        count += (N[0]-1) * solv([9] * (len(N)-1), K-1)
    
    if N[0] > 0:
        count += solv(N[1:], K-1)
    
    if N[0] == 0:
        count += solv(N[1:], K)
    else:
        count += solv([9] * (len(N)-1), K)

    
    return count


if __name__ == "__main__":

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

    print(ans)

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


DP = [[0]*(k+3), [0]*(k+3)]
DP[0][0] = 1

for num in n:
    num = int(num)

    for num_count in range(k+1, -1, -1):
        DP[1][num_count] += DP[1][num_count-1] * 9 + DP[0][num_count-1] * max(0, num-1)

        if num != 0:
            DP[0][num_count] = DP[0][num_count-1] * 1
            DP[1][num_count-1] += DP[0][num_count-1]
            DP[0][num_count-1] = 0

        else:
            continue

ans = DP[1][k] + DP[0][k]
print(ans)

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):
from functools import lru_cache
N = int(input())
K = int(input())

@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,K))

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    N = Scanner.string()
    K = Scanner.int()
    M = len(N)
    dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(M + 1)]
    dp[0][0][0] = 1
    for i in range(M):
        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:
                            nk = 1
                        if d > nd:
                            continue
                    dp[ni][nj][nk] += dp[i][j][k]
    ans = dp[M][K][0] + dp[M][K][1]
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
n=input()
k=int(input())
lenn=len(n)
dp=[[[0]*2 for i in range(k+1)] for j in range(lenn)]
dp[0][1][1]+=int(n[0])-1
dp[0][0][1]+=1
dp[0][1][0]+=1
for i in range(1,lenn):
  keta=int(n[i])
  for j in range(k):
    dp[i][j+1][1]+=dp[i-1][j][1]*9
    dp[i][j][1]+=dp[i-1][j][1]
    if keta>0:
      dp[i][j+1][1]+=dp[i-1][j][0]*(keta-1)
      dp[i][j+1][0]+=dp[i-1][j][0]
      dp[i][j][1]+=dp[i-1][j][0]
    else:
      dp[i][j][0]+=dp[i-1][j][0]
  dp[i][k][1]+=dp[i-1][k][1]
  if keta>0:
    dp[i][k][1]+=dp[i-1][k][0]
  else:
    dp[i][k][0]+=dp[i-1][k][0]
print(dp[lenn-1][k][1]+dp[lenn-1][k][0])

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

Solution (Python):
N=input()
K=int(input())
M=len(N)
dp=[[[0]*(K+1) for i in (0,1)] for j in range(M+1)]
dp[0][0][0]=1

for i in range(M):
   for smaller in (0,1):
      for no_zero_number in range(K+1):
         for x in range(10):
            
            
            
            
            
            if smaller==0 and x>int(N[i]):
               continue
            if x==0:
               dp[i+1][smaller or x<int(N[i])][no_zero_number]+=dp[i][smaller][no_zero_number]
            else:
               if no_zero_number+1>K:
                  continue
               else:
                  dp[i+1][smaller or x<int(N[i])][no_zero_number+1]+=dp[i][smaller][no_zero_number]
            

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

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

s = input()
k = int(input())
print(f(s, 0, k))

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

X = str(N+1)

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(10 if j == 1 else D+1):
                if k + (d != 0) <= K:
                    dp[i+1][j | (d<D)][k+(d != 0)] += dp[i][j][k]


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

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


def main(d, k):
    if d == L:
        if k == 0:
            return 1
        else:
            return 0
    if N[d] == "0":
        return main(d + 1, k)
    if (L - d) < k:
        return 0
    if k == 0:
        return 1
    return main1(d+1, k)+main1(d+1, k-1)*(int(N[d])-1)+main(d+1, k-1)


lmain1 = [[-1 for j in range(K+1)] for i in range(L+1)]


def main1(d, k):
    if d == L:
        if k == 0:
            return 1
        else:
            return 0
    if k == 0:
        return 1
    if lmain1[d][k] != -1:
        return lmain1[d][k]
    ret = main1(d+1, k-1)*9+main1(d+1, k)
    lmain1[d][k] = ret
    return ret


print(main(0, K))

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

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

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

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

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

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

for i in range(1, digit):
    dp[i][1][0] = 1
    for k in range(1, K+1):
        di = int(N[i])
        if di == 0:
            dp[i][0][k] = dp[i-1][0][k]
            dp[i][1][k] = dp[i-1][1][k] + dp[i-1][1][k-1]*9
        else:
            dp[i][0][k] = dp[i - 1][0][k - 1]
            dp[i][1][k] = dp[i-1][0][k-1]*(di-1)+dp[i-1][0][k]\
                      +dp[i-1][1][k]+dp[i-1][1][k-1]*9


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

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

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

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

for i in range(len(str(n))):
    for j in range(k+1):
        for m in range(2):
            nd = int(str(n)[i])
            for l in range(10):
                ni = i+1
                nj = j
                nm = m
                if l != 0:
                    nj += 1
                if nj > k:
                    continue
                if nm == 0:
                    if  l > nd:
                        continue
                    elif l < nd:
                        nm = 1
                dp[ni][nj][nm] += dp[i][j][m]
print(dp[len(str(n))][k][0]+dp[len(str(n))][k][1])

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

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

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

for i in range(1, digit):
    for k in range(K+1):
        cd = int(N[i])
        if k == 0:
            dp[i][1][0] = 1
        else:
            if cd == 0:
                dp[i][0][k] = dp[i-1][0][k]
                dp[i][1][k] = dp[i-1][1][k] + dp[i-1][1][k-1]*9
            else:
                dp[i][0][k] = dp[i - 1][0][k - 1]
                dp[i][1][k] = dp[i-1][0][k-1]*(cd-1)+dp[i-1][0][k]\
                          +dp[i-1][1][k]+dp[i-1][1][k-1]*9


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

Solution (Python):


from functools import lru_cache


@lru_cache(None)
def F(N, K):
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        else:
            return 0
    
    q,r = divmod(N,10)

    ans = 0
    if K >= 1:
        
        ans += F(q, K-1) * r
        ans += F(q-1, K-1) * (9-r)
    
    ans += F(q, K)
    
    return ans

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

    print(F(N,K))

if __name__ == "__main__":
    main()

Solution (Python):
N = input()
L = len(N)
K = int(input())
dp = [[[0 for k in range(2)]for j in range(K+1)]for i in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
    p = int(N[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for d in range(10):
                nk = k
                nj = j
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if nk == 0:
                    if d > p:
                        continue
                    if d < p:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
print(dp[L][K][0]+dp[L][K][1])

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    K = int(f_i.readline())
    S = str(N)
    
    
    import numpy as np
    
    dp = np.zeros((len(S) + 1, 2, K + 1), dtype=int)
    dp[0][0][0] = 1
    digits = (int(c) for c in S)
    
    for i, d in enumerate(digits):
        for j in (0, 1):
            for k in range(K):
                if j:
                    dp[i+1][j][k+1] += dp[i][j][k] * 9
                    dp[i+1][j][k] += dp[i][j][k]
                else:
                    if d:
                        dp[i+1][1][k+1] += dp[i][j][k] * (d - 1)
                        dp[i+1][j][k+1] += dp[i][j][k]
                        dp[i+1][1][k] += dp[i][j][k]
                    else:
                        dp[i+1][j][k] += dp[i][j][k]
                    
    ans = np.sum(dp[:, :, K])
    
    print(ans)

solve()

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

from math import factorial

str_n = str(N)
len_n = len(str(str_n))

def conb(n, r):
    return factorial(n)//factorial(r)//factorial(n-r)
    
def get_num(top, k_val, depth):
    if k_val==0:
        return 1
    elif k_val>(len_n-depth+1):
        return 0
    elif top:
        if int(str_n[depth - 1])==0:
            return get_num(top, k_val, depth + 1)
        else:
            b1 = get_num(top, k_val - 1, depth + 1)
            b2 = (int(str_n[depth-1])-1) * get_num(False, k_val-1, depth+1)
            b3 = get_num(False, k_val, depth + 1)
            return b1+b2+b3
    else:
        return 9**(k_val) * conb(len_n - depth + 1, k_val)
    
    
a1 = get_num(True, K-1, 2)
a2 = (int(str_n[0])-1)*get_num(False, K-1, 2)
a3 = get_num(False, K, 2)


print(a1+a2+a3)

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve_1(N):
    N_str = str(N)
    ans = 0
    for i, ch in enumerate(N_str):
        if i == 0:
            ans += int(ch)
        else:
            ans += 9
    return ans

def solve_2(N):
    N_str = str(N)

    

    
    
    ans = (int(N_str[0]) - 1) * 9 * (len(N_str) - 1)

    
    
    
    
    
    
    
    
    flag = False
    for ch in N_str[1:]:
        if flag:
            ans += 9
        else:
            ans += int(ch)
            if ch != '0':
                flag = True

    
    
    for i in range(1, len(N_str) - 1):
        ans += 81 * i

    return ans

def solve_slow_2(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 2
    return ans











def solve_3(N):
    N_str = str(N)
    size = len(N_str)

    

    
    
    ans = (int(N_str[0]) - 1) * (((size - 1) * (size - 2)) // 2) * 81

    
    
    if size > 1:
        ans += solve_2(int(N_str[1:]))

    
    
    
    
    
    
    
    
    for size in range(1, len(N_str)):
        ans += 9 * 9 * 9 * (size - 1) * (size - 2) // 2

    return ans

def solve_slow_3(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 3
    return ans










        

def solve(N, K):
    if K == 1:
        return solve_1(N)
    elif K == 2:
        return solve_2(N)
    else:
        return solve_3(N)


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

print(solve(N, K))

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

from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, K = [int(sys.stdin.buffer.readline()) for _ in range(2)]
N = str(N)


@lru_cache(maxsize=None)
def solve(d, k):
    
    if d <= 0:
        return 0
    if k == 0:
        return 1
    n = int(N[-d])
    if d == 1:
        if k == 0:
            return 1
        elif k == 1:
            return n
        else:
            return 0
    if n == 0:
        return solve(d - 1, k)
    ret = 0
    
    ret += solve(d - 1, k - 1)
    
    ret += comb(d - 1, k - 1, exact=True) * (n - 1) * 9 ** (k - 1)
    
    ret += comb(d - 1, k, exact=True) * 9 ** k
    return ret


ans = solve(len(N), K)
print(ans)