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 sys import setrecursionlimit
setrecursionlimit(10**6) 

from sys import stdin
from functools import lru_cache
n = int(stdin.readline().rstrip())
k = int(stdin.readline().rstrip())

@lru_cache(maxsize=None)
def kosuu(n,k):
    
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q = n//10
    r = n%10
    ret = 0
    if k >= 1:
        
        ret += kosuu(q, k-1) * r
        ret += kosuu(q-1, k-1) * (9-r)
    ret += kosuu(q,k)
    return ret
print(kosuu(n,k))

Solution (Python):

from sys import setrecursionlimit
setrecursionlimit(10**6) 

from sys import stdin
from functools import lru_cache
n = int(stdin.readline().rstrip())
k = int(stdin.readline().rstrip())

@lru_cache(maxsize=None)
def kosuu(n,k):
    
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q = n//10
    r = n%10
    ret = 0
    if k >= 1:
        
        ret += kosuu(q, k-1) * r
        ret += kosuu(q-1, k-1) * (9-r)
    ret += kosuu(q,k)
    return ret
print(kosuu(n,k))

Solution (Python):
from math import factorial as f
from functools import reduce
def C(n,k):
    a,b=sorted((k,n-k))
    return reduce(int.__mul__, range(b+1,n+1),1) // f(a)

def almost_everywhere_zero(v, k):
    if not v or not k: return 0
    s = str(v)
    n,d = len(s), int(s[0])
    
    if k>n: return 0
    
    below = 9**k * C(n-1,k) if n>k else 0
    return below + ( d if k==1 else (d-1) * 9**(k-1) * C(n-1,k-1) + almost_everywhere_zero(int(s[1:]), k-1) )
N = input()
K = int(input())
print(almost_everywhere_zero(N,K))

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

l = len(S)

MOD = 1000000007


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



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

for i in range(l):
    cur = int(S[i])

    for j in range(i + 1):
        
        for k in range(10):
            if k == 0:
                dp[i + 1][True][j] += dp[i][True][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][True][j]

        
        for k in range(cur):
            if k == 0:
                dp[i + 1][True][j] += dp[i][False][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][False][j]

        
        if cur == 0:
            dp[i + 1][False][j] += dp[i][False][j]
        else:
            dp[i + 1][False][j + 1] += dp[i][False][j]

if K > l:
    print(0)
else:
    print(dp[l][True][K] + dp[l][False][K])

Solution (Python):
n=int(input())
k=int(input())
l=[int(i) for i in "0"+str(n)]

dp=[[[0]*5,[0]*5] for i in "ww"]
dp[0][0][0]=1
for i,j in enumerate(str(n),start=1):
    for p in range(k+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][p+[0,1][l[i]>0]]=1
            for q in range(l[i]):
                dp[i%2][1][p+[0,1][q>0]]+=1
        if dp[i%2-1][1][p]:
            dp[i%2][1][p]+=dp[i%2-1][1][p]
            dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9
    for p in range(10): dp[i%2-1][p//5][p%5]=0
print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])

Solution (Python):
n=int(input())
k=int(input())
l=[int(i) for i in "0"+str(n)]

dp=[[[0]*5,[0]*5] for i in "ww"]
dp[0][0][0]=1
for i,j in enumerate(str(n)):
    i+=1
    for p in range(k+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][p+[0,1][l[i]>0]]=1
            for q in range(l[i]):
                dp[i%2][1][p+[0,1][q>0]]+=1
        if dp[i%2-1][1][p]:
            dp[i%2][1][p]+=dp[i%2-1][1][p]
            dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9
    for p in range(10): dp[i%2-1][p//5][p%5]=0
print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])

Solution (Python):
n=int(input())
k=int(input())
l=[int(i) for i in "0"+str(n)]

dp=[[[0]*5,[0]*5] for i in "ww"]
dp[0][0][0]=1
v=0
for i,j in enumerate(str(n)):
    i+=1
    v=v*10+l[i]
    for p in range(k+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][p+[0,1][l[i]>0]]=1
            for q in range(l[i]):
                dp[i%2][1][p+[0,1][q>0]]+=1
        if dp[i%2-1][1][p]:
                dp[i%2][1][p]+=dp[i%2-1][1][p]
                dp[i%2][1][p+1]+=dp[i%2-1][1][p]*9
    for p in range(10): dp[i%2-1][p//5][p%5]=0
print(dp[0][0][k]+dp[1][0][k]+dp[0][1][k]+dp[1][1][k])

Solution (Python):
n = input()
k = len(n) - int(input())
if k < 0:
    print(0)
    exit()

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

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

for i in range(len(n)):
    if n[i] == "0":
        for j in range(k):
            dp[i + 1][j + 1][0] = dp[i][j][0]
            dp[i + 1][j + 1][1] = dp[i][j][1]
        for j in range(k+1):
            dp[i + 1][j][0] += dp[i][j][0] * 9
    else:
        for j in range(k):
            dp[i + 1][j + 1][0] = dp[i][j][0] + dp[i][j][1]
        for j in range(k+1):
            dp[i + 1][j][0] += dp[i][j][0] * 9+dp[i][j][1] * (int(n[i])-1)
            dp[i + 1][j][1] += dp[i][j][1]
print(sum(dp[-1][-1]))

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

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

n = len(N)
for i in range(n):
    nd = int(N[i])
    for j in range(4):
        for k in range(2):
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Solution (Python):
from scipy.misc import comb
def solve(i,k,smaller):
    if i == len(S):
        if k == 0:
            
            return 1
        else:
            
            return 0 
    
    if k ==0:
        
        return 1
    
    if smaller :
        return comb(len(S)-i,k)*pow(9,k)
    else:
        if S[i] =="0":
            return solve(i+1,k,False)
        else:
            zero = solve(i+1,k,True)
            aida = solve(i+1,k-1,True)*(int(S[i])-1)
            ici  = solve(i+1,k-1,False)
            
            return zero+aida+ici
            
N = int(input())
S = str(N)
K = int(input())

ans = round(solve(0,K,False))

print(int(ans))

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

dp0 = [[0] * (k + 1) for _ in range(l + 1)]
dp1 = [[0] * (k + 1) for _ in range(l + 1)]

for i in range(1, l + 1):
    dp0[i][0] = 1

dp1[0][0] = 1

for i in range(1, l + 1):
    for j in range(1, k + 1):
        m = int(n[i - 1])
        if m != 0:
            dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j] + dp1[i-1][j-1] * (m-1) + dp1[i-1][j]
            dp1[i][j] = dp1[i-1][j-1]
        else:
            dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j]
            dp1[i][j] = dp1[i-1][j]

print(dp0[l][k] + dp1[l][k])

Solution (Python):
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp=[[[0]*5,[0]*5] for i in range(x)]
dp[0][0][0]=1
r=0

for i in range(1,x):
    for j in range(2):
        dp[i][1][0]=1
        for p in range(1,k+1):
            if j==0 and l[i]==0:
                dp[i][0][p]=dp[i-1][0][p]
            elif j==0 and l[i]!=0 and dp[i-1][0][p-1]:
                dp[i][0][p]=1
            if j==1:
                dp[i][1][p]=dp[i-1][1][p]+(dp[i-1][1][p-1]*9)+(dp[i][0][p]*max(0,l[i]-1))+([0,1][l[i]!=0 and dp[i-1][0][p]])
print(dp[-1][0][k]+dp[-1][1][k])

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

dp1 = [[0] * (k + 2) for _ in range(len(n_str) + 1)]
dp2 = [[0] * (k + 2) for _ in range(len(n_str) + 1)]



dp1[0][0] = 1



for i in range(len(n_str)):
    for j in range(k + 1):
        if n_str[i] != '0':
            dp1[i + 1][j + 1] += dp1[i][j]

            dp2[i + 1][j + 1] += dp1[i][j] * (int(n_str[i]) - 1)
            dp2[i + 1][j + 1] += dp2[i][j] * 9

            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp1[i + 1][j] += dp1[i][j]

            dp2[i + 1][j + 1] += dp2[i][j] * 9
            dp2[i + 1][j] += dp2[i][j]



ans = dp1[len(n_str)][k] + dp2[len(n_str)][k]
print(ans)

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

X = str(N)

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

for i in range(len(X)):
    digit = int(X[i])
    for j in range(2):
        for k in range(K+1):
            for d in range(10 if j == 1 else digit+1):
                if k + int(d != 0) <= K:
                    dp[i+1][j | (d < digit)][k + (d!=0)] += dp[i][j][k]
print(dp[-1][0][-1]+dp[-1][1][-1])

Solution (Python):
import numpy as np

N=int(input())
n=[int(i) for i in str(N)]
K=int(input())
L=len(n)
dp=np.zeros((L+1,K+1,2),dtype=int)
dp[0,0,0]=1

for i in range(L):
  for j in range(K+1):
    for smaller in range(2):
      m=10 if smaller else n[i]+1
      for x in range(m):
        if int(j+(x!=0))>K:
          continue
        
        dp[i+1,j+(x!=0),smaller or x<n[i]]+=dp[i,j,smaller]
        
        
print(dp[L,K].sum())

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


dp0 = [[0]*5 for i in range(len(n)+1)]
dp1 = [[0]*5 for i in range(len(n)+1)]

dp0[0][0] = 1


for i in range(1, len(n)+1):
    nn = int(n[i-1])
    for j in range(4):
        dp0[i][j] += dp0[i-1][j]*(nn==0)
        dp1[i][j] += dp1[i-1][j] + dp0[i-1][j]*(nn!=0)
        dp0[i][j+1] += dp0[i-1][j]*(nn!=0)
        dp1[i][j+1] += dp1[i-1][j]*9 + dp0[i-1][j]*(nn-1)*(nn!=0)

print(dp0[len(n)][k]+dp1[len(n)][k])

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


string = str(N)
digits = len(string)



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

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

for i in range(digits):
    d = int(string[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for nd in range(10):
                nk = 1 if k == 1 and nd == d else 0
                if k == 1 and nd > d: break

                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue

                dp[ni][nj][nk] += dp[i][j][k]

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

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



string = str(N)
digits = len(string)


dp0 = [[0] * (K+1) for _ in range(digits+1)]
dp1 = [[0] * (K+1) for _ in range(digits+1)]

dp1[0][0] = 1

for i in range(digits):
    d = int(string[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for nd in range(10):
                nj = j + (1 if nd != 0 else 0)
                if nj > K: continue
                nk = k
                if k == 1:
                    if nd < d: nk = 0
                    elif nd > d: continue
                dp_b = dp0 if k == 0 else dp1
                dp_a = dp0 if nk == 0 else dp1
                dp_a[ni][nj] += dp_b[i][j]

print(dp0[digits][K] + dp1[digits][K])

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

s = ns()
N = len(s)
K = ni()
dp = [[[0] * 4 for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(2):
        D = int(s[i])
        n = 9 if j == 1 else D
        for d in range(n + 1):
            for k in range(4):
                ni, nj, nk = i + 1, j, k
                if d != 0:
                    nk += 1
                if nk > K:
                    continue
                if d < D:
                    nj = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Solution (Python):
N = input()
digits = len(N)
K = int(input())
dp0 = [[0]*5 for i in range(digits + 1)] 
dp1 = [[0]*5 for i in range(digits + 1)]
dp0[0][0] = 1
for i, n in enumerate(N):
    n = int(n)
    for j in range(4):
        if n == 0:
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            dp1[i+1][j+1] += 9 * dp1[i][j]
        else:
            dp0[i+1][j+1] += dp0[i][j]
            dp1[i+1][j] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+1] += (n - 1) * dp0[i][j] + 9 * dp1[i][j]
print(dp0[digits][K] + dp1[digits][K])

Solution (Python):
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)


n = input()
K = int(input())


def func(i, k, free=False):
    
    m = len(n) - i

    
    if k > m:
        return 0

    if m == 0:
        return 1
    
    if k == 0:
        return 1

    if free:
        a = 9 ** k
        
        for j in range(k):
            a *= (m - j)
        for j in range(k):
            a = a // (j + 1)
        
        return a

    else:
        if n[i] != '0':
            
            a = func(i + 1, k, free=True)

            
            b = (int(n[i]) - 1) * func(i + 1, k - 1, free=True)

            
            c = func(i + 1, k - 1, free=False) 
            
            return a + b + c
        else:
            
            c = func(i + 1, k, free=False)
            return c


print(func(0, K, free=False))

Solution (Python):
import functools

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

@functools.lru_cache(maxsize=2048)
def nCk(n, k):
    if k == 0:
        return 0
    elif k == 1:
        return n
    elif k == 2:
        return (n * (n-1)) // 2
    return (n * (n-1) * (n-2)) // 6

def slowsolve(N, K):
    if not N:
        return 0, {}
    ans = 0
    meta = {}
    for i in range(1, int(N) + 1):
        if len(str(i)) - str(i).count("0") == K:
            meta.setdefault(len(str(i)), 0)
            meta[len(str(i))] += 1
            ans += 1
    return ans, meta

def clean(N):
    clean_N = []
    for n in N:
        if n == "0" and not clean_N:
            pass
        else:
            clean_N.append(n)
    if clean_N:
        return "".join(clean_N)
    return ""

@functools.lru_cache(maxsize=2048)
def solve(N, K):
    N = clean(N)

    if len(N) <= 3:
        return slowsolve(N, K)[0]
    elif K == 0:
        return 0
    else:
        m = int(N[0])

        
        ans = solve("9" * len(N[1:]), K)

        if K == 3:
            
            
            ans += (m - 1) * nCk(len(N[1:]), 2) * 9 * 9
            
            ans += solve(N[1:], K - 1)
        elif K == 2:
            
            
            ans += (m - 1) * len(N[1:]) * 9
            
            ans += solve(N[1:], K - 1)
        elif K == 1:
            
            ans += m
        return ans


print(solve(N, K))

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

result = 0
for i in range(101):
    if n < 10 ** i:
        if i < k:
            break
        if i > k:
            result += cmb(i-1, k) * 9**k
        s = str(n)
        result += (int(s[0])-1) * cmb(i-1, k-1) * (9 **(k-1))
        if k > 1:
            ind = -1
            for j in range(1, i):
                if s[j] != '0':
                    ind = j
                    break
            if ind == -1:
                break
            if i - ind >= k:
                result += cmb(i-ind-1, k-1) * (9**(k-1))
            result += (int(s[ind])-1) * cmb(i-ind-1, k-2) * (9**(k-2))
            if k > 2:
                ind2 = -1
                for j in range(ind+1, i):
                    if s[j] != '0':
                        ind2 = j
                        break
                if ind2 == -1:
                    break
                result += (i-ind2-1) * 9 + int(s[ind2])
            else:
                result+=1
        else:
            result+=1
        break
print(result)

Solution (Python):

import numpy as np

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

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

for i in range(len(N)) : 
    n = int(N[i])
    if ( i == 0 ) :
        dp[i][0][0] = 1
        dp[i][0][1] = n-1
        dp[i][1][0] = 0
        dp[i][1][1] = 1
    else : 
        if n == 0 : 
            dp[i][0][0] = dp[i-1][0][0] 
            dp[i][1][0] = dp[i-1][1][0]
            for k in range(1,K+1) :
                dp[i][0][k] = dp[i-1][0][k-1]*9 + dp[i-1][0][k] 
                dp[i][1][k] = dp[i-1][1][k]
        else : 
            dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][0]
            dp[i][1][0] = 0
            for k in range(1, K+1) :
                dp[i][0][k] = dp[i-1][0][k-1]*9 + dp[i-1][0][k] + dp[i-1][1][k-1] * (n-1) + dp[i-1][1][k]
                dp[i][1][k] = dp[i-1][1][k-1]




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

Solution (Python):
s = list(input())
n = len(s)
k = int(input())


dp1 = [[0 for i in range(k+1)] for j in range(n+1)]
dp2 = [[0 for i in range(k+1)] for j in range(n+1)]
dp1[0][0] = 1
dp1[0][1] = int(s[0]) - 1
dp2[0][1] = 1
for i in range(1,n):
    dp1[i][0] = 1
    for j in range(1,k+1):
        x = int(s[i])
        if x != 0:
            
            dp2[i][j] += dp2[i-1][j-1]
            dp1[i][j] += dp1[i-1][j-1] * 9 + dp2[i-1][j-1] * (x-1)
            dp1[i][j] += dp1[i-1][j] + dp2[i-1][j]
        else:
            dp1[i][j] += dp1[i-1][j-1] * 9 + dp1[i-1][j]
            dp2[i][j] += dp2[i-1][j]
print(dp1[n-1][k] + dp2[n-1][k])

Solution (Python):
from decimal import*
from fractions import*
import math
import functools

s=input()
k=input()
k=(int)(k)

n=len(s)
dp=[[[0 for mind in range (2)] for j in range(k+5)] for i in range(n+5)]

dp[0][0][0]=1
for i in range(n):
    for j in range(2):
        for cnt in range(k+1):
            pre_num=1
            if(j!=0):
                pre_num=9
            else:
                pre_num=(int)(s[i])
            for digit in range(pre_num+1):
                cur=j
                if(digit<pre_num): 
                    cur=1
                dp[i+1][cnt+(digit!=0)][cur]+=dp[i][cnt][j]
sum=dp[n][k][0]+dp[n][k][1]
print(sum)

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


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


def read_list():
    return list(read_values())


def main():
    N = input().strip()
    M = len(N)
    K = int(input())

    dp1 = [[0 for _ in range(K + 1)] for __ in range(M)]
    dp2 = [[0 for _ in range(K + 1)] for __ in range(M)]

    dp1[0][0] = 1
    dp1[0][1] = int(N[0]) - 1
    dp2[0][1] = 1

    for i in range(1, M):
        a = int(N[i])
        for k in range(K + 1):
            dp1[i][k] += dp1[i - 1][k]
            if a > 0:
                dp1[i][k] += dp2[i - 1][k]
            
            if a == 0:
                dp2[i][k] = dp2[i - 1][k]
            else:
                if k > 1:
                    dp2[i][k] = dp2[i - 1][k - 1]

        for k in range(1, K + 1):
            dp1[i][k] += 9 * dp1[i - 1][k - 1]
            if a > 0:
                dp1[i][k] += (a - 1) * dp2[i - 1][k - 1]

    print(dp1[M - 1][K] + dp2[M - 1][K])


if __name__ == "__main__":
    main()

Solution (Python):






n = input()
k_in = int(input())





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

digit = int(n[0])

dp[0][False][0] = 1
dp[0][False][1] = digit - 1
dp[0][True][1] = 1

for i in range(len(n) - 1):
    for smaller in [True, False]:
        for k in range(4):
            
            if not smaller:
                
                dp[i+1][False][k] += dp[i][smaller][k]
                
                dp[i+1][False][k+1] += 9 * dp[i][smaller][k]
            else:
                next_digit = int(n[i+1])
                if next_digit == 0:
                    
                    dp[i+1][True][k] += dp[i][smaller][k]
                else:
                    
                    dp[i+1][False][k] += dp[i][smaller][k]
                    
                    dp[i+1][False][k+1] += (next_digit - 1) * dp[i][smaller][k]
                    
                    dp[i+1][True][k+1] += dp[i][smaller][k]

print(dp[len(n)-1][True][k_in] + dp[len(n)-1][False][k_in])

Solution (Python):



def solve(*args: str) -> str:
    N = list(map(int, '0' + (args[0])))
    k = int(args[1])

    d = len(N)-1
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            
            F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]*(0 < N[i])
            U[i][j-1] += U[i-1][j-1]*(0 == N[i])

            
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
            U[i][j] += U[i-1][j-1]*(0 < N[i])

    return str(sum(x[k] for x in F+U))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

























def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')

def main():
	S = input()
	S = S[:-1]
	N = len(S)

	K = inputInt()

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

	cnt = 1
	for i in range(N):
		for j in range(K+1):
			for k in range(2):
				targetN = int(S[i])
				for num in range(10):
					ni = i+1
					nj = j
					nk = k

					if num != 0:
						nj += 1
						if nj > K:
							continue

					if k == 0:
						if num > targetN:
							continue
						elif num == targetN:
							nk = 0
						else:
							nk = 1
					else:
						nk = 1

					dp[ni][nj][nk] += dp[i][j][k]
		cnt += 1

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

if __name__ == "__main__":
	main()

Solution (Python):



def solve(*args: str) -> str:
    n = int(args[0])
    k = int(args[1])

    N = list(map(int, '0' + str(n)))
    d = len(str(n))
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            if 0 < N[i]:
                F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]
                U[i][j] += U[i-1][j-1]
            else:
                F[i][j-1] += F[i-1][j-1]
                U[i][j-1] += U[i-1][j-1]
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
    return str(sum([x[k] for x in F])+sum([x[k] for x in U]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
n = input()
k = int(input())
n_len = len(n)
dp0 = [[0]*k for i in range(n_len)]
dp1 = [[0]*k for i in range(n_len)]
for i in range(k):
    if i == 0:
        dp0[0][i]=int(n[0])-1
        dp1[0][i]=1
    else:
        dp0[0][i]=0
        dp1[0][i]=0

for i in range(1,n_len):
    for j in range(k):
        if j == 0:
            dp0[i][j]=9 + dp0[i-1][0] + dp1[i-1][0]*min(1,int(n[i]))
            dp1[i][j]=dp1[i-1][0] if int(n[i]) == 0 else 0
        else:
            dp0[i][j]=dp0[i-1][j-1]*9 + dp1[i-1][j-1]*max(0,int(n[i])-1) + dp0[i-1][j] + dp1[i-1][j]*min(1,int(n[i]))
            dp1[i][j]=dp1[i-1][j-1] if int(n[i]) != 0 else dp1[i-1][j]
            
print(dp0[n_len-1][k-1]+dp1[n_len-1][k-1])

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

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

for i in range(N):
    for j in range(4):
        for k in range(2):
            nd = int(S[i])
            for d in range(10):
                nj = j
                nk = k
                if d != 0: nj += 1
                if nj > K: continue
                if k == 0:
                    if d > nd: continue
                    if d < nd: nk = 1
                dp[i+1][nj][nk] += dp[i][j][k]

print(sum(dp[N][K]))

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

dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if d < nd:
                        nc = 1
                    if d > nd:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Solution (Python):
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for a in range(n):
    for b in range(k + 1):
        for c in range(2):
            nd = int(s[a])
            for d in range(10):
                na, nb, nc = a + 1, b, c
                if 0 != d:
                    nb += 1
                if nb > k:
                    break
                if nc == 0:
                    if nd > d:
                        nc = 1
                    if nd < d:
                        break
                dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

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






dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
  n = int(N[i])
  for j in range(4):
    for k in range(2):
      for d in range(10): 
        
        ni = i+1
        nj = j
        nk = k
        if d > 0:
          nj += 1
        if nj > K:
          continue
        if k == 0:
          if d > n:
            continue
          if d < n:
            nk = 1
        dp[ni][nj][nk] += dp[i][j][k]

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

Solution (Python):


def e(): exit()
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]


dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+([dp1[i-1][j],0][l[i]==0])
print(dp1[-1][-2]+dp2[-1][-2])

Solution (Python):
N = int(input())
K = int(input())
S = str(N)
L = len(S)

dp = [[[1, 0], [0, 0], [0, 0], [0, 0]] for i in range(L)]
dp[0] = [[1, 0], [int(S[0])-1, 1], [0, 0], [0, 0]]

for l in range(1,L):
    s = int(S[l])
    if s == 0:
        for k in range(1,4):
            dp[l][k][1] += dp[l-1][k][1]
    else:
        for k in range(1,4):
            dp[l][k][1] += dp[l-1][k-1][1]
            dp[l][k][0] += dp[l-1][k][1]
    for k in range(1,4):
        dp[l][k][0] += dp[l-1][k-1][0]*9 + dp[l-1][k][0]
        dp[l][k][0] += dp[l-1][k-1][1]*max(0,s-1)

print(sum(dp[L-1][K]))

Solution (Python):
N = int(input())
K = int(input())
S = str(N)
L = len(S)

dp = [[[1, 0], [0, 0], [0, 0], [0, 0]] for i in range(L)]
dp[0] = [[1, 0], [int(S[0])-1, 1], [0, 0], [0, 0]]

for l in range(1,L):
    s = int(S[l])
    if s == 0:
        dp[l][1][1] += dp[l-1][1][1]
        dp[l][2][1] += dp[l-1][2][1]
        dp[l][3][1] += dp[l-1][3][1]
    else:
        dp[l][1][1] += dp[l-1][0][1]
        dp[l][2][1] += dp[l-1][1][1]
        dp[l][3][1] += dp[l-1][2][1]
        dp[l][1][0] += dp[l-1][1][1]
        dp[l][2][0] += dp[l-1][2][1]
        dp[l][3][0] += dp[l-1][3][1]

    dp[l][1][0] += dp[l-1][0][0]*9 + dp[l-1][1][0]
    dp[l][2][0] += dp[l-1][1][0]*9 + dp[l-1][2][0]
    dp[l][3][0] += dp[l-1][2][0]*9 + dp[l-1][3][0]
    dp[l][1][0] += dp[l-1][0][1]*max(0,s-1)
    dp[l][2][0] += dp[l-1][1][1]*max(0,s-1)
    dp[l][3][0] += dp[l-1][2][1]*max(0,s-1)

print(sum(dp[L-1][K]))

Solution (Python):
N = int(input())
K = int(input())
S = str(N)
'''
ans = 0
li = []
for i in range(1,N+1):
    if str(i).count('0') == len(str(i)) - K:
        ans += 1
        li.append(i)
print(ans)
print(li)
'''
L = len(S)

dp = [[[1, 0], [0, 0], [0, 0], [0, 0]] for i in range(L)]
dp[0] = [[1, 0], [int(S[0])-1, 1], [0, 0], [0, 0]]

for l in range(1,L):
    s = int(S[l])
    if s == 0:
        dp[l][1][1] += dp[l-1][1][1]
        dp[l][2][1] += dp[l-1][2][1]
    else:
        dp[l][1][1] += dp[l-1][0][1]
        dp[l][2][1] += dp[l-1][1][1]
        dp[l][3][1] += dp[l-1][2][1]
        dp[l][1][0] += dp[l-1][1][1]
        dp[l][2][0] += dp[l-1][2][1]
        dp[l][3][0] += dp[l-1][3][1]

    dp[l][1][0] += dp[l-1][0][0]*9 + dp[l-1][1][0]
    dp[l][2][0] += dp[l-1][1][0]*9 + dp[l-1][2][0]
    dp[l][3][0] += dp[l-1][2][0]*9 + dp[l-1][3][0]
    dp[l][1][0] += dp[l-1][0][1]*max(0,s-1)
    dp[l][2][0] += dp[l-1][1][1]*max(0,s-1)
    dp[l][3][0] += dp[l-1][2][1]*max(0,s-1)


print(sum(dp[L-1][K]))

Solution (Python):
from functools import lru_cache

def almost_everywhere_zero():
    N=int(input())
    K=int(input())
    print(f(N,K))
    
@lru_cache(None)
def f(n,k):
    if n<=10:
        if k==0:
            return 1
        if k==1:
            return n
        return 0
    div_n=n//10
    mod_n=n%10
    ans=f(div_n,k-1)*mod_n + f(div_n-1,k-1)*(9-mod_n) + f(div_n,k)
    return ans


almost_everywhere_zero()

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

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

for i, s in enumerate(K):
    a = ord(s)-48
    for j in range(4):
        for k in range(10):
            p = j+1 if k else j
            dp[i+1][1][p] += dp[i][1][j]
            if k<a:
                dp[i+1][1][p] += dp[i][0][j]

    for j in range(4):
        p = j+1 if a else j
        dp[i+1][0][p] += dp[i][0][j]

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

Solution (Python):
n = input()
k = int(input())
l = len(n)
dp = [[[0] * (k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][0][0] = 1

for i in range(1, l+1):
    m = int(n[i-1])
    for j in range(k+1):
        
        dp[i][1][j] += dp[i-1][1][j]*1  
        if j - 1 >= 0:
            dp[i][1][j] += dp[i-1][1][j-1]*9  
            
        if m == 0:
            pass
        elif m >= 1:
            dp[i][1][j] += dp[i-1][0][j]
            if j - 1>= 0:
                dp[i][1][j] += dp[i-1][0][j-1]*(m-1)
        
        if m == 0:
            dp[i][0][j] += dp[i-1][0][j]
        else:
            if j - 1>= 0:
                dp[i][0][j] += dp[i-1][0][j-1]
        
print(dp[-1][0][k] + dp[-1][1][k])