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



Sample input:
100
1


Sample output:
19

Submission status: Accepted

Solution code:
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でない数字の個数][smaller=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()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#          print(x)
          if x<=N:
            cnt += g
          else:
            cnt += g-1
          s[i] = '0'
          s[j] = '0'
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

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

# dp[tight-loose][k][i-th item]
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:
        # tight -> tight
        dp[0][1][0] = 1
        # tight -> loose with 0
        dp[1][0][0] = 1
        # tight -> loose without 0
        dp[1][1][0] = max(0, item - 1)
        continue
    for j in range(k+1):
        if item != 0:
            # tight -> loose with 0
            dp[1][j][i] += dp[0][j][i-1]
            # loose -> loose with 0
            dp[1][j][i] += dp[1][j][i-1]
            if j < k:
                # tight -> tight
                dp[0][j+1][i] += dp[0][j][i-1] 
                # tight -> loose without 0
                dp[1][j+1][i] += dp[0][j][i-1] * max(0, (item - 1))
                # loose -> loose without 0
                dp[1][j+1][i] += dp[1][j][i-1] * 9 
        else:
            # tight -> tight with 0
            dp[0][j][i] += dp[0][j][i-1] 
            # loose -> loose with 0
            dp[1][j][i] += dp[1][j][i-1] 
            if j < k:
                # loose -> loose without 0
                dp[1][j+1][i] += dp[1][j][i-1] * 9

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

Submission status: Accepted

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

Submission status: Accepted

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

    # divisors.sort()
    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

#a = list(map(int, input().split()))

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]
        
#print(arr,nonzero)

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
    #print(ii,ans,arr[i])
    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)

Submission status: Accepted

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

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

# print(dp)
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]

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

Submission status: Accepted

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

# iけためまでの0のj数
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])

Submission status: Accepted

Solution code:
import numpy as np

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

M = len(N)
dp = np.zeros((M+1, K+1, 2), int)
# dp[i,j,k] = i桁の正整数であって、0でない数をj回使っており、Nの下からi桁目までの数を越えていない(k=0)/いる(k=1) ようなものの数

dp[0,0,0] = 1

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

    # Nの下からi桁目
    X = int(N[-i])
    
    # i桁目が0の場合
    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): # i桁目がn(1以上)の場合
        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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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: # K == 3
  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)

Submission status: Accepted

Solution code:

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

	# Last position 
	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

		# Next recursive call 
		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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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():
    #https://www.geeksforgeeks.org/count-of-numbers-in-range-where-the-number-does-not-contain-more-than-k-non-zero-digits/
    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() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    print(countInRangeUtil(0, 0, 0, num)) 
  

E()

Submission status: Accepted

Solution code:
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 # strict
dp[1][1][0] = Ns[0] - 1 # loose
dp[1][0][0] = 1
for i in range(L-1):
    n = Ns[i+1]
    for j in range(4): # 0,1,2,3
        if n == 0:
            dp[0][j][i+1] += dp[0][j][i] # 0
            dp[1][j][i+1] += dp[1][j][i] # 0
            dp[1][j+1][i+1] += 9*dp[1][j][i] # 1 to 9
        else:
            dp[0][j+1][i+1] += dp[0][j][i] # n
            dp[1][j][i+1] += dp[0][j][i] # 0
            dp[1][j+1][i+1] += (n-1) * dp[0][j][i] # 1 to n-1
            dp[1][j][i+1] += dp[1][j][i] # 0
            dp[1][j+1][i+1] += 9*dp[1][j][i] # 1 to 9
print(dp[0][K][L-1] + dp[1][K][L-1])

Submission status: Accepted

Solution code:
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 = False
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:
                        # print(i, smaller, k, k + 1)
                        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(i, dp[i+1])

    # print(dp[N])
    print(dp[N][0][K] + dp[N][1][K])
    # print(C(2 * m + n - 1, 2*m) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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])

Submission status: Accepted

Solution code:
#!/usr/bin/env 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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # dp[i][j][f]...i桁目までみたとき、0でない数字がj個で、s以下が確定かどうかがf
    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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
# Python Program to find the count of 
# numbers in a range where the number 
# does not contain more than K non 
# zero digits 

# This function returns the count of 
# required numbers from 0 to num 
def countInRangeUtil(pos, cnt, tight, num): 

	# Last position 
	if pos == len(num): 

		# If count of non zero digits 
		# is less than or equal to K 
		if cnt == K: 
			return 1
		return 0

	# If this result is already computed 
	# simply return it 
	if dp[pos][cnt][tight] != -1: 
		return dp[pos][cnt][tight] 

	ans = 0

	# Maximum limit upto which we can place 
	# digit. If tight is 1, means number has 
	# already become smaller so we can place 
	# any digit, otherwise num[pos] 
	limit = 9 if tight else num[pos] 

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

		# If the current digit is nonzero 
		# increment currCnt 
		if dig != 0: 
			currCnt += 1

		currTight = tight 

		# At this position, number becomes 
		# smaller 
		if dig < num[pos]: 
			currTight = 1

		# Next recursive call 
		ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 

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

# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
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) 

# Driver Code 

# states - position, count, tight 
dp = [] 
M = 101

# K is the number of non zero digits 
K = 0

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
def main():

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

    if K == 1:
        v = (len(S) - 1) * 9
        v += int(S[0])
        return v
    if K == 2:
        v = (len(S)-1) * (len(S)-2) * 9 * 9 // 2
        v += (int(S[0]) - 1) * 9 * (len(S)-1)
        u = int(S[0]) * pow(10, len(S)-1)
        for j in range(len(S)-1):
            for k in range(1, 10):
                if u + k * pow(10, j) <= N:
                    v += 1
        return v
    if K == 3:
        v = (len(S)-1) * (len(S)-2) * (len(S)-3) * 9 * 9 * 9 // 6
        v += (int(S[0]) - 1) * 9 *9 * (len(S)-1) * (len(S)-2) // 2
        u = int(S[0]) * pow(10 ,len(S)-1)
        ps = [1]
        for i in range(len(S)+1):
            ps.append(ps[-1] * 10)
        for j1 in range(len(S)-1):
            for j2 in range(j1):
                for k1 in range(1, 10):
                    for k2 in range(1, 10):
                        if u + k1 * ps[j1] + k2 * ps[j2] <= N:
                            v += 1
        return v


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def countInRangeUtil(pos, cnt, tight, num): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt <= K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x): 
    global dp, K, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  

a = int(input())
b = int(input())
dp = [] 

M = 100
R = a
K = b
m = countInRange(R)

dp = [] 
M = 100
R = a
K = b - 1
n = countInRange(R)

print(m - n)