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 countInRangeUtil(pos, cnt, tight, num): 
  
    
    if pos == len(num): 
  
        
        
        if cnt <= K: 
            return 1
        return 0
  
    
    
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    
    
    
    
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        
        
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        
        
        if dig < num[pos]: 
            currTight = 1
  
        
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  



def countInRange(x): 
    global dp, K, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  

if __name__ == "__main__": 
  
    
    dp = [] 
    M = 100
  
    
    K = 0
  
    L = 1
    R = int(input())
    K = int(input())
    a=countInRange(R)
    K=K-1
    b=countInRange(R)
    print(a-b)

Solution (Python):
from math import factorial
N=int(input())
K=int(input())
S=list(map(int,str(N)))

def C(n,r):
  if n>=r:
    return factorial(n)//factorial(r)//factorial(n-r)
  else:
    return 0

def D(i,j):
  return C(i,j)*(9**j)

ans=0
l=len(S)
for i in range(l):
  if S[i]!=0:
    ans+=(S[i]-1)*D(l-1,K-1)+D(l-1,K)
    l-=1
    K-=1
  else:
    l-=1
  if K==0:
    ans+=1
    break
    
print(ans)

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

r = 0
tp = n
while tp != 0:
    r += 1
    tp = tp//10

p = n//pow(10,r-1)

res = 0

if k == 1:
    res = (r-1)*9 + p
    print(res)

elif k == 2:
    if r <= 1:
        print(0)
        exit()
    if r >= 3:
        res = (r-1)*(r-2)*81//2
    
    res += (p-1)*9*(r-1)

    tmp = p*pow(10,r-1)
    for i in range(r-1):
        for j in range(1,10):
            if tmp + j*pow(10,i) <= n:
                res += 1
    
    print(res)
else:
    if r <= 2:
        print(0)
        exit()
    
    if r >= 4:
        res = pow(9,3)*(r-1)*(r-2)*(r-3)//6
    
    res += (p-1)*81*(r-1)*(r-2)//2

    tmp = p*pow(10,r-1)

    for i in range(r-1):
        for j in range(i+1,r-1):
            for w in range(1,10):
                for q in range(1,10):
                    if tmp + w*pow(10,i) + q*pow(10,j) <= n:
                        res += 1
    
    print(res)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def f1(ss):
	return (len(ss)-1)*9

def f2(ss):
	ll=len(ss)
	return (((ll-1)*(ll-2))//2)*9*9
	
def f3(ss):
	ll=len(ss)
	return (((ll-1)*(ll-2)*(ll-3))//6)*9*9*9
	
def fk1(ss):
	aa=int(ss[0])
	return aa+f1(ss)
	
def fk2(ss):
	aa=int(ss[0])
	ret=f2(ss)
	ret+=(aa-1)*f1(ss)
	for i, c in enumerate(ss):
		if i == 0:
			continue
		if int(c)>0:
			ret += fk1(ss[i:])
			break
	return ret
	
def fk3(ss):
	aa=int(ss[0])
	ret = f3(ss)
	ret += (aa-1)*f2(ss)
	for i, c in enumerate(ss):
		if i == 0:
			continue
		if int(c)>0:
			ret += fk2(ss[i:])
			break
	return ret	

def main():
	n = input()
	k = int(input())
	if k== 1:
		return fk1(n)
	elif k==2:
		return fk2(n)
	else:
		return fk3(n)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import math
def C(a,b):
    return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

def count(N, K):
    if K == 0:
        return 1
    if N == 0:
        return 0
    keta = int(math.log10(N)) + 1
    if keta < K:
        return 0
    elif keta == K:
        if K == 1:
            return N
        elif K == 2:
            return (N//10 - 1) * 9 + N % 10
        else:
            return (N//100 - 1) * 81 + ((N//10)%10 - 1) * 9 + N % 10
    else:
        keta1 = (N//(10**(keta-1)))%10
        ans = C(keta - 1, K) * (9**K)
        ans += (keta1 - 1) * C(keta-1, K-1) * (9**(K-1))
        ans += count(N-(keta1*(10**(keta-1))), K-1)
        return ans

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

Solution (Python):
"""
E
"""
import sys
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())

L=len(N)
if L<K:
    print(0)
    sys.exit()
ans=0
if L>K:
    ans+=cmb(L-1,K)*(9**K)
ans+=(N[0]-1)*cmb(L-1,K-1)*(9**(K-1))


if K==1:
    ans=(L-1)*9+N[0]
    
elif K==2:
    H=[0]*L
    H[0]=N[0]
    for i in range(1,L):
        for j in range(1,10):
            H[i]=j
            if N>=H:
                ans+=1
        H[i]=0
    
else:
    H=[0]*L
    H[0]=N[0]
    for i in range(1,L-1):
        for k in range(1,10):
            H[i]=k
            for j in range(i+1,L):
                for l in range(1,10):
                    H[j]=l
                    if N>=H:
                        ans+=1
                H[j]=0
        H[i]=0
print(ans)

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


def f(n, d, k):
    if k == 0:
        return 1
    if d == 1:
        return int(n) if k == 1 else 0
    msb = int(n[0])
    if msb == 0:
        return f(n[1:], d - 1, k)
    return f(n[1:], d - 1, k - 1) + (msb - 1) * f('9' * (d - 1), d - 1, k - 1) + f('9' * (d - 1), d - 1, k)


print(f(N, len(N), K))

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

ln = len(N)

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

for i in range(1, ln + 1):
    for j in range(2):
        for k in range(4):
            num = int(N[i-1])
            if j:
                l_mx = 9
            else:
                l_mx = num

            for l in range(l_mx + 1):
                if l == 0:
                    dp[i][j or l < num][k] += dp[i-1][j][k]
                else:
                    if k > 0:
                        dp[i][j or l < num][k] += dp[i-1][j][k-1]

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

Solution (Python):
n = int(input())
k = int(input())
m = n
l = []
while m > 0:
    l.append(m%10)
    m //= 10

try:
  n_ = n-(l[-1]*10**(len(l)-1))
  m_ = n_
  l_ = []
  while m_ > 0:
      l_.append(m_%10)
      m_ //= 10

  n__ = n_-(l_[-1]*10**(len(l_)-1))
  m__ = n__
  l__ = []
  while m__ > 0:
      l__.append(m__%10)
      m__ //= 10
except:
  pass
      
def d1(lst):
  ans = 0
  for num,i in enumerate(lst):
    if num != (len(lst)-1):
      ans += 9
    else:
      ans += i
  return ans

def d2(lst,lst_):
  ans = 0
  for num,i in enumerate(lst):
    if num != (len(lst)-1):
      ans += 81*num
    else:
      ans += (i-1)*9*num+d1(lst_)
  return ans

def d3(lst,lst_,lst__):
  ans = 0
  for num,i in enumerate(lst):
    if num != (len(lst)-1):
      ans += 729*(num-1)*num//2
    else:
      ans += (i-1)*81*(num-1)*num//2+d2(lst_,lst__)
  return ans

if k ==  1:
  print(d1(l))
if k ==  2:
  print(d2(l,l_))
if k ==  3:
  print(d3(l,l_,l__))

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


if int(n)<1000:
    c=0
    for i in range(1,int(n)+1):
       if len(str(i))-str(i).count("0")==k:
           c+=1
else:
    n_l=len(n)
    c=0
    if k==1:
        c=int(n[0])+9*(n_l-1)
    elif k==2:
        for i in range(2,n_l):
            c+=9*9*(i-1)
        c+=(int(n[0])-1)*9*(n_l-1)
        
        for i in range(1,n_l):
            if int(n[i])>0:
                c+=int(n[i])+(n_l-i-1)*9
                break

    else:
        for i in range(3,n_l):
            c+=9**3*((i-1)*(i-2)/2)
                    
        c+=(int(n[0])-1)*9*9*((n_l-1)*(n_l-2)/2)
        
        flag_i=False
        flag_j=False
        for i in range(1,n_l):
            if int(n[i])>0:
                flag_i=True
                for j in range(i+1,n_l):
                    if int(n[j])>0:
                        flag_j=True
                        break
            if flag_i:
                break
        if flag_i:
            c+=(int(n[i])-1)*9*(n_l-i-1)
            c+=9*9*((n_l-i-1)*(n_l-i-2)*0.5)
            if flag_j:
                c+=(int(n[j]))+9*(n_l-j-1)
                
print(int(c))

Solution (Python):
MOD = 1000000007
INF = float("inf")

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

len_n = len(str(n))

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

base = [[0]*4 for _ in range(200)]

for i in range(200):
    base[i][0] = 1
for i in range(1, 200):
    base[i][1] = 9 * i
for i in range(2, 200):
    base[i][2] = 9 * 9 * i*(i-1)//2
for i in range(3, 200):
    base[i][3] = 9 * 9 * 9 * i * (i - 1) * (i-2) // 6

ans = 0
len_n = len(str(n))
n_str = str(n)

for i in range(len(n_str)):
    
    if int(n_str[i]) > 0:
        ans += (int(n_str[i])-1)*base[len_n-1][k-1] + base[len_n-1][k]
        
        if k == 1:
            ans += 1
        k -= 1
    len_n -= 1
    if k == 0:
        break

print(ans)

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

N = readline().strip()
K = int(readline())

MM = [9, 81, 9 ** 3]

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

def xxx(N, K):
    L = len(N)
    if L <= K - 1:
        return 0
    
    if K == 0:
        return 1
    
    a = comb(L - 1, K) * MM[K - 1]

    b = int(N[0]) - 1
    a += b * comb(L - 1, K - 1) * MM[K - 2] if K >= 2 else b
    
    _i = L
    for i in range(1, L):
        if N[i] != '0':
            _i = i
            break

    if _i < L:
        a += xxx(N[_i:], K - 1)
    elif K == 1:
        a += 1
    return a

print(xxx(N, K))

Solution (Python):
def almost0(m,K):
    M=str(m)
    s=len(M)
    if s<K:
        return 0
    elif m==0:
        return 0
    elif K==0:
        return 0
    elif K==1:
        return int(M[0])+almost0((10**(len(M)-1))-1,K)
    elif K==2:
        return (int(M[0])-1)*9*(len(M)-1)+almost0(m%(10**(len(M)-1)),K-1)+almost0((10**(len(M)-1))-1,K)
    else:
        return  (int(M[0])-1)*81*(s-1)*(s-2)//2+almost0(m%(10**(s-1)),K-1)+almost0((10**(s-1))-1,K)

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

print(almost0(N,K))

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


@lru_cache(maxsize=None)
def rec(k,tight,sum_val):
    
    if k == len(N):
        if sum_val == K and sum_val != 0:
            return 1
        else:
            return 0

    
    x = int(N[k])
    if tight:
        r = x
    else:
        r = 9
    res = 0
    for i in range(r + 1):
        if i == 0:
            res += rec(k + 1 ,tight and i == r, sum_val)
        else:
            res += rec(k + 1, tight and i == r, sum_val + 1)

    return res



print(rec(0 , True , 0))

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

def c(n, k):
    if n < k:
        return 0
    else:
        x = 1
        for i in range(k):
            x *= (n - i)
            x //= (i + 1)
        return x

ans = 0
for i in range(k):
    temp1 = len(str(n)) - 1
    temp2 = n // (10 ** temp1)
    check = k - i
    if check == 1:
        ans += temp2 + temp1 * 9
    else:
        ans += c(temp1, check) * (9 ** check) + (temp2 - 1) * c(temp1, check - 1) * (9 ** (check - 1))
    n %= 10 ** temp1
print(ans)

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

DP = [[[1,0,0,0,],[0,0,0,0]] for i in range(len(N)+1)]
for i in range(len(N)):
    if N[-1-i] == '0':
        for k in range(K):
            DP[i+1][0][k+1] = DP[i][0][k+1]
            DP[i+1][1][k+1] = DP[i][1][k+1]
    else:
        for k in range(K):
            DP[i+1][0][k+1] = DP[i][0][k+1]+DP[i][1][k+1]
    for j in range(1,10):
        for k in range(K):
            if j > int(N[-1-i]):
                DP[i+1][1][k+1] += DP[i][1][k] + DP[i][0][k]
            elif j < int(N[-1-i]):
                DP[i+1][0][k+1] += DP[i][1][k] + DP[i][0][k]
            elif j == int(N[-1-i]):
                DP[i+1][0][k+1] += DP[i][0][k]
                DP[i+1][1][k+1] += DP[i][1][k]
"""
for i in DP:
    for j in i:
        print(j)
    print()
"""
print(DP[-1][0][K])

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

len_n = len(n)

dp = []
for _ in range(len_n + 1):
    dp.append([[0] * 4 for __ in range(2)])


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

for i in range(1, len_n+1):
    now = int(n[i-1])

    dp[i][0][0] = 1
    for j in range(1,4):
        dp[i][0][j] = dp[i-1][0][j] + dp[i-1][0][j-1] * 9
        if(now == 0):
            dp[i][1][j] = dp[i-1][1][j]
        else:
            dp[i][0][j] += dp[i-1][1][j]
            dp[i][0][j] += dp[i-1][1][j-1] * (now-1)
            dp[i][1][j] = dp[i-1][1][j-1]

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

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def f(k,p):
    if p<k:
        ret = 0
    if k==0:
        ret = 1
    elif k==1:
        ret = p*9
    elif k==2:
        ret = 9*9*p*(p-1)//2
    else:
        ret = 9*9*9*p*(p-1)*(p-2)//6
    
    return ret

def g(k,p,n):
    
    if p==0 or p<k:
        return 0
    if k==0:
        ret = 1
    elif p==1:
        ret = n
    elif n<10**(p-1):
        ret = g(k,p-1,n)
    else:
        m = n//(10**(p-1))
        ret = g(k-1,p-1,n-m*(10**(p-1))) + (m-1)*f(k-1,p-1) + f(k,p-1)
    
    return ret

n = inn()
k = inn()
print(g(k,100,n))

Solution (Python):
N=input()
K=int(input())
m=len(N)
a=0
if K==3:
    for i in range(1,m-2):
        a+=i*(i+1)
    a//=2
    a*=729
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                for b in range(m-2):
                    for c in range(m-2-b):
                        if N>=str(i)+"0"*b+str(j)+"0"*c+str(k)+"0"*(m-3-b-c):
                            a+=1
elif K==1:
    if int(N)<10:
        a=int(N)
    else:
        a=9
        for i in range(2,m):
            a+=9
        for i in range(1,10):
            if N>=str(i)+"0"*(m-1):
                a+=1
else:
    for i in range(1,m-1):
        a+=i
    a*=81
    for i in range(1,10):
        for j in range(1,10):
            for k in range(m-1):
                if N>=str(i)+"0"*k+str(j)+"0"*(m-2-k):
                    a+=1
print(a)

Solution (Python):
import math
n=input()
k=int(input())
t=0
def com(a,b):
    if b>a:
        return 0
    else:
        return math.factorial(a)//(math.factorial(b)*math.factorial(a-b))
def su(n,k,i,s):
    if s==0:
        return 1
    if len(n)-i<s:
        return 0
    if n[i]=="0":
        return su(n,k,i+1,s)
    else:
        return (9**s)*(com(len(n)-i-1,s))+(int(n[i])-1)*(9**(s-1))*(com(len(n)-i-1,s-1))+su(n,k,i+1,s-1)
print(su(n,k,0,k))

Solution (Python):
import sys

def comb(n, k):
    if k == 0:
        return 0
    if n < k:
        return 0
    res=1
    for i in range(n - k + 1, n + 1):
        res *= i
    for i in range(1,k + 1):
        res //= i
    return res

n=input()
k = int(input())
l = len(n)

top = int(n[0])

if l == 1:
    if k >= 2:
        print(0)
        sys.exit()
    print(top)
    sys.exit()

if k == 1:
    z = 9
elif k == 2:
    z = 81
else:
    z = 729

ans = comb(l - 1, k) * z
ans += comb(l - 1, k - 1) * (top - 1) * (z // 9)

if k == 1:
    ans+=top
elif k == 2:
    for i in range(1, l):
        if i==1 or int(n[1:i]) == 0:
            ans += int(n[i])
        else:
            ans += 9
elif k == 3:
    for i in range(1, l):
        for j in range(i + 1, l):
            flag1 = i == 1 or int(n[1:i]) == 0
            flag2 = j == i + 1 or int(n[i + 1 :j]) == 0
            if not(flag1) and not(flag2):
                ans += 81
            elif flag1 and not (flag2):
                ans += 9 * int(n[i])
            elif not (flag1) and flag2:
                ans += 81
            else:
                if int(n[i]) == 0:
                    continue
                ans += 9 * (int(n[i]) - 1) + int(n[j])

print(ans)

Solution (Python):
import math

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

str_n=input()
k=int(input())
cnt=0
dig = len(str_n)


cnt += (int(str_n[0])-1)*combinations_count(dig-1,k-1)*9**(k-1)

if dig-1>=k:
  cnt += combinations_count(dig-1,k)*9**k


if k==1:
  cnt+=1
else:
  
  for i in range(dig-1):
    if str_n[i+1] != '0':
      dig2 = i+1
      break
  else:
    print(cnt)
    exit()
  
  cnt += (int(str_n[dig2])-1)*combinations_count(dig-1-dig2,k-2)*9**(k-2)
  
  if dig-1-dig2>=k-1:
    cnt += combinations_count(dig-1-dig2,k-1)*9**(k-1)
  
  if k==2:
    cnt+=1
  else:
    
    for i in range(dig-1-dig2):
      if str_n[i+1+dig2] != '0':
        dig3 = i+1+dig2
        break
    else:
      print(cnt)
      exit()
    
    cnt += int(str_n[dig3])
    
    cnt += combinations_count(dig-1-dig3,k-2)*9**(k-2)
print(cnt)

Solution (Python):

import sys
input = sys.stdin.readline





def main():
    n = input().strip()
    k = int(input())
    if k == 1:
        ans = k1(n)
    elif k == 2:
        ans = k2(n)
    elif k == 3:
        ans = k3(n)
    
    print(int(ans))


def k1(n):
    ans = 0
    return 9*(len(n)-1)+int(n[0])

def k2(n):
    ans = 0
    if len(n) == 1:
        ans = 0
    elif len(n) >= 2:
        ans += k1(str(int(n[1:])))
        ans += (int(n[0])-1)*9*(len(n)-1)
        ans += 9*9*(len(n)-1)*(len(n)-2)/2
    return ans

def k3(n):
    ans = 0
    if len(n) <= 2:
        ans = 0
    elif len(n) >= 3:
        ans += k2(str(int(n[1:])))
        ans += (int(n[0])-1)*9*9*(len(n)-1)*(len(n)-2)/2
        ans += (len(n)-1)*(len(n)-2)*(len(n)-3)/6*9**3
    return ans

    
if __name__ == '__main__':
    main()

Solution (Python):
N = input()
K = int(input())
def Anger(n, k):
  d = int(n[0])
  if len(n) < k:
    return 0
  else:
    if k == 1:
      if d == 0 and len(n) != 1:
        return Anger(n[1:], k)
      elif d == 0 and len(n) == 1:
        return 0
      else:
        if len(n) != 1:
          S = d + 9 * (len(n) - 1)
          return S
        else:
          return d
    else:
      if d == 0:
        return Anger(n[1:], k)
      else:
        S = (d - 1) * (9 ** (k-1))
        for j in range(k-1):
          S *= len(n) - j - 1
          S //= j + 1
        T = 9 ** k
        for j in range(k):
          T *= len(n) - j - 1
          T //= j + 1
        return S + T + Anger(n[1:], k - 1)
    
print(Anger(N, K))

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    K = int(input())
    if N <= 1000:
        count = 0
        for i in range(1, N + 1):
            d = 0
            ci = i
            while ci > 0:
                d += (1 if ci % 10 > 0 else 0)
                ci //= 10
            if d == K: count += 1
        print(count)
    else:
        strN = str(N)
        dig = len(strN)
        DPsmall = [[0 for j in range(K + 1)] for i in range(dig)]
        DPsmall[0][0] = 1
        DPsmall[0][1] = int(strN[0]) - 1
        for i in range(1, dig):
            DPsmall[i][0] = 1
            for j in range(1, K + 1):
                DPsmall[i][j] += DPsmall[i-1][j-1] * 9 + DPsmall[i-1][j]
            
        DPlarge = [[0 for j in range(K + 1)] for i in range(dig)] 
        DPlarge[0][0] = 1
        for i in range(1, dig):
            if strN[i] == "0": DPlarge[i][0] = DPlarge[i-1][0]
            else: DPlarge[i][0] = DPlarge[i-1][0] + 1
            for j in range(1, K + 1):
                if DPlarge[i-1][0] == j - 1: DPlarge[i][j] += (int(strN[i]) - 1 if strN[i] != "0" else 0)
                if DPlarge[i-1][0] == j: DPlarge[i][j] += (1 if strN[i] != "0" else 0)

                DPlarge[i][j] += DPlarge[i-1][j] 
                if j > 1: DPlarge[i][j] += DPlarge[i-1][j-1] * 9 

        ans = DPsmall[dig-1][K] + DPlarge[dig-1][K]
        if DPlarge[dig-1][0] == K: ans += 1
        print(ans)   
        
        

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
S = input().strip()
K = int(input())
N = len(S)
def cmb(n, r):
    nn = n
    rrr = r
    rr = 1
    for i in range(r):
        rr *= n
        n -= 1
    for i in range(r):
        rr //= r
        r -= 1

    return rr

d = dict()
def f(k, i):
    if (k, i) in d:
        return d[(k, i)]
    if i == N:
        if k==0:
            return 1
        else:
            return 0
    dd = int(S[i])
    if k!=0:
        if dd == 0:
            rn = 0
            rm = 0
            r0 = f(k, i+1)
        else:
            rn = (dd-1)*cmb(N-i-1, k-1)*(9**(k-1))
            rm = f(k-1, i+1)
            r0 = cmb(N-i-1, k)*(9**k)
    else:
        rn = 0
        rm = 0
        r0 = f(k, i+1)
    d[(k,i)] = rm+rn+r0

    return rm + rn + r0

print(f(K, 0))

Solution (Python):

import sys





  


def countInRangeUtil(pos, cnt, tight, num, K): 
  
    
    if pos == len(num): 
  
        
        
        if cnt == K: 
            return 1
        return 0
  
    
    
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    
    
    
    
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        
        
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        
        
        if dig < num[pos]: 
            currTight = 1
  
        
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num, K) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  



def countInRange(x, K): 
    global dp, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num, K) 

def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return



dp = []
M = 100

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

if __name__ == '__main__':
    main()

Solution (Python):
from scipy.misc import comb

def f(n_str, k):
  while len(n_str) > 0 and n_str[0] == '0':
    n_str = n_str[1:]
  if len(n_str) < k:
    return 0
  if k == 1:
    return int(n_str[0]) + 9 * (len(n_str) - 1)
  else:
    return (int(n_str[0]) - 1) * f('9' * (len(n_str) - 1), k - 1) + f(n_str[1:], k - 1) + 9 ** k * (comb(len(n_str) - 1, k, exact=True) if len(n_str) > k else 0)

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

print(f(n, k))

Solution (Python):

from collections import deque

def comb(a, b):
    result = 1
    for i in range(b):
        result *= (a - i) / (i + 1)
    return result

def zero_num(n, k):
    if k == 0:
        return 1
    if len(n) == 0:
        return 0
    if n[0] == 0:
        return zero_num(n[1:], k)

    rest = comb(len(n) - 1, k) * 9 ** k
    rest += (n[0]-1) * comb(len(n) - 1, k-1) * 9 ** (k-1)
    return int(rest + zero_num(n[1:], k-1))


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

    print(zero_num(N, K))


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations
N = int(input())
K = int(input())
s = []
n = N
while(N > 0):
    if N > 10:
        s.append(9)
    else:
        s.append(N-1)
    N = N // 10
ans = 0
for x in combinations(s, K):
    tmp = 1
    for i in range(K):
        tmp *= x[i]
    ans += tmp

if K == 1:
    print(ans + 1)
    exit(0)

for x in combinations(range(len(s)-1), K - 1):
    tmp = (10**(len(s)-1))*(s[-1]+1)
    for j in range(9, 0, -1):
        if K-1 == 2:
            for k in range(9, 0, -1):
                if tmp + ((10**x[1])*j) + ((10**x[0])*k) <= n:
                    ans += k
                    break

        elif K - 1 == 1:
            if tmp + ((10 ** x[0]) * j) <= n:
                ans += j
                break


print(ans)

Solution (Python):







def countInRangeUtil(pos, cnt, tight, num): 

	
	if pos == len(num): 

		
		
		if cnt == K: 
			return 1
		return 0

	
	
	if dp[pos][cnt][tight] != -1: 
		return dp[pos][cnt][tight] 

	ans = 0

	
	
	
	
	limit = 9 if tight else num[pos] 

	for dig in range(limit + 1): 
		currCnt = cnt 

		
		
		if dig != 0: 
			currCnt += 1

		currTight = tight 

		
		
		if dig < num[pos]: 
			currTight = 1

		
		ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 

	dp[pos][cnt][tight] = ans 
	return dp[pos][cnt][tight] 




def countInRange(x): 
	global dp, K, M 
	num = [] 
	while x: 
		num.append(x % 10) 
		x //= 10
	num.reverse() 
	dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
	return countInRangeUtil(0, 0, 0, num) 




dp = [] 
M = 101


K = 0

L = 1
R = int(input())
K = int(input())
print(countInRange(R) - countInRange(L - 1))

Solution (Python):
n = int(input())
k = int(input())
def f(n,k):
  m = len(str(n))
  if n < 10^4:
    s = 0
    for i in range(1,n+1):
      if sum([1 for j in str(i) if j!="0"])==k:
        s += 1
  else:
    if k==1:
      s = n//(10**(m-1)) + 9*(m-1)
    elif k==2:
      s = (n//(10**(m-1))-1)*9*(m-1) + f(n%(10**(m-1)),1) + 9*9*(m-1)*(m-2)//2
    elif k==3:
      s = (n//(10**(m-1))-1)*9*9*(m-1)*(m-2)//2 + f(n%(10**(m-1)),2) + 9*9*9*(m-1)*(m-2)*(m-3)//6
  return s
print(f(n,k))

Solution (Python):
from itertools import combinations

def c(N, K):
    for i, n in enumerate(N):
        if n != 0:
            break
    N = N[i:]
    a = len(N)
    if a < K:
        return 0
    if K == 1:
        return N[0] + 9 * (a - 1)
    return (N[0] - 1) * c([9] * (a - 1), K - 1) + c(N[1:], K - 1) + c([9] * (a - 1), K)

def main():
    N = list(map(int, input()))
    K = int(input())
    return c(N, K)
    

print(main())

Solution (Python):
N = input()
n = int(N)
l = len(N)
k = int(input())
ans = 0
tmp = 0
def c(x,y):
  z = 1
  for w in range(y):
    z *= x - w
    z /= y - w
  return z

for i in range(l):
  for d in range(10):
    if d < int(N[i]):
      if d == 0 and k - tmp >= 0:
        now = c(l-1-i,k-tmp) * 9**(k-tmp)
        ans += now
        
      elif k - tmp - 1 >= 0:
        now =  c(l-1-i,k-tmp-1) * 9**(k-tmp-1)
        ans += now
        
    elif d == int(N[i]):
      if d != 0:
        tmp += 1
if k == tmp:
  ans += 1
print(int(ans))

Solution (Python):
N=input()
k=int(input())
ln=len(N)
DP=[[[0]*2 for _ in range(k+1)] for _ in range(len(N)+1)]
DP[0][0][0]=1
for i in range(1,len(N)+1):
  DP[i][0][1]=1
for i in range(len(N)):
  ni=int(N[i])
  for j in range(1,k+1):
    DP[i+1][j][1]=DP[i][j][1]+max(0,ni-1)*DP[i][j-1][0]+9*DP[i][j-1][1]
    if ni==0:
      DP[i+1][j][0]=DP[i][j][0]
    else:
      DP[i+1][j][0]=DP[i][j-1][0]
      DP[i+1][j][1]+=DP[i][j][0]
print(DP[ln][k][0]+DP[ln][k][1])

Solution (Python):
def main(N,K):

    if K == 1:
        return int(N[0]) + 9 * (len(N)-1)
    if K == 2:
        if len(N) == 1:
            return 0
        less = (len(N)-1) * (len(N)-2) // 2 * 9 * 9
        mid = (len(N)-1) * 9 * (int(N[0])-1)
        for i in range(1,len(N)):
            if N[i] != "0":
                break
        one = main(N[i:],1)
        return less+mid+one
    if K == 3:
        if len(N) < 3:
            return 0
    less = (len(N)-1) * (len(N)-2) * (len(N)-3) // 6 * 9 * 9 * 9
    mid = (int(N[0])-1) * (len(N)-1) * (len(N)-2) // 2 * 9 * 9
    for i in range(1,len(N)):
        if N[i] != "0":
            break
    one = main(N[i:],2)
    return (less+mid+one)
        
print(main(input(),int(input())))

Solution (Python):
N = input()
K = int(input())
l = len(N)
if K == 1:
    a = int(N[0])
    ans1 = 9*(l-1)+a
if K == 2:
    a=int(N[0])
    ans2 =(a-1)*9*(l-1)
    state = 0
    for n in N[1:]:
        if state:
            ans2 += 9
            continue
        if int(n) != 0:
            state = 1
        n = int(n)
        ans2 += n
    for i in range(2,l):
        ans2 += 81*(i-1)
    if l < K:
        ans2 = 0
if K == 3:
    a = int(N[0])
    ans3 = (a-1)*81*(l-1)*(l-2)/2
    state = 0
    for i in range(1,l):
        n = int(N[i])
        if state:
            ans3 += 81*(l-i-1)
            continue
        if n !=0:
            state = 1
        else:
            continue
        S = 0
        for j in range(i+1,l):
            m = int(N[j])
            if S:
                ans3 += n*9
                continue
            if m != 0:
                S = 1
            ans3 += (n-1)*9+m
    for i in range(3,l):
        ans3 += 729*(i-1)*(i-2)/2
    if l < K:
        ans3 = 0
if K == 1:
    print(ans1)
if K == 2:
    print(int(ans2))
if K == 3:
    print(int(ans3))