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

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





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


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

x0=int(N[0])

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

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

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

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

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

Solution (Python):
def main():
    NOT_DET = 0
    SMALLER = 1

    s = input()
    n = len(s)  

    k = int(input())

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

    for i, ci in enumerate(s):
        for j in range(k + 1):
            dp[i + 1][j][SMALLER] = (
                    dp[i][j][SMALLER]
                    + dp[i][j][NOT_DET] * (1 if ci != '0' else 0)
                    + (dp[i][j - 1][SMALLER] if j > 0 else 0) * 9
                    + (dp[i][j - 1][NOT_DET] if j > 0 else 0) * max(0, int(ci) - 1)
            )

            dp[i + 1][j][NOT_DET] = dp[i][j][NOT_DET] if ci == '0' else (
                dp[i][j - 1][NOT_DET] if j > 0 else 0)

    print(sum(dp[n][k]))


if __name__ == '__main__':
    main()

Solution (Python):
n = input()
k = int(input())
m = len(n)
if k == 1:
    print(int(n[0])+9*(m-1))
elif k == 2:
    if m<2:ans = 0
    else:
        ans = 81*(m-1)*(m-2)//2+(int(n[0])-1)*(m-1)*9
        for i in range(1,m):
            if int(n[i]) != 0:
                ans += (m-i-1)*9+int(n[i])
                break
    print(ans)
else:
    if m<3:ans = 0
    else:
        ans = (m-1)*(m-2)*(m-3)//6*9**3 + (int(n[0])-1)*(m-1)*(m-2)//2*81
        for i in range(1,m):
            if int(n[i])!=0:
                ans += (m-i-1)*(m-i-2)//2*81+(int(n[i])-1)*(m-i-1)*9
                break
        for j in range(i+1,m):
            if int(n[j]) != 0:
                ans += (m-j-1)*9+int(n[j])
                break
    print(ans)

Solution (Python):
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 = int(input())
K = int(input())
L = len(str(N))
S = str(N)
if K>L:
  print(0)
  import sys
  sys.exit()
if K==1:
  s = ['0']*L
  cnt = 0
  for i in range(L):
    for j in range(1,10):
      s[i] = str(j)
      x = ''.join(s)
      x = int(x)
      if x<=N:
        cnt += 1
      s[i] = '0'
elif K==2:
  s = ['0']*L
  cnt = 0
  for i in range(L-1):
    for j in range(i+1,L):
      for a in range(1,10):
        for b in range(1,10):
          s[i] = str(a)
          s[j] = str(b)
          x = ''.join(s)
          x = int(x)
          if x<=N:
            cnt += 1
          s[i] = '0'
          s[j] = '0'
else:
  s = ['0']*L
  cnt = 0
  cnt += cmb(L-1,3)*(9**3) if L>3 else 0
  g = int(S[0])
  s[0] = S[0]
  for i in range(1,L-1):
    for j in range(i+1,L):
      for a in range(1,10):
        for b in range(1,10):
          s[j] = str(a)
          s[i] = str(b)
          x = ''.join(s)
          x = int(x)

          if x<=N:
            cnt += g
          else:
            cnt += g-1
          s[i] = '0'
          s[j] = '0'
print(cnt)

Solution (Python):

import sys
input = sys.stdin.readline
INF = 10**9

n = input().rstrip()
k = int(input())


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

for i, ch in enumerate(n): 
    item = int(ch)
    if i == 0:
        
        dp[0][1][0] = 1
        
        dp[1][0][0] = 1
        
        dp[1][1][0] = max(0, item - 1)
        continue
    for j in range(k+1):
        if item != 0:
            
            dp[1][j][i] += dp[0][j][i-1]
            
            dp[1][j][i] += dp[1][j][i-1]
            if j < k:
                
                dp[0][j+1][i] += dp[0][j][i-1] 
                
                dp[1][j+1][i] += dp[0][j][i-1] * max(0, (item - 1))
                
                dp[1][j+1][i] += dp[1][j][i-1] * 9 
        else:
            
            dp[0][j][i] += dp[0][j][i-1] 
            
            dp[1][j][i] += dp[1][j][i-1] 
            if j < k:
                
                dp[1][j+1][i] += dp[1][j][i-1] * 9

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

Solution (Python):
def comb(n,k):
    if k==0:
        return 1
    elif k==1:
        return n
    elif k==2:
        return n*(n-1)/2

n = input()
k = int(input())
ans=0
for dgt in range(1,len(n)):
    if dgt<len(n):
        ans+=9**k*comb(dgt-1,k-1)
dgt=len(n)
cnt=0
for i in range(len(n)):
    if n[i] != '0' and cnt<k:
        cnt+=1
        ans+=(int(n[i])-1)*9**(k-cnt)*comb(dgt-i-1, k-cnt)
        if i:
            ans+=9**(k-cnt+1)*comb(dgt-i-1, k-cnt+1)

if cnt==k:
    ans+=1
print(int(ans))

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans



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

arr = ValueToArray10(n,100)
nonzero = [0 for i in range(101)]


for i in range(100):
    if(arr[i]!=0):
        nonzero[i+1] = nonzero[i]+1
    else:
        nonzero[i+1] = nonzero[i]
        


ans = 0

def c2(n):
    if(n<=1):
        return 0
    else:
        return n*(n-1)//2

def c3(n):
    if(n<=2):
        return 0
    else:
        return n*(n-1)*(n-2)//6

if(nonzero[100]==k):
    ans += 1

for ii in range(100):

    i = 99 - ii
    
    if(nonzero[i]>=k+1):
        continue
    else:
        if(arr[i]==0):
            continue
        else:
            rem = ii
            if(nonzero[i]==k):
                ans += 1
            elif(nonzero[i] == k-1):
                ans +=  rem * 9 + (arr[i]-1)
            elif(nonzero[i] == k-2):
                ans +=  c2(rem) * 81 + (arr[i]-1) * rem * 9
            elif(nonzero[i] == k-3):
                ans += c3(rem) * 729 + (arr[i]-1) * c2(rem) * 81
            

print(ans)

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

dp = [[[0,0] for i in range(len(n)+1)] for j in range(len(n)+1)]


num_d = len(n)

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

for i in range(len(n)):
    num = int(n[i])

    if num == 0:
        for j in range(num_d):
            dp[i+1][j+1][0] = dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][1]

        for j in range(num_d+1):
            dp[i+1][j][1] += dp[i][j][1]*9

    else:
        for j in range(num_d):
            dp[i+1][j][0] = dp[i][j][0]

        for j in range(num_d+1):
            dp[i+1][j][1] += dp[i][j][0]*(num-1)
            dp[i+1][j][1] += dp[i][j][1]*9

        for j in range(num_d):
            dp[i+1][j+1][1] += dp[i][j][0] + dp[i][j][1]


if num_d < k:
    print(0)
else:
    print(sum(dp[-1][num_d-k]))

Solution (Python):
nl = list(input())
k = int(input())
l = len(nl) - k


dp1 = [[0 for i in range(l+2)] for j in range(len(nl)+1)]
dp2 = [[0 for i in range(l+2)] for j in range(len(nl)+1)]
dp1[0][0] = 0
dp2[0][0] = 1
for i, t in enumerate(nl):
    t = int(t)
    for j in range(10):
        if j == 0:
            if j < t:
                for p in range(l+1):
                    dp1[i+1][p+1] += dp2[i][p]
                    dp1[i+1][p+1] += dp1[i][p]
            elif j == t:
                for p in range(l+1):
                    dp2[i+1][p+1] += dp2[i][p]
                    dp1[i+1][p+1] += dp1[i][p]
            else:
                for p in range(l+1):
                    dp1[i+1][p+1] += dp1[i][p]
        else:
            if j < t:
                for p in range(l+1):
                    dp1[i+1][p] += dp2[i][p]
                    dp1[i+1][p] += dp1[i][p]
            elif j == t:
                for p in range(l+1):
                    dp2[i+1][p] += dp2[i][p]
                    dp1[i+1][p] += dp1[i][p]
            else:
                for p in range(l+1):
                    dp1[i+1][p] += dp1[i][p]


print(dp1[-1][l] + dp2[-1][l])

Solution (Python):
import numpy as np

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

M = len(N)
dp = np.zeros((M+1, K+1, 2), int)


dp[0,0,0] = 1

for i in range(1,M+1):

    
    X = int(N[-i])
    
    
    dp[i,:,0] += dp[i-1,:,0]
    if X>0:
        dp[i,:,0] += dp[i-1,:,1]
    else:
        dp[i,:,1] += dp[i-1,:,1]
        
    for n in range(1,10): 
        if n<X:
            dp[i,1:,0] += dp[i-1,:-1,0] + dp[i-1,:-1,1]
        elif X==n:
            dp[i,1:,0] += dp[i-1,:-1,0]
            dp[i,1:,1] += dp[i-1,:-1,1]
        else:
            dp[i,1:,1] += dp[i-1,:-1,0] + dp[i-1,:-1,1]

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

Solution (Python):
from math import factorial


def comb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


N = input()
K = int(input())
ans = 0
if K == 1:
    for i in range(1, len(N)):
        ans += 9
    ans += int(N[0])
elif K == 2:
    for i in range(K, len(N)):
        ans += 81 * comb(i - 1, 1)
    for i1 in range(1, 10):
        for i2 in range(1, 10):
            for p in range(len(N) - 1):
                if str(i1) + "0" * (len(N) - p - 2) + str(i2) + "0" * p <= N:
                    ans += 1
elif K == 3:
    for i in range(K, len(N)):
        ans += 729 * comb(i - 1, 2)
    for i1 in range(1, 10):
        for i2 in range(1, 10):
            for i3 in range(1, 10):
                for p1 in range(1, len(N) - 1):
                    for p2 in range(p1):
                        st = str(i1) + "0" * (len(N) - p1 - 2) + str(i2) + \
                            "0" * (p1 - p2 - 1) + str(i3) + "0" * p2
                        if st <= N:
                            ans += 1

print(ans)

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

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

dp = [[[0, 0] for j in range(4)] for i in range(len(n)+1)]
dp[0][0][0] = 1

for i in range(len(n)):
    if int(n[i]) == 0:
        dp[i+1][0][0] = dp[i][0][0]
        dp[i+1][1][0] = dp[i][1][0]
        dp[i+1][2][0] = dp[i][2][0]
        dp[i+1][3][0] = dp[i][3][0]

    else:
        dp[i+1][1][0] = dp[i][0][0]
        dp[i+1][2][0] = dp[i][1][0]
        dp[i+1][3][0] = dp[i][2][0]
        dp[i+1][0][1] = dp[i][0][0]
        dp[i+1][1][1] = dp[i][1][0]
        dp[i+1][2][1] = dp[i][2][0]
        dp[i+1][3][1] = dp[i][3][0]

    dp[i+1][0][1] += dp[i][0][1]
    dp[i+1][1][1] += dp[i][1][1] + dp[i][0][1]*9 + dp[i][0][0]*max(int(n[i])-1, 0)
    dp[i+1][2][1] += dp[i][2][1] + dp[i][1][1]*9 + dp[i][1][0]*max(int(n[i])-1, 0)
    dp[i+1][3][1] += dp[i][3][1] + dp[i][2][1]*9 + dp[i][2][0]*max(int(n[i])-1, 0)


print(sum(dp[len(n)][k]))

Solution (Python):
def main():
    A = input()
    K = int( input())
    N = len(A)
    dp = [ [ [0]*(K+1) for _ in range(2)] for _ in range(N)]
    t = int( A[0])
    dp[0][0][1] = 1
    dp[0][1][1] = t-1
    for i in range(N):
        dp[i][1][0] = 1
    for i in range(1,N):
        t = int(A[i])
        if t == 0:
            for k in range(1,K+1):
                dp[i][0][k] = dp[i-1][0][k]
        else:
            for k in range(K):
                dp[i][0][k+1] = dp[i-1][0][k]
        if t == 0:
            for k in range(1,K+1):
                dp[i][1][k] = dp[i-1][1][k] + dp[i-1][1][k-1]*9
        else:
            for k in range(1,K+1):
                dp[i][1][k] = dp[i-1][1][k] + dp[i-1][1][k-1]*9 + dp[i-1][0][k-1]*(t-1) + dp[i-1][0][k]
    print(dp[N-1][0][K] + dp[N-1][1][K])
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):







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 comb(n, k):
  if n < k:
    return 0
  else:
    res = 1
    _n = n
    for _k in range(1, k+1):
      res *= _n
      res //= _k
      _n -= 1
    
    return res
    

N = input()
n = len(N)
K = int(input())

ans = comb(n-1, K) * (9**K)

if K == 1:
  ans += int(N[0])
elif K == 2:
  ans += comb(n-1, 1) * 9 * (int(N[0])-1)
  N = str(int(N) - int(N[0])*(10**(n-1)))
  n = len(N)
  ans += comb(n-1, 1) * 9
  ans += int(N[0])
else: 
  ans += comb(n-1, 2) * (9**2) * (int(N[0])-1)
  N = str(int(N) - int(N[0])*(10**(n-1)))
  n = len(N)
  ans += comb(n-1, 2) * (9**2)
  ans += comb(n-1, 1) * 9 * (int(N[0])-1)
  N = str(int(N) - int(N[0])*(10**(n-1)))
  n = len(N)
  ans += comb(n-1, 1) * 9
  ans += int(N[0])

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

k = len(N)
ans = 0

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


def solve(N,K):
    if len(N) < K:
        return 0
    if N[0] == '0':
        return solve(N[1:],K)
    if K == 1:
        return (len(N)-1)*9+int(N[0])
    res = 0
    if K == 2:
        res += (9**2)*(len(N)-1)*(len(N)-2)//2
        res += 9*(len(N)-1)*(int(N[0])-1)
        res += solve(N[1:],K-1)
    if K == 3:
        res += (9**3)*(len(N)-1)*(len(N)-2)*(len(N)-3)//6
        res += (9**2)*(len(N)-1)*(len(N)-2)//2*(int(N[0])-1)
        res += solve(N[1:],K-1)
    return res


print(solve(N,K))

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 c(n,k):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k == 2:
		return n*(n-1)//2
	else:
		return n*(n-1)*(n-2)//6
def f(N, K):
	if N == 0 and K > 0:
		return 0

	if K == 0:
		return 1
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit-1, K) * (9 ** K)
	a = 10**(digit-1)
	d = N // a
	ret += (d-1) * c(digit-1, K-1) * (9 ** (K-1))
	ret += f(N - d*a, K-1)

	return ret

print(f(N,K))

Solution (Python):
def A():
    temp = input().split()
    S = temp[0]
    T = temp[1]
    temp = [int(i) for i in input().split()]
    A = temp[0]
    B = temp[1]
    U = input()
    if U == S:
        print(A-1, B)
    else:
        print(A, B-1)

def B():
    print('x'*len(input()))

def C():
    N = int(input())
    A = [int(i) for i in input().split()]
    if N > len(set(A)):
        print('NO')
    else:
        print('YES')

def D():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    K = temp[1]
    p = [int(i) for i in input().split()]
    expected_val = [(i+1)/2.0 for i in p]
    cur = sum(expected_val[:K])
    ans = cur
    for i in range(N-K):
        cur -= expected_val[i]
        cur += expected_val[i+K]
        ans = max(ans, cur)
    print(ans)

def E():
    
    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] 

    global dp, K, M 
    N = int(input())
    K = int(input())
    M = 100
  
    num = [] 
    while N: 
        num.append(N % 10) 
        N //= 10
  
    num.reverse() 
  
    
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    print(countInRangeUtil(0, 0, 0, num)) 
  

E()

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

Ns = list(map(int,list(str(N))))
L = len(Ns)
    
dp = [[[0]*L for i in range(5)] for j in range(2)]
dp[0][1][0] = 1 
dp[1][1][0] = Ns[0] - 1 
dp[1][0][0] = 1
for i in range(L-1):
    n = Ns[i+1]
    for j in range(4): 
        if n == 0:
            dp[0][j][i+1] += dp[0][j][i] 
            dp[1][j][i+1] += dp[1][j][i] 
            dp[1][j+1][i+1] += 9*dp[1][j][i] 
        else:
            dp[0][j+1][i+1] += dp[0][j][i] 
            dp[1][j][i+1] += dp[0][j][i] 
            dp[1][j+1][i+1] += (n-1) * dp[0][j][i] 
            dp[1][j][i+1] += dp[1][j][i] 
            dp[1][j+1][i+1] += 9*dp[1][j][i] 
print(dp[0][K][L-1] + dp[1][K][L-1])

Solution (Python):
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']



show_flg = True


def main():
    s = S()
    K = I()
    N = len(s)
    n = [int(s[i]) for i in range(N)]
    dp = [[[0 for j in range(max(N + 2, K + 2))]
           for smaller in range(2)]
          for i in range(N + 1)]
    dp[0][0][0] = 1

    for i in range(0, N):
        for smaller in range(2):
            for k in range(K + 1):
                for x in range(10 if smaller else n[i]+1):
                    if x != 0:
                        
                        dp[i+1][smaller or x < n[i]][k+1] += dp[i][smaller][k]
                    else:
                        dp[i+1][smaller or x < n[i]][k] += dp[i][smaller][k]
        

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


if __name__ == '__main__':
    main()

Solution (Python):

n = input()
K = int(input())
l = len(n)
dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    D = int(n[i])
    for j in range(2):
        for k in range(4):
            for d in range((9 if j==1 else D)+1):
                J = j==1 or d<D
                if d!=0:
                    dp[i+1][1 if J else 0][k+1] += dp[i][j][k]
                else:
                    dp[i+1][1 if J else 0][k] += dp[i][j][k]

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
K = INT()

dp0 = list2d(N+1, 107, 0)
dp1 = list2d(N+1, 107, 0)
dp0[0][0] = 1
for i in range(N):
    num = int(S[i])
    for j in range(107):
        for k in range(10):
            nxt = j+1 if k != 0 else j
            if nxt == 107:
                continue
            if k < num:
                dp1[i+1][nxt] += dp0[i][j]
                dp1[i+1][nxt] += dp1[i][j]
            elif k == num:
                dp0[i+1][nxt] += dp0[i][j]
                dp1[i+1][nxt] += dp1[i][j]
            else:
                dp1[i+1][nxt] += dp1[i][j]
ans = dp0[N][K] + dp1[N][K]
print(ans)

Solution (Python):


from collections import deque, defaultdict
import itertools as ite
import sys
import math
from decimal import *

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = raw_input()
K = input()
K_ = K

DP = [[0] * 110 for i in range(110)]
DP[0][0] = 1

for i in range(1, 110):
    DP[i][0] = 1
    for j in range(1, 110):
        DP[i][j] = DP[i - 1][j] + DP[i - 1][j - 1] * 9

ans = 0
for i in range(len(N)):
    if N[i] != '0':
        ans += DP[len(N) - i - 1][K]
        ans += (int(N[i]) - 1) * DP[len(N) - i - 1][K - 1]
    if N[i] != '0':
        K -= 1
        if K < 1:
            ans += 1
            break

print ans

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

L = list(map(int, readline().strip()))
LN = len(L)
K = int(readline())

dpp = [0]*(K+1)
dpp[1] = 1
dpn = [0]*(K+1)
dpn[0] = 1
dpn[1] = L[0]-1
for l in L[1:]:
    dpp2 = [0]*(K+1)
    dpn2 = dpn[:]
    for i in range(1, K+1):
        dpn2[i] += 9*dpn[i-1]
        if l:
            dpn2[i] += (l-1)*dpp[i-1] + dpp[i]
    if not l:
        dpp2 = dpp[:]
    else:
        for i in range(1, K+1):
            dpp2[i] = dpp[i-1]
    dpp = dpp2[:]
    dpn = dpn2[:]

print(dpp[K] + dpn[K])

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

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

for i in range(len(N)):
    D = int(N[i])
    for j in range(2):
        for k in range(5):
            dMax = 9 if j else D
            for d in range(dMax + 1):
                dp[i + 1][j | (d < D)][min(4, k + (d != 0))] += dp[i][j][k]

ans1 = dp[len(N)][0][K]
ans2 = dp[len(N)][1][K]

print(ans1 + ans2)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    s=SI()
    k=II()
    n=len(s)
    dp=[[[0]*2 for _ in range(k+1)] for _ in range(n+1)]
    dp[0][0][0]=1
    
    for i,c in enumerate(s):
        for j in range(k+1):
            for f in range(2):
                pre=dp[i][j][f]
                if pre==0:continue
                if f:
                    dp[i+1][j][f]+=pre
                    if j<k:dp[i+1][j+1][f]+=pre*9
                else:
                    c=int(c)
                    if c:
                        dp[i+1][j][1]+=pre
                        if j<k:
                            dp[i+1][j+1][1]+=pre*(c-1)
                            dp[i+1][j+1][0]+=pre
                    else:
                        dp[i+1][j][0]+=pre
    print(sum(dp[n][k]))

main()

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

    N = input().rstrip('\n')
    L = len(N)
    K = int(input())

    dp0 = [[0] * (K+1) for _ in range(L+1)]
    dp1 = [[0] * (K+1) for _ in range(L+1)]
    dp0[0][0] = 1
    for i in range(L):
        for k in range(K+1):
            m = int(N[i])
            if m == 0:
                dp0[i+1][k] += dp0[i][k]
                dp1[i+1][k] += dp1[i][k]
            else:
                dp1[i+1][k] += dp0[i][k] + dp1[i][k]
            if k+1 <= K:
                if m != 0:
                    dp0[i+1][k+1] += dp0[i][k]
                    dp1[i+1][k+1] += dp0[i][k] * (m-1) + dp1[i][k] * 9
                else:
                    dp1[i + 1][k + 1] += dp1[i][k] * 9
    print(dp0[-1][-1] + dp1[-1][-1])


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

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

for i in range(l):
    for j in range(2):
        for m in range(k+1):
            ni = int(n[i])
            if j == 0:
                for num in range(ni+1):
                    if num == ni:
                        if ni == 0:
                            dp[i+1][0][m] += dp[i][j][m]
                        else:
                            if m+1 <= k:
                                dp[i+1][0][m+1] += dp[i][j][m]
                    else:
                        if num == 0:
                            dp[i+1][1][m] += dp[i][j][m]
                        else:
                            if m+1 <= k:
                                dp[i+1][1][m+1] += dp[i][j][m]
            else:
                for num in range(10):
                    if num == 0:
                        dp[i+1][1][m] += dp[i][j][m]
                    else:
                        if m+1 <= k:
                            dp[i+1][1][m+1] += dp[i][j][m]



print(dp[l][0][k] + dp[l][1][k])

Solution (Python):
from collections import defaultdict as dd
N = int(input())
K = int(input())

s = str(N)

dp = dd(int)
dp[(True, 1)] = 1
dp[(False, 1)] = int(s[0])-1
dp[(False, 0)] = 1

for c in s[1:]:
    i = int(c)
    ndp = {}
    if i != 0:
        ndp[(True, 0)] = 0
        ndp[(True, 1)] = dp[(True, 0)]
        ndp[(True, 2)] = dp[(True, 1)]
        ndp[(True, 3)] = dp[(True, 2)]
        ndp[(False, 0)] = dp[(False, 0)] + dp[(True, 0)]
        ndp[(False, 1)] = dp[(False, 1)] + dp[(False, 0)]*9 + dp[(True, 0)]*(i-1) + dp[(True, 1)]
        ndp[(False, 2)] = dp[(False, 2)] + dp[(False, 1)]*9 + dp[(True, 1)]*(i-1) + dp[(True, 2)]
        ndp[(False, 3)] = dp[(False, 3)] + dp[(False, 2)]*9 + dp[(True, 2)]*(i-1) + dp[(True, 3)]
    else:
        ndp[(True, 0)] = dp[(True, 0)]
        ndp[(True, 1)] = dp[(True, 1)]
        ndp[(True, 2)] = dp[(True, 2)]
        ndp[(True, 3)] = dp[(True, 3)]
        ndp[(False, 0)] = dp[(False, 0)]
        ndp[(False, 1)] = dp[(False, 1)] + dp[(False, 0)]*9
        ndp[(False, 2)] = dp[(False, 2)] + dp[(False, 1)]*9
        ndp[(False, 3)] = dp[(False, 3)] + dp[(False, 2)]*9
    dp = ndp
print(dp[True, K] + dp[False, K])