Problem:
 Score : 500 points    Problem Statement Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.      Constraints  1 \leq N < 10^{100}  1 \leq K \leq 3         Input Input is given from Standard Input in the following format:  N  K       Output Print the count.        Sample Input 1 100
1      Sample Output 1 19  The following 19 integers satisfy the condition:   1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100        Sample Input 2 25
2      Sample Output 2 14  The following 14 integers satisfy the condition:   11,12,13,14,15,16,17,18,19,21,22,23,24,25        Sample Input 3 314159
2      Sample Output 3 937       Sample Input 4 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3      Sample Output 4 117879300

Solution (Python):
n=int(input())
k=int(input())
s=len(list(str(n)))
if k==1:
    ans=(s-1)*9
    for i in range(9):
        if n>=(10**(s-1))*(i+1):
            ans+=1
elif k==2:
    ans=9*9*(s-1)*(s-2)//2
    for i in range(9):
        for j in range(s-1):
            for p in range(9):
                if n>=(10**(s-1))*(i+1)+(10**j)*(p+1):
                    ans+=1
else:
    ans=9*81*(s-1)*(s-2)*(s-3)//6
    f=int(list(str(n))[0])
    ans+=(f-1)*81*(s-1)*(s-2)//2
    for p in range(s-1):
        for q in range(s-1):
            if p<q:
                for t in range(1,10):
                    for u in range(1,10):
                        if n>=(10**(s-1))*f+(10**p)*t+(10**q)*u:
                            ans+=1
print(ans)

Solution (Python):
def f(k, n):
    n_str = str(n)
    digit = len(n_str)
    head = int(n_str[0])
    rest = int(n_str[1:]) if digit > 1 else 0

    if k == 1:
        return 9*(digit-1) + head
    if k == 2:
        if n <= 10:
            return 0
        else:
            return 9 * (digit-1) * (head-1) + f(1,rest) + f(2, 10**(digit-1)-1)
    if k == 3:
        if n < 111:
            return 0
        else:
            return 9**2 * (digit-1)*(digit-2)//2 * (head-1) + f(2,rest) + f(3, 10**(digit-1)-1)


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

print(f(k,n))

Solution (Python):
import math

def comb(n, r):
	if n <= r:
		return 1
	else:
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def perm(n, r):
	if n <= r:
		return math.factorial(n)
	else:
		return math.factorial(n) // (math.factorial(n - r))
	
N = int(input())
K = int(input())
N_str = str(N)
N_keta = len(N_str)
N_f = int(N_str[0])

def K1(a):
	a_str = str(a)
	a_keta = len(a_str)
	a_f = int(a_str[0])
	return a_f + (a_keta-1)*9

def K2(a):
	a_str = str(a)
	a_keta = len(a_str)
	a_f = int(a_str[0])
	if a_keta < 2:
		return 0
	else:
		a_under1 = int(a_str[1:])
		a_list = [9*9*i for i in range(1, a_keta-1)]
		return (a_f-1)*9*(a_keta-1) + K1(a_under1) + sum(a_list)

if K == 1:	
	print(K1(N))

elif K == 2:
	print(K2(N))

elif K == 3:
	if N_keta < 3:
		print(0)
	else:
		N_under1 = int(N_str[1:])
		N_list = [9*9*9*comb(i, 2) for i in range(2, N_keta-1)]
		print(K2(N_under1) + (N_f-1)*9*9*comb(N_keta-1, 2) + sum(N_list))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = input()
m = len(n)
K = I()

dp1 = [[0]*4 for _ in range(m+1)] 
dp2 = [[0]*4 for _ in range(m+1)] 
dp1[0][0] = 1
for i in range(m):
    x = int(n[i])
    for j in range(10):
        if j == x:
            if j == 0:
                for k in range(4):
                    dp1[i+1][k] += dp1[i][k]
                    dp2[i+1][k] += dp2[i][k]
            else:
                for k in range(3):
                    dp1[i+1][k+1] += dp1[i][k]
                    dp2[i+1][k+1] += dp2[i][k]
        elif j < x:
            if j == 0:
                for k in range(4):
                    dp2[i+1][k] += dp1[i][k]
                    dp2[i+1][k] += dp2[i][k]
            else:
                for k in range(3):
                    dp2[i+1][k+1] += dp1[i][k]
                    dp2[i+1][k+1] += dp2[i][k]
        else:
            for k in range(3):
                dp2[i+1][k+1] += dp2[i][k]
ans = dp1[m][K] + dp2[m][K]
print(ans)

Solution (Python):
import numpy as np


def main():
    n = [int(x) for x in input()]
    K = int(input())
    dp = np.zeros((len(n)+1, 2, 5), dtype=int)

    if len(n) < K:
        print(0)
        return

    dp[0, 0, 0] = 1

    for i in range(len(n)):
        for k in range(K+1):
            
            if n[i] == 0:
                dp[i+1, 0, k] += dp[i, 0, k]
                dp[i+1, 1, k] += dp[i, 1, k]
            else:
                dp[i+1, 1, k] += dp[i, 0, k] + dp[i, 1, k]
            
            for x in range(1, 10):
                if x < n[i]:
                    
                    dp[i+1, 1, k+1] += dp[i, 0, k] + dp[i, 1, k]
                elif x == n[i]:
                    dp[i+1, 0, k+1] += dp[i, 0, k]
                    dp[i+1, 1, k+1] += dp[i, 1, k]
                else:
                    dp[i+1, 1, k+1] += dp[i, 1, k]
    print(dp[len(n), 0, K] + dp[len(n), 1, K])


if __name__ == '__main__':
    main()

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

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} 
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) 

def aaa(n,k):
    r = len(str(n))-1
    st = str(n)
    ans = 0
    if k==1 and r>=0:
        ans += 9**1 * comb(r, 1) \
               + int(st[0])
    else:
        ans += 9**k * comb(r, k) \
               + (int(st[0])-1) * 9**(k-1) * comb(r, k-1) \
               + aaa(n%(10**r), k-1)
    return ans

n = int(input())
k = int(input())
ans = aaa(n,k)
print(ans)

Solution (Python):
n = int(input())
k = int(input())
ans = 0
if k == 1:
    if n < 10:
        ans = n
    else:
        l = len(str(n))
        ans += 9 * (l - 1)
        ans += int(str(n)[0])
elif k == 2:
    if n < 11:
        ans = 0
    else:
        l = len(str(n))
        for i in range(2, l):
            ans += 9 * 9 * (i - 1)
        f = int(str(n)[0])
        ans += (f - 1) * 9 * (l - 1)
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        else:
            num = l - 1
            f = 0
        ans += f
        ans += 9 * (l - num - 1)
else:
    if n < 111:
        ans = 0
    else:
        l = len(str(n))
        
        
        ans += 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6

        
        f = int(str(n)[0])
        ans += (f - 1) * 9 * 9 * (l - 1) * (l - 2) // 2

        
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        else:
            num = l - 1
        ans += (f - 1) * (l - num - 1) * 9  
        ans += 9 * 9 * (l - num - 1) * (l - num - 2) // 2  

        
        for i in range(num + 1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        else:
            num = l - 1
            f = 0
        ans += (l - num - 1) * 9
        ans += f
print(ans)

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


def main(d, k):
    if (L - d) < k:
        return 0
    if N[d] == "0":
        return main(d + 1, k)
    if k == 1:
        return ((L - d) - 1) * 9 + int(N[d])
    elif k == 2:
        return (
            ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81
            + ((L - d) - 1) * 9 * (int(N[d]) - 1)
            + main(d + 1, k - 1)
        )
    elif k == 3:
        return (
            ((((L - d) - 1) * ((L - d) - 2) * ((L - d) - 3)) // 6) * (9 ** 3)
            + ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81 * (int(N[d]) - 1)
            + main(d + 1, k - 1)
        )


print(main(0, K))

Solution (Python):
n = int(input())
k = int(input())
R = len(str(n))
r = R - 1
q = 0
num = [0] * 4
index = [0] * 4
s = str(n)
for i in range(R):
    if s[i] != "0":
        num[q] = int(s[i])
        index[q] = i
        q += 1
    if q == 4:
        break

if k == 1:
    ans = 9 * r + num[0]
elif k == 2:
    ans = 81 * r * (r-1) // 2
    if num[1] != 0:
        pass
    else:
        num[0] -= 1
        num[1] = 9
        index[1] = 1
    ans += 9 * (R - 1) * (num[0] - 1) + num[1] + 9 * (R - index[1] - 1)
elif k == 3:
    ans = 243 * r * (r-1) * (r-2) // 2
    if num[2] != 0:
        pass
    elif num[1] != 0:
        num[1] -= 1
        index[2] = index[1] + 1
        num[2] = 9
    else:
        num[0] -= 1
        index = [0, 1, 2]
        num[1], num[2] = 9, 9
    ans += 81 * (R-1)*(R-2)*(num[0]-1)//2 + 9 * (R - index[1] - 1) * (num[1] - 1)
    ans += 81 * (R-index[1]-1)*(R-index[1]-2) // 2
    ans += 9 * (R - index[2] - 1) + num[2]
print(ans)

Solution (Python):
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
else:

    def main(d, k):
        if (L - d) < k:
            return 0
        if N[d] == "0":
            return main(d + 1, k)
        if k == 1:
            return ((L - d) - 1) * 9 + int(N[d])
        elif k == 2:
            return (
                ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81
                + ((L - d) - 1) * 9 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )
        elif k == 3:
            return (
                ((((L - d) - 1) * ((L - d) - 2) * ((L - d) - 3)) // 6) * (9 ** 3)
                + ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )

    print(main(0, K))

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

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} 
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) 

def aaa(n,k):
    r = len(str(n))-1
    st = str(n)
    ans = 0
    if k==1 and r>=0:
        ans += 9*r \
               + int(st[0])
    elif k==2 and r>=1:
        ans += 9**2 * comb(r, 2) \
               + (int(st[0])-1) * 9**1 * comb(r, 1) \
               + aaa(n%(10**r), k-1)
    elif k==3 and r>=2:
        ans += comb(r, 3)*9**3\
               +comb(r, 2)*9**2*(int(st[0])-1)\
               +aaa(n%(10**r), k-1)
    return ans

n = int(input())
k = int(input())
ans = aaa(n,k)
print(ans)

Solution (Python):


def f(N,k):
    if not N:
        return 0
    N = str(int(N))
    a = (len(N)-1)
    na = int(N[0])
    if k == 1:
        return str(9*a+na)
    if k == 2:
        return str(9**2*a*(a-1)//2 + (na-1)*int(f('9'*a,1)) + int(f(N[1:],1)))
    if k == 3:
        return str(9**3*a*(a-1)*(a-2)//6 + (na-1)*int(f('9'*a,2)) + int(f(N[1:],2)))

def solve():
    N = input()
    K = int(input())
    return f(N,K)
    
if __name__ == '__main__':
    print(solve())

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





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


def getMiman(X):
  if X>0:
    return X-1
  else:
    return 0

x0=int(N[0])

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

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

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

dp[0][1][1]=getMiman(x0)

for i in range(1,keta):
  
  x=int(N[i])
  
  dp[i][0][0]=0
  
  dp[i][1][0]=1
  for j in range(1,K+1):
    
    
    
    dp[i][0][j]=dp[i-1][0][j-1]*(x!=0)+dp[i-1][0][j]*(x==0)
    
    
    
    
    
    
    dp[i][1][j]=dp[i-1][0][j-1]*getMiman(x)+dp[i-1][0][j]*(x!=0)+dp[i-1][1][j-1]*9+dp[i-1][1][j]*1
  
print(dp[keta-1][0][K]+dp[keta-1][1][K])

Solution (Python):
import sys
from math import factorial

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

N = ir()
K = ir()
length = len(str(N))

def F(length, K, N):
    if length < K:
        return 0
    if K == 0:
        return 1
    if length == 1: 
        return N
    ret = 0
    top = int(str(N)[0])
    if length-K >= 1:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K 
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) 
    
    if K > 1: 
        N = int(str(N)[1:])
        length = len(str(N))
        ret += F(length, K-1, N)
    else:
        ret += 1 
    return ret

answer = F(length, K, N)
print(answer)

Solution (Python):
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
else:

    def main(d, k):
        if d == L:
            return 0
        if N[d] == "0":
            return main(d + 1, k)
        if (L - d) < k:
            return 0
        if k == 1:
            return ((L - d) - 1) * 9 + int(N[d])
        elif k == 2:
            return (
                ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81
                + ((L - d) - 1) * 9 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )
        elif k == 3:
            return (
                ((((L - d) - 1) * ((L - d) - 2) * ((L - d) - 3)) // 6) * (9 ** 3)
                + ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )

    print(main(0, K))

Solution (Python):

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

keta1=len(str(N))
maxN=int(str(N)[0])
secN=0
keta2=0
if keta1>1:
    keta2=len(str(int(str(N)[1:])))
    secN=int(str(int(str(N)[1:]))[0])
    if keta2>1:
        keta3=len(str(int(str(int(str(N)[1:]))[1:])))
        thiN=int(str(int(str(int(str(N)[1:]))[1:]))[0])
only1=0
only2=0
if secN==0:
    only1=1
if keta2>1:
    if str(int(str(int(str(N)[1:]))[0]))[0]==0:
        only2=1
import math

if keta1<K:
    print(0)
else:
    if K==1:
        print(maxN+9*(keta1-1))
    if K==2:
        if keta1-2!=0:
            if only1:
                print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2)
            else:
                if keta2-1!=0:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN+(keta2-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN)
        else:
            print((maxN-1)*(keta1-1)*9+secN)
    if K==3:
        if keta1-3!=0:
            if only1:
                print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6)
            else:
                if keta2-2!=0:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN+(keta3-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN)
        else:
            if only1:
                print((maxN-1)*(keta1-1)*9)
            else:
                print((maxN-1)*(keta1-1)*9+(secN-1)*9+thiN)

Solution (Python):
import sys
import math

input = sys.stdin.readline
n = int(input())
k = int(input())
t = n
m = 0
while t:
    m += 1
    t //= 10

def comb(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 9 ** k * comb(m-1, k)
tk = k

def dfs(i, mt, kt):
    a = i // 10 ** mt
    b = n // 10 ** mt
    if kt < 0:
        return 0
    if mt < kt:
        return 0
    if a < b:
        if mt > 0:
            return 9 ** kt * comb(mt, kt)
        else:
            return 1
    elif a > b:
        return 0
    if i == n and kt == 0:
        return 1
    elif i > n:
        return 0
    ret = 0
    for j in range(10):
        f = 0
        if j != 0:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

t_ans = 0
for i in range(1, n // (10 ** (m-1) )+1):
    ti = i * 10 ** (m-1)
    t_ans += dfs(ti, m-1, k-1)

print(int(ans+t_ans))

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

fact = [1]
for i in range(1, 101):
    fact += [fact[i-1] * i]


def nCk(N, K):
    if K > n or K < 0:
        return 0
    return fact[N] // fact[K] // fact[N-K]


def digits(N):
    N = abs(N)
    ret = 0
    x = 1
    while x <= N:
        ret += 1
        x *= 10
    return ret

def solve(N, K):
    if K == 0 and N == 0:
        return 1
    if K == 0 and N > 0:
        return 1
    if K > 0 and N == 0:
        return 0

    d = digits(N)
    if d < K:
        return 0

    top = N // (10**(d-1))
    return (top-1) * 9**(K-1) * nCk(d-1,K-1) + 9**(K) * nCk(d-1,K) + solve(N % (10**(d-1)), K-1)

print(solve(n,k))

Solution (Python):
import copy
N=str(input())
K=int(input())
m=len(N)
def con(n,r):
  if r==0:
    return 1
  else:
    return (n/r)*con(n-1,r-1)
S=0
for i in range(1,m):
  S=S+(9**K)*con(i-1,K-1)
if K==1:
  S=S+int(N[0])
  print(int(S))
if K==2:
  S=S+9*(m-1)*(int(N[0])-1)
  for i in range(1,m):
    for i1 in range(1,10):
      N1=(int(N[0]))*(10**(m-1))+i1*10**(m-i-1)
      if int(N)>=N1:
        S=S+1
  print(int(S))
if K==3:
  S=S+(int(N[0])-1)*(9**2)*con(m-1,K-1)
  for i in range(1,m-1):
    for j in range(i+1,m):
      for i1 in range(1,10):
        for j1 in range(1,10):
          N1=(int(N[0]))*(10**(m-1))+i1*10**(m-i-1)+j1*10**(m-j-1)
          if int(N)>=N1:
            S=S+1
  print(int(S))

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

d_sum = [[0,0,0] for i in range(101)]
pre = [0,0,0]
for i in range(1,101):
    pre[0] += 9
    pre[1] += 81*(i-1)
    pre[2] += (9**3)*(i-1)*(i-2)//2
    d_sum[i][0] = pre[0]
    d_sum[i][1] = pre[1]
    d_sum[i][2] = pre[2]

s = str(n)

ans = d_sum[len(s)-1][k-1]

nonzero = 0
for ind, i in enumerate(s):
    if int(i)==0:
        continue
    digit = len(s)-ind-1
    if ind==0:
        nonzero += 1
        if nonzero==k:
            ans += int(i)
            break
        ans += (int(i)-1)*d_sum[digit][k-nonzero-1]
    else:
        ans += d_sum[digit][k-nonzero-1]
        nonzero += 1
        if nonzero==k:
            ans += int(i)
            break
        ans += (int(i)-1)*d_sum[digit][k-nonzero-1]

print(ans)

Solution (Python):
import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r or n==r:
    return 1
  elif r==0:
    return 1
  else:
    return 0
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    
    if not_zero==K:
      ans+=1
      break
print(ans)

Solution (Python):
import math
import sys
sys.setrecursionlimit(1000010)

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


m = [[0,0,0,0]]
s = [ 1, 9, 0, 0 ]
m.append(s)



for i in range(2,101):
    t = [s[0], s[0]*9 + s[1], s[1]*9 + s[2], s[2]*9 + s[3] ]
    s = t
    m.append(s)




def count(n,k):
    if n ==0:
        if k == 0:
            return 1
        else:
            return 0
    if n < 10:
        if k == 0:
            return 1
        elif k == 1:
            return n
        else:
            return 0
    if k == 0:
        return 1

    if n < 10 ** (k-1):
        return 0
        
    t = n 
    p = 1 
    q = 0
    while t >= 10:
        t = t //10
        p = p * 10
        q = q + 1 
    
    
        
    ans = m[q][k]
    
    
    
    ans = ans + (t-1)* m[q][k-1]

    
    remain = n - p * t 
    x = count(remain,k-1)
    
    ans = ans + x
    
    return ans

print(count(N,K))

Solution (Python):
import sys
from math import factorial

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

N = ir()
K = ir()
length = 0
for i in range(1, 102):
    if 10 ** i > N:
        length = i
        break

answer = 0
def F(length, K, N):
    ret = 0
    if length == 1:
        if K == 1:
            return N
        elif K == 0:
            return 1
        else:
            return 0
    if length < K:
        return 0
    top = int(str(N)[0])
    if length-K >= 1:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K 
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) 
    if K > 1: 
        N = int(str(N)[1:])
        length = 0
        for i in range(1, 100):
            if 10 ** i > N:
                length = i
                break
        ret += F(length, K-1, N)
    else:
        ret += 1 
    return ret

answer = F(length, K, N)
print(answer)

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

def K1(num):
	return int(num[0]) + (len(num)-1)*9

def K2(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K1(tmp)
	out1 = (int(num[0])-1)*(L-1)*9
	out2 = ((L-1)*(L-2)//2)*9*9
	return out + out1 + out2

def K3(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K2(tmp)
	out1 = (int(num[0])-1)*((L-1)*(L-2)//2)*9*9
	out2 = ((L-1)*(L-2)*(L-3)//6)*9*9*9
	return out + out1 + out2

if len(N) < K:
	ans = 0
else:
	if K == 1:
		ans = K1(N)
	elif K==2:
		ans = K2(N)
	else:
		ans = K3(N)

print(ans)

Solution (Python):
N = [int(x) for x in input()]
K = int(input())

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

for i in range(D):
    for j in range(2):
        for d in range(10 if j else N[i] + 1):
            for k in range(4):
                if d:
                    if k + 1 <= 3:
                        dp[i + 1][j | (d < N[i])][k + 1] += dp[i][j][k]
                    else:
                        continue
                else:
                    dp[i + 1][j | (d < N[i])][k] += dp[i][j][k]

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

Solution (Python):
N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 5 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
    for smaller in range(2):
        for j in range(4):
            for x in range((9 if smaller else n[i]) + 1):
                dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])

Solution (Python):
from operator import mul
from functools import reduce
from itertools import combinations, product

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

S_len = len(S)
N_first = int(S[0])

def combinations_count(n, r):
  if n < r:
    return 0
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

if K > S_len:
  print(0)
else:
  count = 0
  if K > 1:
    for l in combinations(range(1, S_len), K-1):
      for m in product('123456789', repeat=K-1):
        s = S[0] + '0' * (S_len - 1)
        for i in range(K-1):
          s = s[:l[i]] + m[i] + s[l[i]+1:]
        if int(s) <= N:
          count += 1
  else:
    count += 1
  count += (N_first-1) * combinations_count(S_len-1, K-1) * (9 ** (K-1))
  count += combinations_count(S_len-1, K) * (9 ** K)
  print(count)

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

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  return ans


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

print(syou(n, k))

Solution (Python):
from math import factorial as fac

def comb(n,r):
    if ( r<0 or r>n ):
        return 0
    return fac(n)/(fac(r)*fac(n-r))


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

nn=str(n)
keta=len(nn)

ans=0

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

zero=0









def search(n,k):
    if k<=0:return
    global ans
    nn = str(n)
    keta = len(nn)
    ans += comb(keta - 1, k ) * 9 ** k
    if int(nn[0])-1>0:
        ans+=(int(nn[0])-1)*comb(keta-1,k-1)*9**(k-1)
    ne=n-int(nn[0])*10**(keta-1)
    search(ne,k-1)


search(n,k)
for i in range(keta):
    if nn[i]=="0":zero+=1
if keta-zero>=k:ans+=1
print(int(ans))

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

strN = str(N)
maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLeN in range(2):
        for m in range(K+1):
            x = 0
            if not isLeN and x > Nd: continue
            isLeN2 = isLeN or x < Nd
            dp[d+1][isLeN2][m] += dp[d][isLeN][m]
            for x in range(1, 10):
                if not isLeN and x > Nd: continue
                isLeN2 = isLeN or x < Nd
                m2 = m+1
                if m2 > K: continue
                dp[d+1][isLeN2][m2] += dp[d][isLeN][m]



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

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

strN = str(N)
maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLeN in range(2):
        for m in range(K+1):
            x = 0
            if not isLeN and x > Nd: continue
            isLeN2 = isLeN or x < Nd
            dp[d+1][isLeN2][m] += dp[d][isLeN][m]
            for x in range(1, 10):
                if not isLeN and x > Nd: continue
                isLeN2 = isLeN or x < Nd
                m2 = m+1
                if m2 > K: continue
                dp[d+1][isLeN2][m2] += dp[d][isLeN][m]



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

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

def kosu(p):
  if p == 1:
    answer = [9, 0, 0]
  elif p == 2:
    answer = [9, 81, 0]
  elif p == 3:
    answer = [9, 162, 729]
  else:
    k1 = 9
    k2 = (9 ** 2) * (p - 1)
    k3 = int((9 ** 3) * (p - 1) * (p - 2) / 2)
    answer = [k1, k2, k3]
  return answer

if keta == 1:
  if K == 1:
    print(N)
  else:
    print("0")
  quit()
  
ans = 0  
for i in range(1, keta):
  ans += kosu(i)[K - 1]


if K == 1:
  ans += int(str(N)[0])
elif K == 2:
  y = 0
  i = 1
  while y == 0:
    if int(str(N)[i]) != 0:
      y = i
      ans += int(str(N)[i]) + 9 * (keta -y - 1)
    i += 1
    if i == keta:
      y = keta
    
  
  ans += (int(str(N)[0]) - 1) * 9 * (keta - 1)
  
else:
  if keta >= 3:
    ans += int((int(str(N)[0]) - 1) * (9 ** 2) * (keta - 1) * (keta - 2) / 2)
    
    x = 0
    i = 1
    while x <= 1:
      if int(str(N)[i]) != 0:
        x += 1
        if x == 1:
          ans += (int(str(N)[i]) - 1) * (9 * (keta - i - 1))
          if i <= keta - 3:
            ans += (9 ** 2) * (keta - i - 1) * (keta - i - 2) / 2
        else:
          ans += int(str(N)[i]) + 9 * (keta - i - 1)
      i += 1
      if (i == keta - 1) and (x == 0):
        x = 2
      if i == keta:
        x = 2
        

print(int(ans))

Solution (Python):
import math
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

answer=0

n=int(input())
k=int(input())
now=n
keta=0
alist=[]
while now!=0:
    amari=now%10
    now=now//10
    alist.append(amari)
    keta+=1
alist.reverse()
zlist=[]
for al in range(len(alist)):
    if alist[al]!=0:
        zlist.append([al, alist[al]])

if k>keta:
    print(0)
else:
    moto=10**(keta-1)
    first=n//moto
    if k>=2:
        second=(n-first*moto)//(moto//10)
        if k>=3:
            third=(n-first*moto-second*(moto//10))//(moto//100)
    
    
    if keta-1>=k:
        answer+=cmb(keta-1, k)*(9**k)
    answer+=max(first-1, 0)*cmb(keta-1, k-1)*(9**(k-1))
    if k==1:
        answer+=1
    elif k==2:
        if keta-1>=k and second!=0:
            answer+=cmb(keta-2, k-1)*(9**(k-1))
        answer+=cmb(keta-2, k-2)*max(second-1, 0)*(9**(k-2))
        if second!=0:
            answer+=1
        else:
            swit=0
            kaz=0
            for zl in zlist:
                if zl[0]>=1 and swit==0:
                    swit=zl[0]
                    kaz=zl[1]
            if swit!=0:
                answer+=(keta-swit-1)*9
                answer+=kaz
    else:
        if keta-1>=k and second!=0:
            answer+=cmb(keta-2, k-1)*(9**(k-1)) 
        answer+=cmb(keta-2, k-2)*max(second-1, 0)*(9**(k-2)) 
        if keta-1>=k and third!=0 and second!=0:
            answer+=cmb(keta-3, k-2)*(9**(k-2)) 
        if second!=0:
            if keta-1>=k:
                if third!=0:
                    answer+=third
                else:
                    swit=0
                    keta2=0
                    kaz=0
                    for zl in zlist:
                        if zl[0]>=2 and swit<=0:
                            swit+=1
                            keta2=zl[0]
                            kaz=zl[1]
                    if swit>0:
                        answer+=(keta-keta2-1)*9
                        answer+=kaz
            else:
                if third!=0:
                    answer+=third
        else:
            if keta-1>=k:
                if True:
                    swit=0
                    keta2=0
                    kaz=0
                    for zl in zlist:
                        if zl[0]>=2 and swit<=1:
                            swit+=1
                            keta2=zl[0]
                            kaz=zl[1]
                    if swit>1:
                        answer+=(keta-keta2-1)*9
                        answer+=kaz
                    elif swit==1:
                        if keta2!=keta:
                            answer+=cmb(keta-keta2-1, 2)*81
            else:
                if third!=0:
                    answer+=third
    
    print(answer)

Solution (Python):
from operator import mul
from functools import reduce
from math import floor, log
from itertools import combinations, product

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

S_len = len(S)
N_first = int(S[0])

def combinations_count(n, r):
  if n < r:
    return 0
  if r == 0:
    return 1
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

if K > S_len:
  print(0)
else:
  count = 0
  if K > 1:
    for l in combinations(range(1, S_len), K-1):
      for m in product('123456789', repeat=K-1):
        s = S[0] + '0' * (S_len - 1)
        for i in range(K-1):
          s = s[:l[i]] + m[i] + s[l[i]+1:]
        if int(s) <= N:
          count += 1
  else:
    count += 1
  count += (N_first-1) * combinations_count(S_len-1, K-1) * (9 ** (K-1))
  count += combinations_count(S_len-1, K) * (9 ** K)
  print(count)