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):
from math import factorial

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

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


ans = 0

if len(str(n)) < k:
    print(0)
    exit()

def ans1(n,k):
    global ans
    m = len(str(n))
    if m-1 >= k:
        ans += combinations_count(m-1, k) * 9 ** k

    if m >= k:
        ans += (int(str(n)[0])-1) * combinations_count(m-1, k-1) * 9 ** (k-1)
        if k >= 2 and m > 1:
            ans1(int(str(n)[1:]), k-1)
        elif k == 1:
            ans += 1

ans1(n,k)

print(ans)

Solution (Python):
import itertools

def comb(a,b):
    if a<=0:
        return 0
    if b==1:
        return a
    elif b==2:
        return a*(a-1)//2
    else:
        return a*(a-1)*(a-2)//6

def tmp(L, K):
    ret=[]
    if K==1:
        bases=itertools.combinations(range(L+1),K)    
        for b in bases:
            ret+=[ k*10**b[0] for k in range(1,10)]
    if K==2:
        bases=itertools.combinations(range(L+1),K)
        kk=list(itertools.product(range(1,10),range(1,10)))
        for b in bases:
            ret+=[ k[0]*10**b[0] + k[1]*10**b[1] for k in kk]
    return ret

Nst=input()
K=int(input())
L=len(Nst)
N1=int(Nst[0])

if K==1:
    ans=comb( L-1, K) * 9 + N1
elif K>=2:
    ans=comb( L-1, K) * 9**(K) + comb( L-1, K-1) * 9**(K-1) *(N1-1)
    lst=[ 10**(L-1)*N1 + a for a in tmp(L-1, K-1)]
    ans+=sum([x <= int(Nst) for x in lst])
print (ans)

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

    def digit_dp(n):  
        """n 以下の非負整数で、0でない数字がちょうど K 個あるような数の個数"""
        digit = len(n)

        dp = [[[0] * (K + 2) for j in range(2)] for i in range(digit + 1)]
        dp[0][0][0] = 1
        for i in range(digit):
            for j in range(2):
                for k in range(K + 1):
                    lim = 9 if j == 1 else ord(n[i]) - ord('0')
                    for d in range(lim + 1):
                        if d != 0:
                            t = k + 1
                            if t >= K + 2:
                                t = K + 1
                        else:
                            t = k
                        dp[i + 1][j or (d < lim)][t] += dp[i][j][k]
        return sum(dp[digit][j][K] for j in range(2))
    return digit_dp(N)

print(e_almost_everywhere_zero())

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


keta = len(N)

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

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

for i in range(keta):
    now_digit = int(N[i])
    for k in range(10):
        for j in range(K+1):
            if k == 0:
                if k < now_digit:
                    dp[i+1][j][1] += dp[i][j][1] + dp[i][j][0]
                elif k == now_digit:
                    dp[i+1][j][1] += dp[i][j][1]
                    dp[i+1][j][0] += dp[i][j][0]
                else:
                    dp[i+1][j][1] += dp[i][j][1]
            else:
                if k < now_digit:
                    dp[i+1][j+1][1] += dp[i][j][1] + dp[i][j][0]
                elif k == now_digit:
                    dp[i+1][j+1][1] += dp[i][j][1]
                    dp[i+1][j+1][0] += dp[i][j][0]
                else:
                    dp[i+1][j+1][1] += dp[i][j][1]
print(dp[-1][K][0] + dp[-1][K][1])

Solution (Python):


from collections import defaultdict

con = 10 ** 9 + 7

def getlist():
	return list(map(int, input().split()))


def main():
	N = list(list(map(int, list(input()))))
	K = int(input())
	
	
	M = len(N)
	DP = [[[0] * 4 for i in range(M)] for j in range(2)]
	
	DP[0][0][1] = 1
	DP[1][0][1] = N[0] - 1
	for i in range(1, M):
		if N[i] == 0:
			DP[0][i][1] += DP[0][i - 1][1]
			DP[0][i][2] += DP[0][i - 1][2]
			DP[0][i][3] += DP[0][i - 1][3]

			DP[1][i][1] += DP[1][i - 1][1]
			DP[1][i][2] += DP[1][i - 1][1] * 9 + DP[1][i - 1][2]
			DP[1][i][3] += DP[1][i - 1][2] * 9 + DP[1][i - 1][3]
		else:
			DP[0][i][2] += DP[0][i - 1][1]
			DP[0][i][3] += DP[0][i - 1][2]

			DP[1][i][2] += DP[0][i - 1][1] * (N[i] - 1)
			DP[1][i][3] += DP[0][i - 1][2] * (N[i] - 1)
			DP[1][i][1] += DP[0][i - 1][1]
			DP[1][i][2] += DP[0][i - 1][2]
			DP[1][i][3] += DP[0][i - 1][3]

			DP[1][i][1] += DP[1][i - 1][1]
			DP[1][i][2] += DP[1][i - 1][1] * 9 + DP[1][i - 1][2]
			DP[1][i][3] += DP[1][i - 1][2] * 9 + DP[1][i - 1][3]
		DP[1][i][1] += 9

	ans = DP[0][M - 1][K] + DP[1][M - 1][K]
	
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
def two(n):
  n = str(n)
  top = int(n[0])
  b = len(n) - 1
  ans = b * (b-1) // 2 * 81 + (top-1) * b * 9 
  if b == 0:
    return 0
  for k,i in enumerate(n[1:],1):
    i = int(i)
    if i:
      ans += i + (b - k) * 9
      break
  return ans

n = int(input())
k = int(input())
if k == 1:
  n = str(n)
  top = int(n[0])
  ans = (len(n)-1) * 9 + top
  print(ans)
elif k == 2:
  n = str(n)
  top = int(n[0])
  b = len(n) - 1
  ans = b * (b-1) // 2 * 81 + (top-1) * b * 9 
  if b == 0:
    print(0)
    exit()
  for k,i in enumerate(n[1:],1):
    i = int(i)
    if i:
      ans += i + (b - k) * 9
      break
  print(ans)
elif k == 3:
  n = str(n)
  top = int(n[0])
  b = len(n) - 1
  if b <= 1:
    print(0)
    exit()
  ans = b * (b-1) * (b-2) // 6 * 729 + (top-1) * b * (b-1) // 2 *81
  n = int(n)
  t = n % (top * (10 ** b))
  mini_ans = two(t)
  ans += mini_ans
  print(ans)

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

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
print(countInRange(N))

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

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

LN = len(str(N))

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])



def keta2(n):
    if n < 10:
        return 0
    cnt2 = [0] * 101
    for i in range(2, 101):
        cnt2[i] = 9 * 9 * (i - 1)
    tmp2 = 0
    for i in range(len(str(n))):
        tmp2 += cnt2[i]
    tmp2 += (int(str(n)[0]) - 1) * keta1((10 ** (len(str(n))  - 1)) - 1) + keta1(int(str(n)[1:]))
    return tmp2

def keta3(n):
    cnt3 = [0] * 101
    for i in range(3, 101):
        cnt3[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    tmp3 = 0
    for i in range(len(str(n))):
        tmp3 += cnt3[i]
    tmp3 += (int(str(N)[0]) - 1) * keta2((10 ** (len(str(n))  - 1)) - 1) + keta2(int(str(n)[1:]))
    
    return tmp3

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

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

def sol1(n):
    l=len(str(n))
    
    return int(str(n)[0])+9*(l-1)

def sol2(n):
    ret=0
    a=int(str(n)[0])
    l=len(str(n))-1
    ret+=sol1(n-a*10**l)
    ret+=(a-1)*sol1(10**l-1)
    ret+=9*9*l*(l-1)//2
    return ret

def sol3(n):
    ret=0
    a=int(str(n)[0])
    l=len(str(n))-1
    ret+=sol2(n-a*10**l)
    ret+=(a-1)*sol2(10**l-1)
    ret+=9*9*9*l*(l-1)*(l-2)//6
    return ret


if k==1:
    print(sol1(n))
elif k==2:
    print(sol2(n))
elif k==3:
    print(sol3(n))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = str(I())
K = I()
digit_len = len(n)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(digit_len + 1)]
dp[0][0][0] = 1
for i in range(digit_len):
    d = int(n[i])
    for j in range(2):
        for k in range(K + 1):
            for l in range(10 if j else d + 1):
                if k + bool(l) <= K:
                    dp[i + 1][j or (l < d)][k + bool(l)] += dp[i][j][k]



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

Solution (Python):
def fact(n):
    x = 1
    for i in range(1, n + 1):
        x *= i
    return x


def nCr(n, r):
    return fact(n) // (fact(n - r) * fact(r))


def solve(N, K):
    if N < int("1" * K):
        return 0
    digits = [int(c) for c in str(N)]
    places = len(digits)
    count = 0
    for i in range(K - 1, places):
        
        firstChoice = 9
        if i == places - 1:
            
            firstChoice = digits[0] - 1
        count += firstChoice * (9 ** (K - 1)) * nCr(i, K - 1)
    
    if K == 1:
        count += 1
    else:
        count += solve(int("".join(map(str, digits[1:]))), K - 1)
    return count


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

print(solve(N, K))

Solution (Python):
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = input()
digit = len(N)
K = I()


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

for i in range(digit):
  num = int(N[i])
  for j in range(2):
    for k in range(K+2):
      for n in range(9+1 if j else num+1):
        dp[i + 1][j or (n < num)][min(K+1, k + (n != 0))] += dp[i][j][k]
print(dp[digit][0][K] + dp[digit][1][K])

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

def count(n, k):
    if len(n) < k:
        return 0
    if k == 0:
        return 1
    if int(n) == 0:
        return 0
    if n[0] == "0":
        return count(n[1:], k)
    return count(n[1:], k-1) + comb(len(n)-1, k)*9**(k) + (int(n[0])-1)*comb(len(n)-1, k-1)*9**(k-1)

n = input()
k = int(input())
print(count(n, k))

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

def comb(n, r):
    if r > n or r < 0: return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result

n, k = map(int, sys.stdin.read().split())

def solve(n, k):
    p = int(str(n)[0])
    l = len(str(n))

    if k == 1:
        return 9 * (l - 1) + p
    
    elif k == 2:
        if l <= 1:
            return 0
        res = 0
        for i in range(1, l-1):
            res += comb(i, 1) * 9 * 9
        res += comb(l-1, 1) * 9 * (p - 1)
        res += solve(int(str(n)[1:]), 1)
        return res
    
    elif k == 3:
        if l <= 2:
            return 0
        res = 0
        for i in range(2, l-1):
            res += comb(i, 2) * 9 ** 2 * 9
        res += comb(l-1, 2) * 9 ** 2 * (p - 1)
        res += solve(int(str(n)[1:]), 2)
        return res

def main():
    return solve(n, k)

if __name__ == '__main__':
    ans = main()
    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) 

n = int(input())
K = int(input())
dp = []
M = 100
print(countInRange(n) - countInRange(0))

Solution (Python):
n = int(input())
k = int(input())
s = str(n)
d = len(s)
c = 0
if k == 1:
  c += 9*(d-1)
if k == 2:
  c += 9*9*(((d-1)*(d-2))//2)
if k == 3:
  c += 3*9*9*(((d-1)*(d-2)*(d-3))//2)
if k == 1:
  c +=  int(s[0])
  print(c)
  exit()
if k == 2:
  s0 = int(s[0])
  c += (s0-1)*9*(d-1)
  for i in range(1,d):
    if int(s[i]) != 0:
      si = int(s[i])
      c += si + 9*(d-i-1)
      break
  print(c)
  exit()
if k == 3:
  s0 = int(s[0])
  c += (s0-1)*9*9*((d-1)*(d-2)//2)
  mi = 0
  for i in range(1,d):
    if int(s[i]) != 0:
      si = int(s[i])
      c += (si-1)*9*(d-i-1)+9*9*(d-i-1)*(d-i-2)//2
      mi = i
      break
  if mi != 0:
    for j in range(mi+1,d):
      if int(s[j]) != 0:
        sj = int(s[j])
        c += sj + 9*(d-j-1)
        break
  print(c)
  exit()

Solution (Python):
n=int(input())
k=int(input())
l=len(str(n))
a=(l-1)*(l-2)*(l-3)//6*9**3
if k==2:
  a=(l-1)*(l-2)//2*9*9
elif k==1:
  a=(l-1)*9
sn=list(str(n))
c=0
for i in range(l):
  p=sn[i]
  if p != "0":
    if k-c == 3:
      a+=(l-i-1)*(l-i-2)//2*(int(p)-1)*9*9
    elif k-c == 2:
      a+=(l-i-1)*(int(p)-1)*9
      if not k==2:
        a+=(l-i-1)*(l-i-2)//2*9*9
    elif k-c == 1:
      a+=int(p)
      if not k==1:
        a+=(l-i-1)*9
    c+=1
    if c==k:
      break
print(a)

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 = 100
N = int(input())
K = int(input())

print(countInRange(N))

Solution (Python):
import sys


TEST_INPUT = [
    """
    100
    1
    """,
    """
    25
    2
    """,
    """
    314159
    2
    """,
    """
    9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
    3
    """
]
ANSWER = [
    "19",
    "14",
    "937",
    "117879300"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def solve(n, k):
    res = 0
    le = len(n) - 1

    
    if k == 1 and le >= 1:
        res += 9 * le
    if k == 2 and le >= 2:
        res += 9 * 9 * le * (le - 1) // 2
    if k == 3 and le >= 3:
        res += 9 * 9 * 9 * le * (le - 1) * (le - 2) // 6

    
    if k == 1:
        res += int(n[0]) - 1
    if k == 2:
        res += (int(n[0]) - 1) * (9 * le)
    if k == 3:
        res += (int(n[0]) - 1) * (9 * 9 * le * (le - 1) // 2)

    
    if k == 1:
        res += 1
    if k == 2:
        
        for i in range(1, le + 1):
            if int(n[i]) > 0:
                res += int(n[i])
                res += 9 * (le - i)
                break
    if k == 3:
        j = 0
        
        for i in range(1, le + 1):
            if int(n[i]) > 0:
                res += (int(n[i]) - 1) * 9 * (le - i)
                res += 9 * 9 * ((le - i) * (le - i - 1) // 2)
                j = i
                break
        
        for i in range(j + 1, le + 1):
            if int(n[i]) > 0:
                res += int(n[i])
                res += 9 * (le - i)
                break
    return res


def input_and_solve(ih):
    n = ih.input()
    k = int(ih.input())
    res = solve(n, k)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()

Solution (Python):
n=int(input())
k=int(input())
def k1(n):
    n_l=len(str(n))
    n_0=int(str(n)[0])
    return n_0+9*(n_l-1)
def k2(n):
    n_l=len(str(n))
    if n_l<=1:
        return 0
    n_0=int(str(n)[0])
    return 81*((n_l-1)*(n_l-2)//2)+(n_0-1)*9*(n_l-1)+k1(n%(10**(n_l-1)))
def k3(n):
    n_l=len(str(n))
    if n_l<=2:
        return 0
    n_0=int(str(n)[0])
    return 729*((n_l-1)*(n_l-2)*(n_l-3)//6)+(n_0-1)*81*((n_l-1)*(n_l-2)//2)+k2(n%(10**(n_l-1)))
if k==1:
    print(k1(n))
if k==2:
    print(k2(n))
if k==3:
    print(k3(n))

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

def mCk(m, k):
  if k == 3:
    return m * (m - 1) * (m - 2) // 6
  elif k == 2:
    return m * (m - 1) // 2
  elif k == 1:
    return m
  return None

def count_up(n, k):
  digit_n = len(n)
  if digit_n < k: 
    return 0
  top_n = int(n[0])
  if k == 1:
    return (top_n + 9 * (digit_n - 1))
  return (
    count_up(str(int(n[1:])), k - 1) 
    + (top_n - 1) * mCk(digit_n - 1, k - 1) * (9 ** (k - 1))
    + mCk(digit_n - 1, k) * (9 ** k)
  )


def main():
  n = input() 
  k = int(input())
  print(count_up(n, k))

if __name__ == "__main__":
  main()

Solution (Python):
def main():
    from itertools import combinations

    N = raw_input()
    K = int(raw_input())
    digit = len(N)
    N = int(N)


    ans = 0

    
    ans += len(list(combinations(range(digit - 1), K))) * (9 ** K)

    if K == 3:
        
        for top in range(1, 10):
            if int(str(N)[0]) < top:
                continue

            if int(str(N)[0]) > top:
                ans += len(list(combinations(range(digit - 1), K - 1))) * (9 ** (K - 1))
                continue

            for perm_digit in combinations(range(1, digit), K - 1):
                perm_digit = list(perm_digit)
                for pn1 in range(1, 10):
                    for pn2 in range(1, 10):
                        s = ['0'] * digit
                        s[0] = str(top)
                        s[perm_digit[0]] = str(pn1)
                        s[perm_digit[1]] = str(pn2)

                        if int(''.join(s)) <= N:
                            ans += 1

    elif K == 2:
        
        for top in range(1, 10):
            for perm_digit in combinations(range(1, digit), K - 1):
                perm_digit = list(perm_digit)

                for pn1 in range(1, 10):
                    s = ['0'] * digit
                    s[0] = str(top)
                    s[perm_digit[0]] = str(pn1)
                    if int(''.join(s)) <= N:
                        ans += 1

    elif K == 1:
        ans += int(str(N)[0])

    print(ans)


if __name__ == '__main__':
    main()

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):
import math
n=int(input())
k=int(input())
strn=str(n)

ans1=9*(len(strn)-1)+int(strn[0])


def fuc1(x):
    strn=str(x)
    return 9*(len(strn)-1)+int(strn[0])

def fuc2(x):
    if x<10:
        return 0
    strn=str(x)
    ans2=fuc1(int(strn[1:]))
    ans2+=(int(strn[0])-1)*(9*(len(strn)-1))
    
    for i in range(1,len(strn)-1):
        ans2+=9*(9*(len(strn)-i-1))
    return ans2

def fuc3(x):
    if x<100:
        return 0
    ans3=fuc2(int(strn[1:]))
    ans3+=(int(strn[0])-1)*(81*(len(strn)-1)*(len(strn)-2)//2)
    
    for i in range(1,len(strn)-2):
        ans3+=9*(81*(len(strn)-i-1)*(len(strn)-i-2)//2)
    
    return ans3

if k==1:
    print(fuc1(n))
if k==2:
    print(fuc2(n))
if k==3:
    print(fuc3(n))

Solution (Python):
import os
import sys

import numpy as np

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

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


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

DIGIT = len(N)

dp = np.zeros((DIGIT + 1, K + 1, 2), dtype=int)
dp[0, 0, 0] = 1
for d in range(1, DIGIT + 1):
    nd = int(N[d - 1])
    if nd > 0:
        dp[d, :, 1] += dp[d - 1, :, 0]
        dp[d, :, 1] += dp[d - 1, :, 1]
        for k in range(1, K + 1):
            
            dp[d][k][0] += dp[d - 1][k - 1][0]
            dp[d][k][1] += dp[d - 1][k - 1][0] * (nd - 1)
            dp[d][k][1] += dp[d - 1][k - 1][1] * 9
    else:
        dp[d, :, 0] += dp[d - 1, :, 0]
        dp[d, :, 1] += dp[d - 1, :, 1]
        for k in range(1, K + 1):
            
            dp[d][k][1] += dp[d - 1][k - 1][1] * 9
print(dp[-1][K].sum())

Solution (Python):
import sys
n = int(input())
k = int(input())
n_keta = len(str(n))
memo_ls = [[[0 for _k in range(2)] for j in range(k+2)] for i in range(n_keta + 1)] 
memo_ls[0][0][0] = 1
for i, base in enumerate(str(n), 1):
    base = int(base)
    for j in range(10):
        for _k in range(k+1):
            if j > base:
                memo_ls[i][_k+1][1] += memo_ls[i-1][_k][1]
            elif j == base:
                if j == 0:
                    memo_ls[i][_k][0] += memo_ls[i-1][_k][0]
                    memo_ls[i][_k][1] += memo_ls[i - 1][_k][1]
                else:
                    memo_ls[i][_k+1][1] += memo_ls[i-1][_k][1]
                    memo_ls[i][_k+1][0] += memo_ls[i-1][_k][0]
            else:
                if j == 0:
                    memo_ls[i][_k][1] += memo_ls[i-1][_k][1] + memo_ls[i - 1][_k][0]
                else:
                    memo_ls[i][_k+1][1] += memo_ls[i-1][_k][1] + memo_ls[i-1][_k][0]
print(sum(memo_ls[-1][k]))

Solution (Python):
def main():
    N = input()
    K = int(input())
    t = len(N)
    if K == 1:
        return (t - 1) * 9 + int(N[0])
    elif K == 2:
        if t < 2:
            return 0
        r = (t - 1) * (t - 2) * 81 // 2
        r += (int(N[0]) - 1) * (t - 1) * 9
        for i, v in enumerate(N):
            if i < 1:
                continue
            if v != '0':
                r += int(v) + 9 * (t - 1 - i)
                return r
        return r
    else:
        if t < 3:
            return 0
        r = (t - 1) * (t - 2) * (t - 3) * 729// 6
        r += (int(N[0]) - 1) * (t - 1) * (t - 2) * 81 // 2
        second = False
        for i, v in enumerate(N):
            if i < 1:
                continue
            if v != '0' and not second:
                r += (int(v)-1) * (t - 1 - i) * 9
                r += (t - 1 - i) * (t - 2 - i) * 81 // 2
                second = True
            elif v != '0':
                r += int(v) + 9 * (t - 1 - i)
                return r
        return r
print(main())

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
import pdb
     
def main():
    N = S()
    K = I()
    dp = [[[0 for _ in range(102)] for __ in range(2)] for ___ in range(102)]
    dp[0][0][0] = 1
    for i in range(1, len(N)+1):
        for j in range(2):
            if j == 1:
                max_dig = 9
            else:
                max_dig = int(N[i-1])
            for k in range(i+1):
                for d in range(max_dig + 1):
                    if d < max_dig:
                        
                        miman = 1
                    else:
                        miman = 0
                        if j == 1:
                            miman = 1
                    if d != 0:
                        newK = k + 1
                    else:
                        newK = k
                    dp[i][miman][newK] += dp[i-1][j][k]

    print(dp[len(N)][0][K] + dp[len(N)][1][K])
main()

Solution (Python):
n=int(input())
K=int(input())
n_list=[]
while n>=10:
    n_list.append(n%10)
    n=(n-n%10)//10
n_list.append(n)
n_list.reverse()
x=len(n_list)
dp=[[[0]*100,[0]*100] for i in range(x+1)]
dp[0][1][0]=1
for i in range(x):
    for k in range(99):
        dp[i+1][0][k]+=dp[i][0][k]
        dp[i+1][0][k+1]+=dp[i][0][k]*9
    if n_list[i]==0:
        for k in range(99):
            dp[i+1][1][k]+=dp[i][1][k]
    else:
        n=n_list[i]
        for k in range(99):
            dp[i+1][1][k+1]+=dp[i][1][k]
            dp[i+1][0][k]+=dp[i][1][k]
            dp[i+1][0][k+1]+=dp[i][1][k]*(n-1)
ans=dp[x][0][K]+dp[x][1][K]
print(ans)

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

LEN=len(N)

from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(keta,use,coin):
    ANS=0

    if keta==LEN:
        if use==K:
            return 1
        return 0
        
    if coin==0:
        if use<K:
            ANS+=dfs(keta+1,use+1,0)*9
        ANS+=dfs(keta+1,use,0)

        return ANS

    else:
        kn=int(N[keta])

        if kn==0:
            return dfs(keta+1,use,1)

        ANS+=dfs(keta+1,use,0)
        ANS+=dfs(keta+1,use+1,0)*(kn-1)
        ANS+=dfs(keta+1,use+1,1)

        return ANS

print(dfs(0,0,1))

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

dp = [[0] * 4 for _ in range(2)]
dp[0][1] = 1
dp[1][0] = 1
dp[1][1] = int(N[0]) - 1

for n in N[1:] :
  n = int(n)
  ndp = [[0] * 4 for _ in range(2)]
  
  if n == 0 :
    ndp[0] = dp[0]
  else :
    ndp[0][1] = dp[0][0]
    ndp[0][2] = dp[0][1]
    ndp[0][3] = dp[0][2]

  ndp[1][0] = dp[1][0]
  ndp[1][1] = dp[1][1] + dp[1][0] * 9
  ndp[1][2] = dp[1][2] + dp[1][1] * 9
  ndp[1][3] = dp[1][3] + dp[1][2] * 9
    
  if n != 0 :
    ndp[1][0] += dp[0][0]
    ndp[1][1] += dp[0][0] * (n - 1) + dp[0][1]
    ndp[1][2] += dp[0][1] * (n - 1) + dp[0][2]
    ndp[1][3] += dp[0][2] * (n - 1) + dp[0][3]
  
  dp = ndp
  
print(dp[0][K] + dp[1][K])

Solution (Python):
n = int(input())
k = int(input())
from math import log10, ceil


def helper(n, k):
    if k == 0:
        return 1
    if k >= 1 and n == 0:
        return 0

    keta = ceil(log10(n))
    if n == 10 ** (keta):
        keta += 1
    count = 0
    for tmp_keta in range(1, keta):
        if tmp_keta >= k:
            add_no = 9
            if k == 2:
                add_no *= 9 * (tmp_keta - 1)
            if k == 3:
                add_no *= 81 * int((tmp_keta - 2) * (tmp_keta - 1) / 2)
            count += add_no

    top = n // (10 ** (keta - 1))
    amari = n % (10 ** (keta - 1))
    if keta >= k:
        add_no = 1
        if k == 2:
            add_no *= 9 * (keta - 1)
        if k == 3:
            add_no *= 81 * int((keta - 2) * (keta - 1) / 2)
        count += add_no * (top - 1)
        count += helper(amari, k - 1)
    return count


print(helper(n, k))