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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    k = I()
    a = [int(c) for c in str(n)]
    l = len(a)
    dp = [[[0]*(k+1) for j in range(2)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        cp = dp[i]
        np = dp[i+1]
        c = a[i]
        if c == 0:
            for j in range(2):
                for ck in range(k+1):
                    np[j][ck] += cp[j][ck]
        else:
            for j in range(2):
                for ck in range(k+1):
                    np[1][ck] += cp[j][ck]

        for v in range(1,10):
            if v == c:
                for ck in range(k):
                    np[0][ck+1] += cp[0][ck]
                    np[1][ck+1] += cp[1][ck]
            elif v < c:
                for ck in range(k):
                    np[1][ck+1] += cp[0][ck]
                    np[1][ck+1] += cp[1][ck]
            else:
                for ck in range(k):
                    np[1][ck+1] += cp[1][ck]

    r = dp[l][0][k] + dp[l][1][k]
    return r


print(main())

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

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

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

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

dp = [[[0 for i in range(2)] for j in range(4)] for k in range(105)]

n = len(s)

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

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

Solution (Python):
n=input()
K=int(input())
m=len(n)

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:DP[i][flag or k<num][j+1] +=DP[i-1][flag][j]

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

Solution (Python):
n=input()
K=int(input())
m=len(n)

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:
                    DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:
                    DP[i][flag or k<num][j+1] +=DP[i-1][flag][j]

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

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





ans = 0
l = len(n_) 
ans += int(n_[0])+9*(l-1)
if k==1:
    print(ans)
    exit()
ans = 0
ans += 9*9*(l-2)*(l-1)//2
ans += (int(n_[0])-1)*9*(l-1)
tmp = int(n_[0])*10**(l-1)
for j in range(1,10):
    for i in range(len(n_)):
        if n>=tmp+j*10**i:
            ans += 1
if k==2:
    print(ans)
    exit()
    
ans = 0

ans += 9*9*9*(l-2)*(l-1)*(l-3)//6
ans += (int(n_[0])-1)*9*9*(l-1)*(l-2)//2
tmp = int(n_[0])*10**(l-1)
for j in range(1,10):
    for k in range(1,10):
        for i in range(len(n_)):
            for h in range(i):
                if n>=tmp+j*10**i+k*10**h:
                    ans += 1
print(ans)

Solution (Python):
n = input().rstrip()
m = int(input())

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

for i in range(len(n)):
    for j in range(4):
        for k in range(2):
            nd = ord(n[i]) - ord('0')
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > m:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
            
print(dp[len(n)][m][0] + dp[len(n)][m][1])

Solution (Python):
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0

def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans

n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    ans += calc(number,k)
else:
    ans = 0
print(ans)

Solution (Python):
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0

def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans

n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    ans += calc(number,k)
else:
    ans = 0
print(ans)

Solution (Python):
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0


def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans


n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    ans += calc(number,k)
else:
    ans = 0
print(ans)

Solution (Python):
from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0

n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

t = len(number)
t1 = len(number) - 1

if t>=k:
    ans = 0
    def calc(a,k):
        t = len(a)
        t1 = len(a) - 1
        if k<1 or t == 0:
            return 0
        else:
            if a[t1]>0:
                ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
                ans+=calc(a[:(t-1)],k-1)
            else:
                ans = 0
                ans+=calc(a[:(t-1)],k)
            if a[-k]>=1 and k == 1:
               ans+=1
            return ans
    ans += calc(number,k)
else:
    ans = 0
print(ans)

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

D = [[[0] * (k+1) for i in range(len(n))] for j in range(2)]

D[0][0][0] = 1
D[0][0][1] = int(n[0]) - 1
D[1][0][1] = 1
kk = 1

for i in range(1, len(n)):
    D[0][i][0] = D[0][i-1][0]
    for j in range(1, k+1):
        D[0][i][j] += D[0][i-1][j-1] * 9 + D[0][i-1][j]
    if n[i] == "0":
        if kk < k+1:
            D[1][i][kk] += D[1][i-1][kk]
    else:
        if kk < k+1:
            D[0][i][kk] += D[1][i-1][kk]
        if kk+1 < k+1:
            D[1][i][kk+1] += D[1][i-1][kk]
            D[0][i][kk+1] += D[1][i-1][kk] * (int(n[i]) - 1)
        kk += 1

print(D[0][-1][-1] + D[1][-1][-1])

Solution (Python):
from functools import lru_cache

N = int(input())
K = int(input())
memo = {}

@lru_cache(maxsize = 128)
def F(N, K):
    """
    F(N, K) = (1以上N以下で0でない桁がちょうどK個なものの個数)
    Nを一の桁から見ていくことで再帰で求める
    （例）F(314,3) = F(31,2)*4 + F(30,2)*5 + F(31,3)
                      = {F(3,1) + F(2,1)*8 + F(3,2)} * 4
                            + {F(2,1)*9 + F(3,2)} * 5
                            + {F(3,2) + F(2,2)*8 + F(3,3)}
                      = ...
    """
    r = int(str(N)[-1])
    M = (N - r) // 10
    if K == 0 and N >= 0:
        return 1
    elif K == 0 and N <= -1:
        return 0
    elif N <= 0:
        return 0
    else:
        return F(M, K-1) * r + F(M-1, K-1) * (9-r) + F(M, K)

print(F(N, K))

Solution (Python):
n = str(input())
K = int(input())
dp=[[[0]*2 for j in range(4)] for i in range(len(n)+1)]

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

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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n = onem()
k = onem()

s = str(n)

dp0 = [[0 for j in range(4)] for i in range(len(str(n))+1)]
dp1 = [[0 for j in range(4)] for i in range(len(str(n))+1)]

po = 0

dp0[0][0] = 0
dp1[0][0] = 1

for i in range(1,len(str(n))+1):
    point = i - 1
    np = int(s[point])
    po += 1 if np == 0 else 0

    dp0[i][0] = 1
    dp1[i][0] = 0

    dp0[i][1] = dp1[i-1][0]*(max(0,np-1)) + dp0[i-1][0]*9 + dp0[i-1][1] + ( dp1[i-1][1] if np != 0 else 0 )
    dp1[i][1] = 1 if i == 1 + po else 0

    dp0[i][2] = dp1[i-1][1] * (max(0,np-1)) + dp0[i-1][1] * (9) + dp0[i-1][2] + ( dp1[i-1][2] if np != 0 else 0 )
    dp1[i][2] = 1 if i == 2 + po else 0

    dp0[i][3] = dp1[i-1][2] * (max(0,np-1)) + dp0[i-1][2] * (9) + dp0[i-1][3] + ( dp1[i-1][3] if np != 0 else 0 )
    dp1[i][3] = 1 if i == 3 + po else 0

    


print(dp0[-1][k]+dp1[-1][k])

Solution (Python):

N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 5 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
    for smaller in range(2):
        for j in range(4):
            for x in range((9 if smaller else n[i]) + 1):
                dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])

Solution (Python):
from functools import lru_cache

@lru_cache(None)
def solve(n,k) :
  if n<=9:
    if k==0: return 1
    if k==1: return n
    return 0
  if k==0: return 1
  m, r = divmod(n, 10)
  return r*solve(m, k-1)+(9-r)*solve(m-1, k-1)+solve(m, k)

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

Solution (Python):
from functools import lru_cache

@lru_cache(None)
def solve(n,k) :
  if n<=9:
    if k==0: return 1
    if k==1: return n
    return 0
  m = n//10
  r = n%10
  return r*solve(m, k-1)+(9-r)*solve(m-1, k-1)+solve(m, k)

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

Solution (Python):
from functools import lru_cache

@lru_cache(None)
def solve(n,k) :
  if n<=9:
    if k==0: return 1
    if k==1: return n
    return 0
  m, r = divmod(n, 10)
  return r*solve(m, k-1)+(9-r)*solve(m-1, k-1)+solve(m, k)

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

Solution (Python):










import math
import string

def intinput():
    return int(input())

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

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

N = str(intinput())
K = intinput()
s = len(str(N))
dp = [[[0] * 2 for i in range(4)] for j in range(s+1)]
dp[0][0][0] = 1
for h in range(1,s+1):
    dp[h][0][1] = 1
    for i in range(1,4):
        for j in range(0,2):
            if j == 1:      
                for k in range(0,10):
                    if int(N[h-1]) == 0:
                        dp[h][i][j] += dp[h-1][i][1] + dp[h-1][i-1][1]*9
                        break
                    if int(N[h-1]) > k:
                        if k == 0:
                            dp[h][i][j] += dp[h-1][i][0] + dp[h-1][i][1]
                        if k != 0:
                            dp[h][i][j] += dp[h-1][i-1][0] + dp[h-1][i-1][1]
                    if int(N[h-1]) <= k:
                        dp[h][i][j] += dp[h-1][i-1][1]
            if j == 0:
                if int(N[h-1]) == 0:
                    dp[h][i][j] += dp[h-1][i][0]
                else:
                    dp[h][i][j] += dp[h-1][i-1][0]

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

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

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

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

for i in range(nl):
  for j in range(2):
    for l in range(k+1):
      c = int(n[i])
      if j == 1:
        dp[i+1][j][l] += dp[i][j][l]
        if l < k:
          dp[i+1][j][l+1] += dp[i][j][l]*9
      else:
        if c == 0:
          dp[i+1][0][l] += dp[i][j][l]
        else:
          dp[i+1][1][l] += dp[i][j][l]
          if l < k:
            dp[i+1][1][l+1] += dp[i][j][l]*(c-1) 
            dp[i+1][0][l+1] += dp[i][j][l] 
            
print(dp[nl][0][k]+dp[nl][1][k])

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


for i in range(nl):
    for j in range(2):
        for l in range(k + 1): 
            c = int(n[i])
            if j == 1:  
                dp[i + 1][j][l] += dp[i][j][l]  
                if l < k:  
                    dp[i + 1][j][l + 1] += dp[i][j][l] * 9  
            else:  
                if c == 0:
                    
                    dp[i + 1][0][l] += dp[i][j][l]
                else:
                    dp[i + 1][1][l] += dp[i][j][l]  
                    if l < k: 
                        dp[i + 1][1][l + 1] += dp[i][j][l] * (c - 1)  
                        dp[i + 1][0][l + 1] += dp[i][j][l]  
print(dp[nl][1][k]+dp[nl][0][k])

Solution (Python):

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

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

x = int(s[0])

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

dp[0][0][1] = x-1

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

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


for i in range(1,l):
    x = int(s[i])
    if x>=1:
        
        dp[i][0][0] = dp[i-1][0][0]*1 +dp[i-1][1][0]*1
        
        dp[i][1][0] = dp[i-1][0][0]*0 +dp[i-1][1][0]*0
        for j in [1,2,3]:
            dp[i][0][j] = dp[i-1][0][j-1]*9 +dp[i-1][1][j-1]*(x-1) +dp[i-1][0][j]*1 +dp[i-1][1][j]*1
            dp[i][1][j] = dp[i-1][0][j-1]*0 +dp[i-1][1][j-1]*1     +dp[i-1][0][j]*0 +dp[i-1][1][j]*0
    else:
        
        dp[i][0][0] = dp[i-1][0][0]*1 +dp[i-1][1][0]*0
        
        dp[i][1][0] = dp[i-1][0][0]*0 +dp[i-1][1][0]*1
        for j in [1,2,3]:
            dp[i][0][j] = dp[i-1][0][j-1]*9 +dp[i-1][1][j-1]*0 +dp[i-1][0][j]*1 +dp[i-1][1][j]*0
            dp[i][1][j] = dp[i-1][0][j-1]*0 +dp[i-1][1][j-1]*0 +dp[i-1][0][j]*0 +dp[i-1][1][j]*1
            
print(dp[-1][0][k] + dp[-1][1][k])

Solution (Python):
from functools import lru_cache
n=int(input())
k=int(input())
@lru_cache(None)
def cal(n,k):
  if n<10:
    if k==0: return 1
    if k==1: return n
    return 0
  q,r=divmod(n,10)
  ret=0
  if k>=1:
    ret+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))

Solution (Python):
import math
import pprint

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


N_d = int(math.log10(N))


def N_n(n):
    return int(N//(10**(n))%(10))

dp = [[[-1]*2 for i in range(K+2)] for i in range(int(math.log10(N))+2)]




def rec(i,j,t):
    if j < 0 :
        return 0

    if dp[i][j][t]!=-1:
        return dp[i][j][t]
    
    nnn = N_n(i)
    
    if i == 0:
        if j == 0:
            dp[i][j][t] = 1
        elif j == 1:
            if t:
                dp[i][j][t] = nnn
            else:
                dp[i][j][t] = 9
        else:
            dp[i][j][t] = 0
    else:
        if t:
            if nnn==0:
                dp[i][j][t] = rec(i-1,j,True)
            else:
                dp[i][j][t] = rec(i-1,j,False) + (rec(i-1,j-1,False) * (nnn-1)) + (rec(i-1,j-1,True))
        else:
            dp[i][j][t] = rec(i-1,j,False) + (rec(i-1,j-1,False) * 9)
    return dp[i][j][t]

print(rec(N_d,K,True))

Solution (Python):
n = list(map(int, list(input())))
k = int(input())





def solve(n, k):
    if k == 0:
        return 1
    if n == []:
        return 0
    dp = [[0 for _ in range(k+1)] for _ in range(len(n))]
    dp[0][0] = 1
    dp[0][1] = n[0] - 1
    for i in range(len(n) - 1):
        for j in range(k + 1):
            if j == 0:
                dp[i+1][0] = dp[i][0]
            else:
                dp[i+1][j] = dp[i][j-1] * 9 + dp[i][j]
    
    i = 1
    while i < len(n) and n[i] == 0:
        i += 1
    return dp[len(n) - 1][k] + solve(n[i:], k-1)

print(solve(n, k))

Solution (Python):


def oneNum(N):
    answer = 0

    while(N > 0):
        if(N >= 9):
            answer = answer + 9
        else:
            answer = answer + N
        
        N = N // 10

    return answer

def twoNum(N):
    answer = 0

    strN = str(N)
    topN = int(strN[0])
    lenN = len(strN)

    if(lenN != 1):
        answer = answer + oneNum(int(strN[1:])) + (topN - 1) * oneNum(int('9' * (lenN - 1)))
        N = int('9' * (lenN - 1))

    while(N >= 10):
        N = N // 10
        answer = answer + 9 * oneNum(N)

    return answer

def main():
    N = int(input())
    K = int(input())

    answer = 0

    if(K == 1):
        answer = oneNum(N)

    elif(K == 2):
        answer = twoNum(N)

    else:
        strN = str(N)
        topN = int(strN[0])
        lenN = len(strN)

        answer = answer + twoNum(int(strN[1:])) + (topN - 1) * twoNum(int('9' * (lenN - 1)))

        N = int('9' * (lenN - 1))

        while(N >= 100):
            N = N // 10
            answer = answer + 9 * twoNum(N)

    print(answer)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
N_digit = len(str(N))
K = int(input())
ans = 0
factorial = [1, 1]
for i in range(2, 101):
    factorial.append(factorial[-1] * i)


def nCr(n, r):
    if n - r < 0:
        return 0
    return factorial[n] // (factorial[r] * factorial[n - r])


if K == 1:
    ans += 9 * (nCr(N_digit - 1, 1))  
    ans += int(str(N)[0])  

elif K == 2:
    ans += (9 ** 2) * (nCr(N_digit - 1, 2))  
    ans += (int(str(N)[0]) - 1) * 9 * (nCr(N_digit - 1, 1))  
    for d2_position in range(1, N_digit):  
        for d2_value in range(1, 10):  
            
            S = ['0'] * N_digit
            S[0] = str(N)[0]
            S[d2_position] = d2_value
            S = int(''.join(map(str, S)))

            ans += (S <= N)

elif K == 3:
    ans += (9 ** 3) * (nCr(N_digit - 1, 3))  
    ans += (int(str(N)[0]) - 1) * (9 ** 2) * (nCr(N_digit - 1, 2))  
    for d2_position in range(1, N_digit):  
        for d3_position in range(d2_position + 1, N_digit):  
            for d2_value in range(1, 10):  
                for d3_value in range(1, 10):  
                    
                    S = ['0'] * N_digit
                    S[0] = str(N)[0]
                    S[d2_position] = str(d2_value)
                    S[d3_position] = str(d3_value)
                    S = int(''.join(S))

                    ans += (S <= N)

print(ans)

Solution (Python):
def comb(a, b):
    if (a < b) or (a < 0) or (b < 0):
        return 0
    res = 1
    for i in range(b):
        res *= a - i
        res //= i + 1
    return res

def solve(n, k):
    s = str(n)
    d = len(s)
    def f(i, t, ok):
        if ok:
            return comb(d-i, t) * (9**t)
        elif t == 0:
            return 1
        elif i == d:
            return 0
        if s[i] == "0":
            return f(i+1, t, False)
        res = f(i+1, t, True)
        if t > 0:
            for j in range(1, 10):
                if int(s[i]) > j:
                    res += f(i+1, t-1, True)
                elif int(s[i]) == j:
                    res += f(i+1, t-1, False)
                else:
                    break
        return res
    return f(0, k, False)

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

Solution (Python):
n = int(input())
k = int(input())
l = len(str(n))
a = [int(str(n)[i]) for i in range(l)]

dp = [[[0, 0] for _ in range(k + 1)] for _ in range(l)] 

dp[0][0][0] = 1         
dp[0][0][1] = 0         
dp[0][1][0] = a[0] - 1  
dp[0][1][1] = 1         



for i in range(1, l):
    for j in range(k + 1):
        if j > 0 and a[i] != 0:
            
            
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9 \
                        + dp[i-1][j][1] * 1 \
                        + dp[i-1][j-1][1] * (a[i] - 1)
            
            dp[i][j][1] = dp[i-1][j-1][1] * 1

        elif j > 0 and a[i] == 0:
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9
            
            dp[i][j][1] = dp[i-1][j][1] * 1
        
        elif j == 0 and a[i] != 0:
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j][1] * 1
            
            dp[i][j][1] = 0
        elif j == 0 and a[i] == 0:
            
            dp[i][j][0] = dp[i-1][j][0] * 1
            
            dp[i][j][1] = dp[i-1][j][1] * 1
            


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

Solution (Python):

'''
import math
n = int(input())
k = int(input())
b = len(str(n)) 

ans = 0

for i in range(k, b + 1):
    in0 = i - 1 
    if in0 > 0:
        
        a = math.factorial(in0) // math.factorial(k - 1) // math.factorial(in0 - k + 1)
        ans += 9 * pow(9, k - 1)
        
        print('a', 9 * pow(9, k - 1))
    else:
        ans += pow(9, i)
        print('b', pow(9, i))

print(ans)

for i in range(n + 1, pow(10, b)):
    
    num = str(i)
    cnt = 0
    for j in range(b):
        if num[j] == '0':
            cnt += 1
    if cnt == b - k:
        ans -= 1
        
'''
'''
b = len(str(n)) 
if b > k:
    a = math.factorial(b - 1) // math.factorial(k) // math.factorial(b - 1 - k)
    ans = a * pow(9, k)
else: 
    ans = 0

if k == 1:
    ans += int(str(n)[0])
elif k == 2:
    c = int(str(n)[0])
    for i in range(1, b): 
        for j in range(1, c + 1): 
            if j < c or i > 1:
                ans += 9
            else:
                
                ans += int(str(n)[i])
else:
    c = [int(str(n)[i]) for i in range(b)] 
    d = 1 
    for i in range(1, b):
        if c[i] == 0:
            d += 1
        else:
            break
    if d < b: 
        ans += (c[0] - 1) * 81 * math.factorial(b - 1) // math.factorial(2) // math.factorial(b - 3) 
        if b - d > 2:
            ans += 81 * math.factorial(b - d - 1) // math.factorial(2) // math.factorial(b - d - 3) 
        ans += (c[d] - 1) * 9 * (b - d - 1) 
        
        
        for i in range(d + 1, b): 
            for j in range(1, 10): 
                e = ['0' for _ in range(b)]
                e[0] = c[0]
                e[d] = c[d]
                e[i] = j
                f = ''
                for k in range(b):
                    f += str(e[k])
                f = int(f)
                if f <= n:
                    ans += 1






print(ans)
'''

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

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

for i in range(l):
    for j in range(k + 1):
        for m in range(2):
            d = int(str(n)[i])

            for nextd in range(10):
                nextj = j
                nextm = m

                if nextd != 0:
                    nextj += 1
                if nextj > k:
                    continue
                
                if m == 0:
                    if d < nextd:
                        continue
                    elif nextd < d:
                        nextm = 1
                
                dp[i + 1][nextj][nextm] += dp[i][j][m]

ans = dp[l][k][0] + dp[l][k][1]
print(ans)
'''

n = int(input())
k = int(input())
l = len(str(n))
a = [int(str(n)[i]) for i in range(l)]

dp = [[[0, 0] for _ in range(k + 1)] for _ in range(l)] 

dp[0][0][0] = 1         
dp[0][0][1] = 0         
dp[0][1][0] = a[0] - 1  
dp[0][1][1] = 1         



for i in range(1, l):
    for j in range(k + 1):
        if j > 0 and a[i] != 0:
            
            
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9 \
                        + dp[i-1][j][1] * 1 \
                        + dp[i-1][j-1][1] * (a[i] - 1)
            
            dp[i][j][1] = dp[i-1][j-1][1] * 1

        elif j > 0 and a[i] == 0:
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9
            
            dp[i][j][1] = dp[i-1][j][1] * 1
        
        elif j == 0 and a[i] != 0:
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j][1] * 1
            
            dp[i][j][1] = 0
        elif j == 0 and a[i] == 0:
            
            dp[i][j][0] = dp[i-1][j][0] * 1
            
            dp[i][j][1] = dp[i-1][j][1] * 1
            


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

Solution (Python):
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            if n[i] != '0':
                dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

Solution (Python):
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            if n[i] != '0':
                dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

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

S=str(N)
l=len(S)

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

for i in range(1, l):
  if S[i]=='0':
    for k in range(1, 4):
      dp[i][0][k]=dp[i-1][0][k]
      dp[i][1][k]=dp[i-1][1][k]+dp[i-1][1][k-1]*9
    dp[i][1][0]=dp[i-1][1][0]
  else:
    dp[i][0][2]=dp[i-1][0][1]
    dp[i][0][3]=dp[i-1][0][2]
    dp[i][1][0]=1
    dp[i][1][1]=dp[i-1][1][1]+dp[i-1][1][0]*9+dp[i-1][0][1]
    dp[i][1][2]=dp[i-1][1][2]+dp[i-1][1][1]*9+dp[i-1][0][2]+dp[i-1][0][1]*(int(S[i])-1)
    dp[i][1][3]=dp[i-1][1][3]+dp[i-1][1][2]*9+dp[i-1][0][3]+dp[i-1][0][2]*(int(S[i])-1)
    
print(dp[-1][0][K]+dp[-1][1][K])

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

keta = len(n)


dp0 = [[0 for j in range(keta+1)] for i in range(keta+1)]
dp1 = [[0 for j in range(keta+1)] for i in range(keta+1)]

dp1[0][0] = 1

for i in range(keta):
    for j in range(keta+1):
        
        if n[i] == '0': 
            dp1[i+1][j] = dp1[i][j] 
        else: 
            if j < keta:
                dp1[i+1][j+1] = dp1[i][j] 
        
        
        if n[i] == '0': 
            
            dp0[i+1][j] += dp0[i][j] 
            if j < keta:
                dp0[i+1][j+1] += dp0[i][j] * 9 
            
                
        else: 
            
            dp0[i+1][j] += dp0[i][j] 
            if j < keta:
                dp0[i+1][j+1] += dp0[i][j] * 9 
            
            dp0[i+1][j] += dp1[i][j] 
            if j < keta:
                dp0[i+1][j+1] += dp1[i][j] * (ord(n[i])-ord('0')-1) 

if k > keta:
    print(0)
else:
    print(dp0[keta][k] + dp1[keta][k])