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

def com(n, r):
  if r < 0 and r > n:
    return 0
  
  if r == 1:
    return n
  elif r == 2:
    return n * (n-1) / 2
  else:
    return n * (n-1) * (n-2) / 6

def pow(n, k):
  res = 1
  for i in range(k):
    res *= n

  return res

def solve(i, k, smaller):
  global P
  global N

  if i == P:
    if k == 0:
      return 1
    else:
      return 0

  if k == 0:
    return 1

  if smaller:
    return com(P-i, k) * pow(9, k)
  else:
    if (N[i] == '0'):
      return solve(i+1, k, False)
    else:      
      a = solve(i+1, k, True)
      b = solve(i+1, k-1, True) * (int(N[i]) - 1)
      c = solve(i+1, k-1, False)
      return a + b + c
    
N = input()
K = input()

P = len(N)

print(math.floor(solve(0, int(K), False)))

Solution (Python):
import sys


def main():
    n = int(sys.stdin.readline().strip())
    k = int(sys.stdin.readline().strip())

    digits = 0
    nc = n
    while nc:
        nc //= 10
        digits += 1

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

    for i in range(digits):
        digit = (n // (10 ** (digits - 1 - i))) % 10
        ndp = [[0] * (k+2) for _ in range(2)]
        for j in range(k+1):
            ndp[1][j] += dp[1][j]  
            ndp[1][j+1] += dp[1][j] * 9

            if digit == 0:
                ndp[0][j] += dp[0][j]
            else:
                ndp[1][j] += dp[0][j]  
                ndp[1][j+1] += dp[0][j] * (digit-1)  
                ndp[0][j+1] += dp[0][j]  
        dp = ndp
    print(dp[1][k] + dp[0][k])


if __name__ == '__main__':
    main()

Solution (Python):
def K1(n):
    ans = 0
    d = len(str(n))
    ans += int(str(n)[0])
    ans += 9 * (d-1)
    return ans


def K2(n):
    d = len(str(n))
    ans = 9**2*(d-2)*(d-1)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K1(int(str(n)[1:]))
    return ans


def K3(n):
    d = len(str(n))
    ans = 0
    for i in range(2,d-1):
        ans += i*(i-1)//2
    ans *= 9**3
    ans += (int(str(n)[0]) - 1) * 9**2 * (d-1)*(d-2) // 2
    ans += K2(int(str(n)[1:]))
    return ans


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

    if K == 1:
        print(K1(N))

    if K == 2:
        if N < 10:
            print(0)
            exit()
        print(K2(N))

    if K == 3:
        if N < 100:
            print(0)
            exit()
        print(K3(N))



if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, open(0).read().split())

X = str(N + 1)
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)):
    D = int(X[i])
    for j in range(2):
        for k in range(K + 1):
            for d in range((9 if j == 1 else D) + 1):
                if k + int(d != 0) <= K:
                    dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k]

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

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

def nCr(n,r):
    if r > n:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def normal(d, k):
    
    return nCr(d, k) * (9**k)

def main():
    tmp = input()
    N = [int(c) for c in tmp]
    D = len(N)
    K = int(input())
    

    x = 0
    ans1, ans2, ans3, ans4, ans5, ans6 = 0, 0, 0, 0, 0, 0
    if K == 1:
        ans1 = normal(D-1, K)
        ans2 = N[0]
    elif K == 2:
        ans1 = normal(D-1, K)
        ans2 = (N[0] - 1) * normal(D-1, K-1)
        x = 1
        found = False
        for i in range(x, D):
            if N[i] != 0:
                x = i
                found = True
                break
        if found:
            if x == D - 1:
                ans4 = N[x]
            else:
                ans3 = normal(D-(x+1), K-1)
                ans4 = N[x]
    elif K == 3:
        ans1 = normal(D-1, K)
        ans2 = (N[0] - 1) * normal(D-1, K-1)
        x = 1
        found = False
        for i in range(x, D):
            if N[i] != 0:
                x = i
                found = True
                break
        if found:
            if x == D - 1:
                pass
            else:
                ans3 = normal(D-(x+1), K-1)
                ans4 = (N[x] - 1) * normal(D-(x+1), K-2)
                x = x + 1
                found = False
                for i in range(x, D):
                    if N[i] != 0:
                        x = i
                        found = True
                        break
                if found:
                    if x == D - 1:
                        ans6 = N[x]
                    else:
                        ans5 = normal(D-(x+1), K-2)
                        ans6 = N[x]

    
    
    
    
    
    

    ans = ans1+ans2+ans3+ans4+ans5+ans6
    
    print(ans)

main()

Solution (Python):
N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
if i == n-1:
    if k == 0:
        ans += 1
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

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

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

for d in n:
    ndp = [[0] * (k + 2) for _ in range(2)]
    for i in range(k + 1):
        ndp[1][i] += dp[1][i]
        ndp[1][i + 1] += dp[1][i] * 9
        if d == '0':
            ndp[0][i] += dp[0][i]
        else:
            ndp[1][i] += dp[0][i]
            ndp[1][i + 1] += dp[0][i] * (int(d) - 1)
            ndp[0][i + 1] += dp[0][i]
    dp = ndp
print(dp[0][k] + dp[1][k])

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

L = list(map(int, list(str(N))))
M = len(L)
DP = [[[0] * 2 for _ in range(K + 1)] for _ in range(M)]

DP[0][1] = [L[0] - 1, 1]
DP[0][0][0] = 1

for i in range(1, M):
  DP[i][0][0] = DP[i - 1][0][0]
  for j in range(1, K + 1):
    if L[i] != 0:
      DP[i][j][0] = DP[i - 1][j][0]
      DP[i][j][0] += DP[i - 1][j][1]
      DP[i][j][0] += DP[i - 1][j - 1][0] * 9
      DP[i][j][0] += DP[i - 1][j - 1][1] * (L[i] - 1)
      DP[i][j][1] = DP[i - 1][j - 1][1]
    else:
      DP[i][j][0] = DP[i - 1][j][0]
      DP[i][j][0] += DP[i - 1][j - 1][0] * 9
      DP[i][j][1] = DP[i - 1][j][1]

ans = DP[-1][-1][0] + DP[-1][-1][1]
ans = max(0, ans)
print(ans)

Solution (Python):
import math as m

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

def f(n,k):
    l = len(str(n))
    if l < k:
        ans = 0
    elif k == 0:
        ans = 1
    elif l == k:
        t = 10 ** (k-1)
        ans = (n//t-1) * f(t-1, k-1) + f(n%t,k-1)
    else:
        ans =  m.factorial(l-1) // m.factorial(k) // m.factorial(l-1-k) * (9 ** k)
        t = n % (10**(l-1))
        ans += f(t,k-1) + f(10**(l-1)-1,k-1)* (n// (10**(l-1))-1)
    return ans

ans = f(n,k)

print(ans)

Solution (Python):
import math

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

def f(n,k):
    l = len(str(n))
    if l < k:
        ans = 0
    elif k == 1:
        ans = 9 * (l-1)
        ans += n//(10**(l-1))
    elif l == k:
        t = 10 ** (k-1)
        ans = (n//t-1) * f(t-1, k-1) + f(n%t,k-1)
    else:
        ans =  math.factorial(l-1) // math.factorial(k) // math.factorial(l-1-k) * (9 ** k)
        t = n % (10**(l-1))
        ans += f(t,k-1) + f(10**(l-1)-1,k-1)* (n// (10**(l-1))-1)
    return ans

ans = f(n,k)

print(ans)

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

digits = len(n)

dp_le = [[0 for j in range(k+1)] for i in range(digits)]
dp_lt = [[0 for j in range(k+1)] for i in range(digits)]

dp_le[0][0] = 0
dp_le[0][1] = 1
dp_lt[0][0] = 1
dp_lt[0][1] = n[0]-1

for i in range(1, digits):
    for j in range(k+1):
        if n[i] == 0:
            dp_le[i][j] = dp_le[i-1][j]
            dp_lt[i][j] = dp_lt[i-1][j]
            if j > 0:
                dp_lt[i][j] += dp_lt[i-1][j-1]*9
        else:
            dp_lt[i][j] = dp_lt[i-1][j] + dp_le[i-1][j]
            if j > 0:
                dp_le[i][j] += dp_le[i-1][j-1]
                dp_lt[i][j] += dp_lt[i-1][j-1]*9 + dp_le[i-1][j-1] * (n[i] - 1)

print(dp_le[digits-1][k] + dp_lt[digits-1][k])

Solution (Python):
S = input().strip()
N = len(S)
K = int(input())
dp = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp[0][K] = 1
dp2[0][K] = 1
for i in range(N):
    for j in range(K+1):
        dp[i+1][j] = dp[i][j]
        if j != K: dp[i+1][j] += dp[i][j+1] * 9
    dd = int(S[N-i-1])
    for j in range(K+1):
        if dd == 0:
            dp2[i+1][j] = dp2[i][j]
        else:
            if j != K:
                dp2[i+1][j] = dp[i][j] + dp[i][j+1]*(dd-1) + dp2[i][j+1]
            else:
                dp2[i+1][j] = dp[i][j]
print(dp2[N][0])

Solution (Python):
s = input()
K = int(input())
n = len(s)
 
dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(n+5)]
 
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):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

MOD = 10**9 + 7

def cone(n):
    if n == 0:
        return 0
    else:
        return n

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

def ketaall(keta, m):
    if m == 0:
        return 1
    if m == 1:
        return keta * 9
    else:
        return ctwo(keta) * 81


def main():
    n = getN()
    n = str(n)
    keta = len(n) - 1
    m = getN()
    if m == 1:
        res = 0
        print(int(int(n[0]) + 9 * keta))
        return

    res = (int(n[0]) - 1)*  ketaall(keta, m -1)
    
    for k in range(int(keta)):
        res += 9 * ketaall(k, m-1)
        

    m -= 1
    
    for s in n[1:]:
        if s == "0":
            pass
        else:
            res += ketaall(keta - 1, m)
            
            res += (int(s) - 1) * ketaall(keta-1, m-1)
            
            m -= 1

        keta -= 1
        
        if m == 0:
            res += 1
            break

    print(res)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Solution (Python):


import sys

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

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

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

Solution (Python):
n=input()
k=int(input())
lenn=len(n)
dp=[[[0]*2 for i in range(k+1)] for j in range(lenn)]
for i in range(int(n[0])+1):
  keta=int(n[0])
  if i<keta:
    if i==0:
      dp[0][0][1]+=1
    else:
      dp[0][1][1]+=1
  elif i==keta:
    dp[0][1][0]+=1
for i in range(1,lenn):
  keta=int(n[i])
  for l in range(10):
    for j in range(k):
      if l>0:
        dp[i][j+1][1]+=dp[i-1][j][1]
      else:
        dp[i][j][1]+=dp[i-1][j][1]
      if l<keta:
        if l>0:
          dp[i][j+1][1]+=dp[i-1][j][0]
        else:
          dp[i][j][1]+=dp[i-1][j][0]
      elif l==keta:
        if keta==0:
          dp[i][j][0]+=dp[i-1][j][0]
        else:
          dp[i][j+1][0]+=dp[i-1][j][0]
  if keta==0:
    dp[i][k][0]+=dp[i-1][k][0]
  else:
    dp[i][k][1]+=dp[i-1][k][0]
  dp[i][k][1]+=dp[i-1][k][1]
print(dp[lenn-1][k][0]+dp[lenn-1][k][1])

Solution (Python):
import itertools

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

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,2):
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += (int(N[0])-1)*9*9
                    ans += (int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += (int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += (int(N[0])-1)*9*9
    print(ans)

Solution (Python):
import itertools

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

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += (int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += (int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += (int(N[0])-1)*9*9

    print(ans)

Solution (Python):
import itertools

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

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Solution (Python):
import itertools

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

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Solution (Python):
import itertools

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


if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                elif not0s < v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
                    
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Solution (Python):
import itertools

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


if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 == v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            elif not0 < v[1]:
                ans += int(N[0])*9
            else:
                ans += max(0,int(N[0])-1)*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                elif not0s < v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
                    
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Solution (Python):
from functools import lru_cache
n=int(input())
k=int(input())
@lru_cache(None)
def F(x,y):  
    if x<10:
        if y==1:
            return x
        elif y==0:
            return 1
        else:
            return 0
    else:
        res=0
        q,r=divmod(x,10)
        res+=F(q,y)  
        if y>=1:
            res+=r*F(q,y-1) 
            res+=(9-r)*F(q-1,y-1) 
        return res
print(F(n,k))

Solution (Python):
def nCk(n, k):
    if n < k:
        return 0
    elif 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 solve(N, K):
    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


N, K = map(int, open(0).read().split())
print(solve(N, K))

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

def one(n):
    l = len(str(n))
    ans = 9 * (l-1)
    ans += n//(10**(l-1))
    return ans

def two(n):
    l = len(str(n))
    if l == 1:
        ans = 0
    elif l == 2:
        ans = (n//10-1) *9 + n%10
    else:
        ans =   81 * (l-1) * (l-2) // 2
        t = n % (10**(l-1))
        ans += one(t) + one(10**(l-1)-1)* (n// (10**(l-1))-1)
    return ans

def three(n):
    l = len(str(n))
    if l <= 2:
        ans = 0
    elif l == 3:
        ans = (n//100-1) * two(99) + two( n % 100 )
    else:
        ans = 729 * (l-1) * (l-2) * (l-3) // 6
        t = n % (10**(l-1))
        ans += two(t) + two(10**(l-1)-1)* (n// (10**(l-1))-1)
    return ans

if k == 1:
    ans = one(n)
if k == 2:
    ans = two(n)
if k == 3:
    ans = three(n)

print(ans)

Solution (Python):
def nCk(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 solve(N, K):
    if N < K:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


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

print(solve(N, K))

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

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


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

def case1(x):
    return (len(x) - 1) * 9 + int(x[0])

def case2(x):
    if (len(x) < 2):
        return 0
    ret = (len(x) - 1) * (len(x) - 2) // 2 * 81
    ret += case1('9' * (len(x) - 1)) * (int(x[0]) - 1)
    for i in range(1, len(x)):
        if x[i] != '0':
            ret += case1(x[i:])
            break
    return ret

def case3(x):
    if (len(x) < 3):
        return 0
    ret = (len(x) - 1) * (len(x) - 2) * (len(x) - 3) // 6 * 729
    ret += case2('9' * (len(x) - 1)) * (int(x[0]) - 1)
    for i in range(1, len(x)):
        if x[i] != '0':
            ret += case2(x[i:])
            break
    return ret

if k == 1:
    print(case1(n))
elif k == 2:
    print(case2(n))
else:
    print(case3(n))

Solution (Python):
def nCk(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 solve(N, K):
    if N == 0 and K > 0:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


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

print(solve(N, K))

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


dp = [[[0 for i in range(K+1)] for f in range(2)] for n in range(len(str(N)))]


Ni = int(str(N)[0])

dp[0][1][0] = 1
if Ni == 1:
    dp[0][0][1] = 1  
else:
    dp[0][0][1] = 1  
    dp[0][1][1] = Ni-1  


for i in range(1,len(str(N))):
    Ni = int(str(N)[i])
    for k in range(K+1):
        
        dp[i][1][k] += dp[i-1][1][k]  
        if k < K:
            dp[i][1][k+1] += dp[i-1][1][k]*9  

        
        if Ni == 0:
            
            dp[i][0][k] += dp[i-1][0][k]
        elif Ni == 1:
            
            dp[i][1][k] += dp[i-1][0][k]
            
            if k < K:
                dp[i][0][k+1] += dp[i-1][0][k]
        else:
            
            dp[i][1][k] += dp[i-1][0][k]
            
            if k < K:
                dp[i][1][k+1] += dp[i-1][0][k]*(Ni-1)
            
            if k < K:
                dp[i][0][k+1] += dp[i-1][0][k]
    
print(dp[-1][0][K]+dp[-1][1][K])

Solution (Python):
def nCk(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 solve(N, K):
    if N == 0 and K > 0:
        return 0

    if K == 0:
        return 1

    M = len(str(N))
    hd, tl = divmod(N, 10 ** (M - 1))

    res = solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    if M > K:
        res += nCk(M - 1, K) * (9 ** K)

    return res


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

print(solve(N, K))

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

l = len(n)
n = int(n)

ans=0

def one(n):
    l = len(str(n))
    ans = 9 * (l-1)
    ans += n//(10**(l-1))
    return ans

def two(n):
    l = len(str(n))
    ans = 0
    if l == 1:
        return 0
    elif l == 2:
        ans = (n//10-1) *9 + n%10
        return ans
    else:
        ans +=   81 * (l-1) * (l-2) // 2
        
        
        t = n % (10**(l-1))
        ans += one(t) + one(10**(l-1)-1)* (n// (10**(l-1))-1)
        return ans

def three(n):
    l = len(str(n))
    ans = 0
    if l <= 2:
        
        return ans
    elif l == 3:
        ans = (n//100-1) * two(99) + two( n % 100 )
        return  ans
    else:
        ans = 729 * (l-1) * (l-2) * (l-3) // 6
        t = n % (10**(l-1))
        ans += two(t) + two(10**(l-1)-1)* (n// (10**(l-1))-1)
        return ans
    return ans

if k == 1:
    ans = one(n)
if k == 2:
    ans = two(n)
if k == 3:
    ans = three(n)

if l <= 3 and n != one(n) + two(n) + three(n):
    print(one(n),two(n),three(n))
    print("Error!")

print(ans)

Solution (Python):
def nlog(n):
    for i in range(200):
        if n<10**i:
            return i-1
n=int(input())
k=int(input())

ns=nlog(n)
n1=n//10**int(ns)


if k==1:
    icnt=0
    for i in range(0,ns+1):
        for i1 in range(1,10):
            x=i1*10**i
            if x<=n:
                icnt=icnt+1
    print(icnt)
elif k==2:
    icnt=0
    for i in range(0,ns):
        for j in range(i+1,ns+1):
            for i1 in range(1,10):
                for j1 in range(1,10):
                    x=i1*10**i+j1*10**j
                    if x<=n:
                        icnt=icnt+1
    print(icnt)
elif k==3 and n<=122:
    icnt=0
    print(icnt)
elif k==3 and n>=123:
    icnt=0
    for i in range(0,ns):
        for j in range(i+1,ns+1):
            for i1 in range(1,10):
                for j1 in range(1,10):
                    x=n1*10**ns+i1*10**i+j1*10**j
                    if x<=n:
                        icnt=icnt+1

    icnt=icnt+int((n1-1)*ns*(ns-1)/2*9*9)
    icnt=icnt+int(ns*(ns-1)*(ns-2)/6*9*9*9)

    print(icnt)

Solution (Python):
from itertools import product
from collections import defaultdict
def resolve():
    s = input()
    K = int(input())
    dp = defaultdict(int)
    dp[0, 0, 0] = 1
    for i, less, k in product(range(len(s)), (0, 1), range(K+1)):
        max_d = 9 if less else int(s[i])
        max_d = 0 if k == K else max_d
        for d in range(max_d+1):
            less_ = less or d < max_d
            k_ = k + 1 if d > 0 else k
            dp[i + 1, less_, k_] += dp[i, less, k]
    print(sum(dp[len(s), less, K] for less in (0, 1)))
resolve()