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 anss(N,K):
    c=0
    for i in range(1,N+1):
        if len(str(i))-str(i).count('0') == K:
            c+=1
    return c
def solve(p,n,k):
    if p == 0:
        return 0
    if k==1:
        return 10 + 9*(n-1)+(p-1)
    elif k==2:
        return 81 * n*(n-1)//2 + (p-1)*9*n
    else:
        return 729 * n*(n-1)*(n-2)//6 + (p-1)*81*n*(n-1)//2

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

N=str(N)
NN = [i for i in list(N) if i != '0']
dig = len(N) - 1

if K == 2:
    if len(NN) == 1:
        n0 = int(N[0])
        ans= (solve(n0,dig,2))
    else:
        n0 = int(N[0])
        for inn,nn in enumerate(N[1:]):
            if nn != '0':
                n1 = int(nn)
                break
        ans= (solve(n0,dig,2) + solve(n1,dig-inn-1,1))
elif K == 3:
    if len(NN) == 1:
        n0 = int(NN[0])
        ans=solve((n0),dig,3)
    elif len(NN) == 2:
        n0 = int(N[0])
        for inn,nn in enumerate(N[1:]):
            if nn != '0':
                n1 = int(nn)
                break
        ans= (solve(n0,dig,3) + solve(n1,dig-inn-1,2))
    else:
        n0 = int(N[0])
        
        n1 = int(N[1])
        n2 = int(N[2])
        ans=solve((n0),dig,3) + solve(n1,dig-1,2) + solve(n2,dig-2,1)
elif K == 1:
    ans=(solve(int(N[0]),dig,1))
    
print(ans)

Solution (Python):



def main():
    import sys
    import math
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)
    

    n = int(input())
    ns = str(n)
    k = int(input())
    keta = len(ns)

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

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

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

    for i in range(keta):
        for smaller in range(2):
            for j in range(i+1):
                for x in range(10 if smaller == 1 else int(ns[i])+1):
                    
                    
                    dp[i + 1][1 if smaller == 1 or x < int(ns[i])
                              else 0][j if x != 0 else j+1] += dp[i][smaller][j]
    
    
    
    print(dp[keta][0][keta-k]+dp[keta][1][keta - k])


if __name__ == '__main__':
    main()

Solution (Python):
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod



N = int(input())
K = int(input())
SN = str(N)
LN = list(SN)
keta =len(LN)
Nzer = keta-K
Nsei = K
output = 0
if keta>=K:
    output += comb(keta,K,10**9+7)*9**K
    t = 0
    s = 0
    while (s<=K-1)and(t<=keta-1):
        if LN[t]!="0":
            output -= (9-int(LN[t]))*comb(keta-1-t,K-1-s,10**9+7)*9**(K-1-s)
            t += 1
            s += 1
        elif LN[t]=="0":
            output -= (9-int(LN[t]))*comb(keta-1-t,K-1-s,10**9+7)*9**(K-1-s)
            t+=1
print(int(output))

Solution (Python):
tmp=input()
n=int(tmp)
l=len(tmp)
k=int(input())
if k==1:
    ans=9*(l-1)
    last=int(tmp[0])
    ans+=last
    print(ans)
    exit()
if k==2:
    c=l-2
    ans=(9**2)*((c*(c+1))//2)
    num=0
    for i in range(1,l):
        for head_i in range(9,0,-1):
            for tail_i in range(9,0,-1):
                cal=str(head_i)
                cal+="0"*len(tmp[1:i])
                cal+=str(tail_i)
                cal+="0"*len(tmp[i+1:])
                if int(cal)<=n:
                    num+=1
    
    ans+=num
    print(ans)
    exit()


c=0
for i in range(3,l):
    c+=(i-1)*(i-2)//2
ans=(9**3)*c
num=0
for i in range(1,l):
    for j in range(i+1,l):
        for f_i in range(1,10):
            if f_i<int(tmp[0]):
                num+=81
                continue
            for s_i in range(1,10):
                for t_i in range(1,10):
                    cal=f_i*(10**(l-1))+s_i*(10**(l-1-i))+t_i*(10**(l-1-j))
                    if cal<=n:
                        num+=1
ans+=num
print(ans)

Solution (Python):
import itertools, math

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    return (math.factorial(n) // math.factorial(r)) // math.factorial(n-r)

def ans_when_K1(N):
    max_digit = len(str(N))
    return 9 * (max_digit-1) + int(str(N)[0])

def ans_when_K2(N):
    max_digit = len(str(N))
    if max_digit < 2:
        return 0

    digit = 2
    ans = 0
    while digit < max_digit:
        ans += 9 * (digit-1) * 9
        digit += 1

    second_non_zero_idx = -1
    for i in range(1, max_digit):
        if str(N)[i] != "0":
            second_non_zero_idx = i
            break

    ans += (int(str(N)[0]) -1) * (digit-1) * 9
    if second_non_zero_idx != -1:
        ans += ans_when_K1(int(str(N)[second_non_zero_idx:]))
    return ans

def ans_when_K3(N):
    max_digit = len(str(N))
    if max_digit < 3:
        return 0

    digit = 3
    ans = 0
    while digit < max_digit:
        ans += 9 * cmb(digit-1, 2) * 9 * 9
        digit += 1

    second_non_zero_idx = -1
    for i in range(1, max_digit):
        if str(N)[i] != "0":
            second_non_zero_idx = i
            break

    ans += (int(str(N)[0]) -1) * cmb(digit-1, 2) * 9 * 9
    if second_non_zero_idx != -1:
        ans += ans_when_K2(int(str(N)[second_non_zero_idx:]))
    return ans

if K == 1:
    print(ans_when_K1(N))
elif K == 2:
    print(ans_when_K2(N))
else:
    print(ans_when_K3(N))

Solution (Python):
import math

def Comb(n, r):
  if n < r:
    return 0
  else:
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

N = input()
K = int(input())
ans = 0
for i in range(1, len(N)):
  if i < K:
    pass
  else:
    ans += 9 ** K * Comb(i-1, K-1)
ans += (int(N[0])-1) * Comb(len(N)-1, K-1) * 9 ** (K-1)
if K == 1:
  ans += 1
elif K == 2:
  for i in range(1, len(N)):
    if N[i] != '0':
      ans += int(N[i]) + 9 * (len(N) - i - 1)
      break
else:
  for i in range(1, len(N)):
    if N[i] != '0':
      if len(N) - i - 1 >= 2:
        ans += Comb(len(N) - i - 1, 2) * 9 ** 2
      if len(N) - i - 1 >= 1:
        ans += (int(N[i]) - 1) * 9 * (len(N) - i - 1)
      for j in range(i+1, len(N)):
        if N[j] != '0':
          ans += int(N[j]) + 9 * (len(N) - j - 1)
          break
      break
print(ans)

Solution (Python):

import sys
import math
INF = float("inf")


def solve(N: str, K: int):
    M = len(N)
    DP = [[[0]*2 for __ in range(K+1)] for _ in range(M+1)]
    Nstr = N

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

    for i in range(M):
        DP[i+1][0][True] = 1
        DP[i+1][0][False] = 0
        for k in range(K):
            DP[i+1][k+1][True] = DP[i][k][True]*9 + DP[i][k+1][True]*1
            if int(Nstr[i]) != 0:
                DP[i+1][k+1][True] += DP[i][k+1][False]
                DP[i+1][k+1][True] += DP[i][k][False]*(int(Nstr[i])-1)
            if int(Nstr[i]) == 0:
                DP[i+1][k+1][False] = DP[i][k+1][False]
            else:
                DP[i+1][k+1][False] = DP[i][k][False]
    print(DP[M][K][True]+DP[M][K][False])
    

    return


def main():

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


if __name__ == '__main__':
    main()

Solution (Python):
def tail(x):
	s = str(x)
	a = int(s[0]); d = len(s)
	return x - a * 10 ** (d - 1)

def K1(N):
	s = str(N)
	a = int(s[0]); d = len(s)
	res = 9 * (d - 1) + a
	return res

def K2(N):
	s = str(N)
	a = int(s[0]); d = len(s)
	res = (d - 1) * (d - 2) // 2 * 81
	res += (a - 1) * (d - 1) * 9
	res += K1(tail(N))
	return res
	
def K3(N):
	s = str(N)
	a = int(s[0]); d = len(s)
	res = (d - 1) * (d - 2) * (d - 3) // 6 * 729
	res += (a - 1) * (d - 1) * (d - 2) // 2 * 81
	res += K2(tail(N))
	return res

N = int(input())
K = int(input())
if K == 1:
	ans = K1(N)
elif K == 2:
	ans = K2(N)
elif K == 3:
	ans = K3(N)

print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k = get_all_int()



dp = [ [None]*101 for _ in range(4)]

for i in range(101):
    dp[0][i] = 1
dp[0][0] = 0
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0
dp[1][1] = 9
dp[2][1] = 0
dp[3][1] = 0

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




ans = 0

keta = 0
x = n
while x > 0:
    keta += 1
    x //= 10

def sol(n, keta, k):
    if k == 0:
        return 1
    if k < 0:
        return 0
    if keta < k:
        return 0
    if keta == 0:
        return 1
    
    top = n//10**(keta-1)%10
    if keta==1:
        return top
    ans = 0
    
    if top == 0:
        ans += sol(n, keta-1, k)
    else:
        ans += 1 * (0 if keta==1 else dp[k][keta-1])
    
    log(keta,top,k,ans)

    
    if top != 0:
        if top == 1:
            ans += sol(n, keta-1, k-1)
        else:
            ans += (top-1) * (1 if keta==1 else dp[k-1][keta-1])
        
        log(keta,top,k,ans)

    
    if top > 1:
        ans += sol(n, keta-1, k-1)
        log(keta,top,k,ans)
    return ans

if keta < k:
    print(0)
    exit()
ans += sol(n, keta, k)

print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a
 
show_flg=False
show_flg=True
 
ans=0

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

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


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




def solve():
    for i in range(n):
        c=int(s[i])
        for sm in range(1):
            for j in range(K+1):
            
            
                
                if j!=K:
                    if c!=0:
                        
                        dp[i+1][0][j+1]+=dp[i][0][j]
                        
                        dp[i+1][1][j+1]+=dp[i][0][j]*(c-1 if c!=0 else 0)
                        
                        dp[i+1][1][j+1]+=dp[i][1][j]*9
                    else:
                        
                        
                        
                        
                        
                        dp[i+1][1][j+1]+=dp[i][1][j]*9
                        
                
                
                if c!=0:
                    
                    0
                    
                    dp[i+1][1][j]+=dp[i][0][j]
                    
                    dp[i+1][1][j]+=dp[i][1][j]
                else:
                    
                    dp[i+1][0][j]+=dp[i][0][j]
                    
                    0
                    
                    dp[i+1][1][j]+=dp[i][1][j]


solve()

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

Solution (Python):
n=int(input())
m=len(str(n))
k=int(input())
def c(n,m):
    import math
    if n-m<0 or m<=0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))
def f(m,k):
    return c(m,k)*9**(k)



def slove(n,k):
    if k==0:
        return 0
    m=len(str(n))
    t=0
    t+=f(m-1,k)
    t+=f(m-1,k-1)*(int(str(n)[0])-1)
    if k==1:
        t+=int(str(n)[0])
    if n>9:
        t+=slove(int(str(n)[1:]),k-1)
    else:
        if k==1:
            return n
    return t

print(slove(n,k))

Solution (Python):
n = input()
K = int(input())
len_n = len(n)
ans = 0

def calc(free, count, now):
    global ans
    if count == K:
        ans += 1
        return
    if now == len_n:
        return 
    if free:
        for _ in range(9):
            calc(free, count + 1, now+1)
        
        calc(free, count, now+1)
    else:
        
        if n[now] != '0':
            for _ in range(int(n[now])-1):
                calc(not free, count + 1, now+1)
            
            calc(free, count+1, now+1)
        
            calc(not free, count, now+1)
        else:
            calc(free, count, now+1)
calc(False,0,0)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N = I()
K = I()
S = str(N)

def calc1(S):
    if len(S)<1:
        return 0
    flag = False
    ans = 0
    for s in S:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    return ans

def calc2(S):
    bl = len(S)
    ans = 0
    if bl<2:
        return 0
    
    ans += (bl-1)*(bl-2)*81 // 2
    
    ans += (int(S[0])-1)*9*(bl-1)
    
    val = -1
    for i in range(1,len(S)):
        if S[i]!='0':
            val = i
            break
    if val!=-1:
        newS = S[val:]
        ans += calc1(newS)
    return ans

def calc3(S):
    bl = len(S)
    if bl<3:
        return 0
    ans = 0
    
    ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    
    ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    
    val = -1
    for i in range(1,len(S)):
        if S[i]!='0':
            val = i
            break
    if val!=-1:
        newS = S[val:]
        ans += calc2(newS)
    return ans

if K==1:
    print(calc1(S))
if K==2:
    print(calc2(S))
if K==3:
    print(calc3(S))

Solution (Python):
from itertools import combinations as com
def comb(a,b):
  if a == 0:
    return 1
  r = 1
  for i in range(b):
    r *= a
    a -= 1
  r = r // [1,2,6][b-1]
  return r
n = input()
nl = len(n)
k = int(input())
i = 0
c = 0
while i < nl:
  if i+1 >= nl:
    break
  if i+1 < k:
    pass
  else:
    if k == 1:
      c += 9
    elif k == 2:
      c += 81 * i
    else:
      c += 729 * (i*(i-1))//2
  i += 1
lis = []
if k == 1:
  for cur in range(1,10):
    cur = cur * 10**i
    lis.append(cur)
elif k == 2:
  for j in range(i):
    for k in range(1,10):
      for cur in range(1,10):
        cur = cur * 10**i + k * 10**j
        lis.append(cur)
else:
  for j,k in com(range(i),2):
    for l in range(1,10):
      for m in range(1,10):
        for cur in range(1,10):
          if cur < int(n[0]):
            c += 1
          else:
            cur = str(cur) + '0'*(i-k-1) + str(l) + '0'*(k-j-1) + str(m) + '0'*j
            if cur <= n:
              c += 1
n = int(n)
for i in lis:
  if i <= n:
    c += 1
print(c)

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

M = len(str(N)) 

def solve_1(n,m):
    ans = 0
    ans += 9*(m-1)
    x = n//(10**(m-1))
    ans += x
    return ans

def solve_2(n,m):
    ans=0
    if m<2:
        return ans
    elif m>2:
        ans+= (9**2)*int((m-2)*(m-1)/2) 

    x = n//(10**(m-1))
    ans+= (x-1)*(m-1)*9

    y=int(str(n)[1:])
    ans+=solve_1(y,len(str(y)))
    
    return ans

def solve_3(n,m):
    ans=0
    if m<3:
        return ans
    elif m>3:
        ans+=int((9**3)*(1/6)*(m-1)*(m-2)*(m-3))
    
    x = n//(10**(m-1))
    ans+=int((x-1)*(m-1)*(m-2)/2*81)
    
    y= int(str(n)[1:])

    ans+=solve_2(y,len(str(y)))
    return ans

if K==1:
    ans = solve_1(N,M)
if K==2:
    ans = solve_2(N,M)
if K==3:
    ans = solve_3(N,M)

print(ans)

Solution (Python):
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[0])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[0])-1)
    print(counter)

Solution (Python):
n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())


MOD = 1000000007


class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0
if(n_digit < k):
    
    print(0)
else:
    
    ans += com.calc_COM(n_digit-1, k) * (9 ** k)
    
    n_top = int(n_str[0])
    if(k-1 <= 0):
        
        ans += n_top
    else:
        
        ans += (n_top - 1) * com.calc_COM(n_digit-1, k-1) * (9 ** (k-1))
        
        n_sec = 0
        count = n_digit
        i = 1
        for nc in n_str[1:]:
            i += 1
            count -= 1
            n_sec = int(nc)
            if(n_sec > 0):
                break
        if(count >= k-1):
            
            
            ans += 1 * com.calc_COM(count-1, k-1) * (9 ** (k-1))
            
            if(k-2 <= 0):
                ans += 1 * n_sec 
            else:
                
                ans += 1 * (n_sec - 1) * com.calc_COM(count-1, k-2) * (9 ** (k-2))
                
                n_third = 0
                sec_count = count
                for nd in n_str[i:]:
                    sec_count -= 1
                    n_third = int(nd)
                    if(n_third > 0):
                        break
                if(sec_count >= k-2):
                    
                    
                    ans += 1 * 1 * (sec_count-1) * 9
                    
                    ans += 1 * 1 * n_third

    print(ans)

Solution (Python):


import math

def f(m, k):
    if k > m:
        return 0

    return math.factorial(m)//(math.factorial(m-k)*math.factorial(k))*(9**k)


def g(N, k, i):
    if k == 0:
        return 1
        
    M = len(N)-i

    if M < k:
        return 0

    n = int(N[i])

    s = 0

    if n > 0:
        s += f(M-1, k) + (n-1)*f(M-1, k-1) + g(N, k-1, i+1)
    else:
        s += g(N, k, i+1)

    return s


N = input()
K = int(input())
print(g(N, K, 0))

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

num = len(str(N))
n = str(N)
List = [[0,0],[0,0],[0,0]]
count = 0

for i in range(num):
    if n[i] != '0':
        List[count][0] = int(n[i])
        List[count][1] = num - i
        count += 1
        if count == 3:
            break
        
result = 0

if K == 1:
    result += List[0][0] + (List[0][1] - 1) * 9
elif K == 2:
    if N <= 10:
        result = 0
    else:
        if List[1][1] != 0:
            result += List[1][0] + (List[1][1] - 1) * 9 
        result += (List[0][0] - 1) * (List[0][1] - 1) * 9 
        result += 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) / 2 
elif K == 3:
    if N <= 110:
        result = 0
    else:
        if List[2][1] != 0:
            result += List[2][0] + (List[2][1] - 1) * 9 
        if List[1][1] != 0:
            result += (List[1][0] - 1) * (List[1][1] - 1) * 9 
        result += 9 * 9 * (List[1][1] - 1) * (List[1][1] - 2) / 2 
        result += (List[0][0] - 1) * 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) / 2 
        result += 9 * 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) * (List[0][1] - 3) / 3 / 2 

print(int(result))

Solution (Python):
import math
def comb(n, r):
  if n >= r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0
N = int(input())
K = int(input())
A = []
ans = 0


for i in range(K):
  n = int(str(N)[0])
  dig = len(str(N)) - 1
  A.append([n, dig])
  N -= n * 10**dig
  if N == 0:
    break


for i in range(len(A)):
  if A[i][1] >= K-i:
    ans += comb(A[i][1], K-i) * 9 ** (K-i) 

  ans += (A[i][0]-1) * comb(A[i][1], K-i-1) * 9 ** (K-i-1)

if len(A) == K:
  ans += 1


print(ans)

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

if n_num < k:
    print('0')
else:

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

    dp[0][0][0] = 1
    for i in range(n_num):
        for smaller in range(2):
            for j in range(n_num):
                lim = 9 if smaller else n_list[i]
                for x in range(lim + 1):
                    if x != 0:
                        ns = j + 1
                    else:
                        ns = j
                    nlt = smaller | (x < n_list[i])
                    dp[i + 1][nlt][ns] += dp[i][smaller][j]
    ans = dp[n_num][0][k] + dp[n_num][1][k]
    print(ans)

Solution (Python):
N = [int(i) for i in input()]
n = len(N)
K = int(input())
lis = [0]*3
foo = 0
for i in range(n):
    if N[i]!=0:
        lis[foo] = i
        foo += 1
    if foo==3:
        break



if n < K:
    print(0)
else:
    if K ==3:
        ans = (n-1)*(n-2)*(n-3)*9**3//6
        ans += (N[0]-1)*(n-1)*(n-2)*9**2 //2
        if lis[1]!=0:
            ans += (n-1-lis[1])*(n-2-lis[1])*9**2//2
        if lis[2]!=0:
            ans += (N[lis[1]]-1)*(n-1-lis[1])*9 +(n-1-lis[2])*9 +N[lis[2]]
    elif K ==2:
        ans = (n-1)*(n-2)//2 *9**2 +(N[0]-1)*(n-1)*9
        if lis[1]!=0:
            ans += (n-1-lis[1])*9 +N[lis[1]]
    elif K ==1:
        ans = 9*(n-1) +N[0]

    print(max(0,ans))

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

def nine(x, y):
  if y == 0:
    return 1
  elif x < y:
    return 0
  elif x == y:
    return 9 ** x
  elif y < 0:
    return 0
  else:
    r = 1
    for i in range(y):
      r *= x - i
      r //= i + 1
    r *= 9 ** y
    return r

ans = 0
if n > 10000:
  while n >= 10**(k-1):
    d = math.floor(math.log(n, 10))
    ans += nine(d, k)
    ans += nine(d, k-1) * (n//(10**d) - 1)
    n %= 10**d
    if k > 0:
      k -= 1
    else:
      break
  print(ans)
else:
  for i in range(1,n+1):
    if str(i).count('0')==len(str(i))-k:
      ans += 1
  print(ans)

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

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for j1 in range(len(str(N))-2):
        for j2 in range(len(str(N))-2-j1):
            j3 = len(str(N))-2-j1-j2-1
            for i1 in range(1,10):
                for i2 in range(1,10):
                    for i3 in range(9,0,-1):
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += i3
                            break

print(res)

Solution (Python):
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
K = int(input())
strN = str(N)
lenn = len(strN)
if K == 1:
    print((lenn-1)*9 + int(strN[0]))
elif K == 2:
    if lenn == 1:
        print(0)
    else:
        ans1 = 81*comb(lenn-1,2)
        ans1 += (int(strN[0])-1)*9*(lenn-1)
        for i in range(1,lenn):
            if int(strN[i]) != 0:
                ans1 += int(strN[i])
                ans1 += 9*(lenn-i-1)
                break
        print(ans1)
else:
    if lenn <= 2:
        print(0)
    else:
        ans1 = (9**3)*comb(lenn-1,3)
        ans1 += (int(strN[0])-1)*81*comb(lenn-1,2)
        for i in range(1,lenn):
            if strN[i] != '0':
                break
        strN = strN[i:]
        lenn = len(strN)
        if lenn == 1:
            ans2 = 0
        else:
            ans2 = 81*comb(lenn-1,2)
            ans2 += (int(strN[0])-1)*9*(lenn-1)
            for i in range(1,lenn):
                if int(strN[i]) != 0:
                    ans2 += int(strN[i])
                    ans2 += 9*(lenn-i-1)
                    break
        print(ans1+ans2)

Solution (Python):
def f2(n):
    c = len(n)-1
    nn = n[1:]
    s = c*(c-1)//2 * 9*9 
    s += c * (int(n[0])-1)*9
    nn = str(int(nn))
    s += (len(nn)-1)*9 + int(nn[0])
    return s

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

if k == 1:
    print((len(n)-1)*9 + int(n[0]))
if k == 2:
    if len(n) >= 2:
        print(f2(n))
    else:
        print(0)
        
if k == 3:
    if len(n) >= 3:
        c = len(n)-1
        nn = n[1:]
        nn = str(int(nn))
        s = c*(c-1)*(c-2)//(3*2) * 9*9*9
        s += (int(n[0])-1) * c*(c-1)//2 * 9*9 
        if len(nn) >= 2:
            s += f2(nn)
        print(s)
    else:
        print(0)

Solution (Python):
import itertools
S=input()
SS=int(S)
N=len(S)
K=int(input())
def base9(n):
    res=""
    while(n>0):
        res=str((n%9)+1)+res
        n=n//9
    return "1"*(K-len(res))+res
ans=0
for seq in itertools.combinations(range(N),K):
    
    low=0
    high=-1+9**K
    tmp=sum([9*10**(seq[i]) for i in range(K)])
    
    if tmp<=SS:
        ans+=9**K
        continue
    if tmp//9>SS:
        continue
    while(high-low>1):
        mid=(high+low)//2
        tmp2=base9(mid)
        tmp=sum([int(tmp2[i])*10**(seq[-i-1]) for i in range(K)])
        
        if tmp<=SS:
            low=mid
        else:
            high=mid
    ans+=low+1
print(ans)

Solution (Python):
N=input()
n=int(N)
K=int(input())
import math

l=len(N)

if l==1:
  if K==1:
    print(N)
  else:
    print(0)
else:
  a=[0]*3
  b=[l]*3
  k=0
  for i in range(l):
    if int(N[i])!=0:
      a[k]=int(N[i])
      b[k]=i
      k+=1
    if k==3:
      break
  
  x=0
  for i in range(l-1):
    if K==1:
      x+=9
    elif K==2:
      x+=81*i
    else:
      x+=(729*i*(i-1))//2
  
  if K==1:
    x+=a[0]
  elif K==2:
    x+=(a[0]-1)*9*(l-1)+max([0,(l-b[1]-1)*9])+a[1]
  else:
    x+=((a[0]-1)*81*(l-2)*(l-1))//2
    x+=(81*max([0,(l-b[1]-1)])*max([0,(l-b[1]-2)]))//2
    x+=max([0,(a[1]-1)])*9*max([0,(l-b[1]-1)])
    x+=9*max([0,(l-b[2]-1)])+a[2]
  
  print(x)

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

def take_k_comb(a, b):
    if b == 0:
        return 1
    if b == 1 and a >= 1:
        return a * 9
    if b == 2 and a >= 2:
        return a*(a-1)//2 * 9 * 9
    if b == 3 and a >= 3:
        return a*(a-1)*(a-2)//6*9*9*9
    return 0

def constrained_nk(n, k):
    if k == 0:
        return 1
    if n == "":
        if k == 0:
            return 1
        else:
            return 0
    h = int(n[0])
    rest = n[1:]
    if h == 0:
        return constrained_nk(rest, k)
    s = take_k_comb(len(rest), k)
    s += (h-1) * take_k_comb(len(rest), k - 1)
    s += constrained_nk(rest, k-1)
    return s

print(constrained_nk(n, k))