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 sys
input = sys.stdin.readline

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


dp = [[[0] * l for _ in range(K + 1)] for _ in range(2)]
for i, item in enumerate(s):
    val = int(item)
    
    if i == 0:
        dp[0][0][i] = 1
        for j in range(1, 10):
            if j < val:
                dp[0][1][i] += 1
            if j == val:
                dp[1][1][i] += 1
        continue
    
    if val == 0:
        for k in range(K+1):
            dp[0][k][i] += dp[0][k][i-1]
            dp[1][k][i] += dp[1][k][i-1]
    else:
        for k in range(K+1):
            dp[0][k][i] += dp[0][k][i-1] + dp[1][k][i-1]
    for j in range(1, 10):
        if val == j:
            for k in range(K):
                dp[0][k+1][i] += dp[0][k][i-1]
                dp[1][k+1][i] += dp[1][k][i-1]
        elif j < val:
            for k in range(K):
                dp[0][k+1][i] += dp[0][k][i-1] + dp[1][k][i-1]
        else:
            for k in range(K):
                dp[0][k+1][i] += dp[0][k][i-1]

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

Solution (Python):
n=input()
l=len(n)
k=int(input())
def f(n,k):
  l=len(n)
  if l<k:return 0
  if n[0]=="0":return f(n[1:],k)
  if k==1:
    ans=((l-1)*9)+int(n[0])
  if k==2:
    ans=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
    ans+=f(n[1:],k-1)
  if k==3:
    ans=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
    ans+=f(n[1:],k-1)
  return ans
print(f(n,k))

Solution (Python):
n = input()
k = int(input())
l = len(n)
dp = [[[0,0] for j in range(5)] for i in range(l+1)]
dp[0][0][1] = 1
for i in range(l):
  for j in range(k+1):
    dp[i+1][j+1][0] += 9 * dp[i][j][0]
    dp[i+1][j  ][0] += dp[i][j][0]
    if n[i] == '0':
      dp[i+1][j  ][1] = dp[i][j][1]
    else:
      dp[i+1][j  ][0] += dp[i][j][1]
      dp[i+1][j+1][0] += (int(n[i]) - 1)*dp[i][j][1]
      dp[i+1][j+1][1] += dp[i][j][1]
print(dp[l][k][1] + dp[l][k][0] )

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = [int(i) for i in STR()]
k = INT()
l = len(n)
dp = [[[0, 0] for _ in range(l)] for _ in range(k + 1)] 
dp[0][0][0] = 1 
dp[1][0][1] = 1 
dp[1][0][0] = n[0] - 1 
for j in range(1, l):
    dp[0][j][0] = dp[0][j - 1][0] 

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

        dp[i][j][1] += dp[i][j - 1][1] if n[j] == 0 else 0 
        dp[i][j][1] += dp[i - 1][j - 1][1] if n[j] > 0 else 0 
print(sum(dp[k][l - 1]))

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

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

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

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

L = len(N)





dp = [[[0] * 2 for _ in range(5)] for _ in range(110)]

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


for i in range(L):
    S = int(N[i])
    for j in range(K+1):
        for k in range(2):
            
            for d in range((9 if k else S) + 1):
                dp[i+1][j + (d != 0)][k | (d < S)] += dp[i][j][k]

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

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

s = str(N)
n = len(s)

dp = [[[0]*2 for i in range(4)] for j in range(105)]
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 k == 0:
                    if d > nd:
                        continue
                    elif d < nd:
                        nk = 1
                    else:
                        pass
                if nj <= 3:
                    dp[ni][nj][nk] += dp[i][j][k]

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

Solution (Python):
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*(K+2) for j in range(2)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            for k in range(K+1):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    
                    dp[i+1][j or d < lim][k + (d != 0)] += dp[i][j][k]
    print((dp[N][0][K]+dp[N][1][K]))


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache

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

@lru_cache(maxsize=None)
def search(d, cnt, isLess):
    if d == len(N):
        return cnt == K

    a = int(N[d])

    if isLess:
        return search(d + 1, cnt + 1, isLess) * 9 + search(d + 1, cnt, isLess)

    ret = 0
    for i in range(a + 1):
        ret += search(d + 1, cnt + (i != 0), i < a)
    return ret

print(search(0, 0, False))

Solution (Python):
import numpy as np

dp = np.zeros((105,4,2),dtype=np.int32)

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

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 = int(input())
K = int(input())
n = str(N)
l = len(n)
dp0 = [[0 for _ in range(K+1)]  for _ in range(l+1)]
dp1 = [[0 for _ in range(K+1)]  for _ in range(l+1)]
dp0[0][0] = 1

for i in range(l):
    x = int(n[i])
    for j in range(K):
        dp1[i+1][j+1] += dp1[i][j]*9
        dp1[i+1][j] += dp1[i][j]
        if x > 0:
            dp1[i+1][j] += dp0[i][j]
            dp1[i+1][j+1] += dp0[i][j]*(x-1)
            dp0[i+1][j+1] += dp0[i][j]
        else:
            dp0[i+1][j] += dp0[i][j]
    dp1[i+1][K] += dp1[i][K]
    if x > 0:
        dp1[i+1][K] += dp0[i][K]
    else:
        dp0[i+1][K] += dp0[i][K]
print(dp0[-1][-1]+dp1[-1][-1])

Solution (Python):
N = [int(x) for x in input()]
K = int(input())
dp = [[[0]*2 for j in range(K+1)] for i in range(len(N)+1)]
dp[0][0][1] = 1
for i in range(len(N)):
    dp[i+1][0][0] = 1
    if N[i] == 0:
        for k in range(1, K+1):
            dp[i+1][k][0] = dp[i][k][0]+dp[i][k-1][0]*9
            dp[i+1][k][1] = dp[i][k][1]
    else:
        for k in range(1, K+1):
            dp[i+1][k][0] = dp[i][k][0]+dp[i][k-1][0]*9+dp[i][k-1][1]*(N[i]-1)+dp[i][k][1]
        for k in range(K-1, -1, -1):
            if dp[i][k][1]:
                dp[i+1][k+1][1] = dp[i][k][1]
                break
print(dp[len(N)][K][0]+dp[len(N)][K][1])

Solution (Python):
from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else nCr(size - 1, k) * (9 ** k)
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  first = int(str(n)[0])
  count += 0 if k > size else (first - 1) * nCr(size - 1, k - 1) * (9 ** (k - 1))
  for digits in combinations(range(size - 1), k - 1):
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n % (10 ** (size - 1))
      for nums in product(range(1, 10), repeat = k - 1)
    )
print(count)

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


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

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

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

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

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n2 = N[j:le]
    
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Solution (Python):
n = list(map(int,list(input())))
k = int(input())
l = len(n)
count = 0 
lst = [[0]*(k+1) for _ in range(l+1)] 
for i in range(l):
    if count < k:
        if n[i] != 0:
            lst[i+1][count] += 1
            lst[i+1][count+1] += n[i]-1
    if count == k:
        if n[i] != 0:
            lst[i+1][count] += 1
    for j in range(k):
        lst[i+1][j] += lst[i][j]
        lst[i+1][j+1] += 9*lst[i][j]
    lst[i+1][k] += lst[i][k]
    if n[i] != 0:
        count += 1
if count == k:
    print(lst[l][k]+1)
else:
    print(lst[l][k])

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

for i in range(l):
    for small in range(2):
        for j in range(k+1):
            if j==k:
                if small==0 and d[i]==0:
                    dp[i+1][small][j] += dp[i][small][j]
                else:
                    dp[i+1][1][j] += dp[i][small][j]
            else:
                a = 10 if small else d[i]+1
                for x in range(a):
                    z=j if x==0 else j+1
                    dp[i+1][small or x<d[i]][z] += dp[i][small][j]


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

Solution (Python):

from collections import Counter, deque







import sys



readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = input()
    p = int(input())
    l = len(n)

    n_0 = int(str(n)[0])

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

    for i in range(l - 1):
        a = int(n[i + 1])
        if a != 0:
            for j in range(p + 1):
                dp[i + 1][j + 1][0] += dp[i][j][0]
                dp[i + 1][j + 1][1] += 9 * dp[i][j][1] + (a - 1) * dp[i][j][0]
                dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
        else:
            for j in range(p + 1):
                dp[i + 1][j + 1][1] += 9 * dp[i][j][1]
                dp[i + 1][j][0] += dp[i][j][0]
                dp[i + 1][j][1] += dp[i][j][1]

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


if __name__ == '__main__':
    main()

Solution (Python):

n=int(input())
K=int(input())
s=str(n)
n=len(s)
ans=0

dp=[[[0]*2 for j in range(K+1)] for i in range(n+1)]
dp[0][0][0]=1
for i in range(n):
    for j in range(K+1):
        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):
def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + mondai(d, 1)
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = int(mondai(n, k))
    
print(ans)

Solution (Python):
from itertools import combinations
N = list(map(int, input()))
K = int(input())

nlen = len(N)
ans = 0
if K <= nlen:
    cmb = [9] * nlen
    for n in N:
        if n != 0:
            cmb[0] = n - 1
            for x in combinations(cmb, K):
                y = x[0]
                for z in x[1:]:
                    y *= z
                ans += y
            if K == 1:
                ans += 1
                break
            K -= 1
        cmb.pop()
print(ans)

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

l=len(N)
dp0=[[1,0,0,0] for _ in range(l+1)]
dp1=[[0,0,0,0] for _ in range(l+1)]

d=int(N)//10**(l-1)
dp0[0][1],dp1[0][1]=d-1,1

for i,c in enumerate(list(N)[1:]):
  d=int(c)
  for j in range(1,4):
    dp0[i+1][j]=dp0[i][j]+9*dp0[i][j-1]+(dp1[i][j] if d>0 else 0)+((d-1)*dp1[i][j-1] if d>1 else 0)
    dp1[i+1][j]=dp1[i][j-1] if d>0 else dp1[i][j]

print(dp0[l-1][K]+dp1[l-1][K])

Solution (Python):

import sys


def solve(N: "List[int]", K: int):
    print(dfs(N, False, 0, K, 0))


def dfs(N: "List[int]", f: bool, num: int, K: int, idx: int):
    if num == K:
        return 1
    if K - num > len(N) - idx:
        return 0
    else:
        if f:
            return dfs(N, True, num, K, idx + 1) + dfs(N, True, num + 1, K, idx + 1) * 9
        else:
            s = 0
            for i in range(N[idx] + 1):
                if i == N[idx]:
                    if i == 0:
                        s += dfs(N, False, num, K, idx + 1)
                    else:
                        s += dfs(N, False, num + 1, K, idx + 1)
                else:
                    if i == 0:
                        s += dfs(N, True, num, K, idx + 1)
                    else:
                        s += dfs(N, True, num + 1, K, idx + 1)
            return s



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = list(map(int, next(tokens)))  
    K = int(next(tokens))  
    solve(N, K)

if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
n=int(input())
k=int(input())
s=str(n)
l=len(s)
dp0=[[0 for j in range(k+1)] for i in range(l)]
dp1=[[0 for j in range(k+1)] for i in range(l)]

x=int(s[0])
dp0[0][1]=x-1
dp0[0][0]=1
dp1[0][1]=1
for i in range(1,l):
    x=int(s[i])
    dp0[i][0]=1

    for j in range(1,k+1):
        dp0[i][j]+=dp0[i-1][j-1]*9+dp0[i-1][j]
        if x>0:
            dp0[i][j]+=dp1[i-1][j-1]*(x-1)+dp1[i-1][j]
            dp1[i][j]=dp1[i-1][j-1]
        else:
            dp1[i][j]=dp1[i-1][j]

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

Solution (Python):
from sys import stdin

N = stdin.readline().rstrip()
K = int(stdin.readline().rstrip())

N = N[::-1]

dp = [[0] * len(N) for i in range(3)]

dp[0][0] = int(N[0])

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

for i in range(1, len(N)):
    if N[i] == '0':
        dp[1][i] = dp[1][i - 1]
    else:
        dp[1][i] = dp[0][i - 1] + 9 * 9 * i * (i - 1)  // 2 + 9 * i * (int(N[i]) - 1)

for i in range(2, len(N)):
    if N[i] == '0':
        dp[2][i] = dp[2][i - 1]
    else:
        dp[2][i] = dp[1][i - 1] + 9 * 9 * 9 * i * (i - 1) * (i - 2) // 6 + 9 * 9 * i * (i - 1) // 2 * (int(N[i]) - 1)

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

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] +=DP[i-1][flag][j-1]

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

Solution (Python):
import math
import sys
n=int(input())
k=int(input())
s=str(n)
l=len(s)
dp0=[[0 for j in range(k+1)] for i in range(l)]
dp1=[[0 for j in range(k+1)] for i in range(l)]

x=int(s[0])
dp0[0][1]=x-1
dp0[0][0]=1
dp1[0][1]=1
for i in range(1,l):
    x=int(s[i])
    dp0[i][0]=1

    for j in range(1,k+1):
        dp0[i][j]+=dp0[i-1][j-1]*9+dp0[i-1][j]
        if x>0:
            dp0[i][j]+=dp1[i-1][j-1]*(x-1)+dp1[i-1][j]
            dp1[i][j]=dp1[i-1][j-1]
        else:
            dp1[i][j]=dp1[i-1][j]

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

Solution (Python):
import math
import sys

comb=[0,0,0,1,3,6,10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950]
n=int(input())
k=int(input())
s=str(n)
L=len(s)

ans=0
if n<k:
    ans=0

elif k==1:
    for i in range(L):
        for a in range(1,10):
            if a*(10**i)<=n:
                ans+=1

elif k==2:
    for i in range(1,L):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=n: ans+=1


elif k==3 and L<4:
    for a in range(1,10):
        for b in range(1,10):
            for c in range(1,10):
                if a*100+b*10+c<=n: ans+=1

elif k==3 and L>=4:
    ans=sum(comb[:L])*9**3
    ans+=comb[L]* 81 * (int(s[0])-1)

    m=int(s[1:])
    for i in range(1,L-1):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=m: ans+=1

print(ans)

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

a = 1
b = [0] * (K + 1)
b[0] = 1
b[1] = int(N[0]) - 1

for c in N[1:]:
    t = int(c)
    for i in range(K - 1, -1, -1):
        b[i + 1] += b[i] * 9
    if t != 0:
        if a + 1 <= K:
            b[a + 1] += t - 1
        if a <= K:
            b[a] += 1
        a += 1

if a == K:
    print(b[K] + 1)
else:
    print(b[K])

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

a = [0] * (K + 1)
b = [0] * (K + 1)

t = int(N[0])

a = 1
b[0] = 1
b[1] = t - 1

for c in N[1:]:
    t = int(c)
    for i in range(K - 1, -1, -1):
        b[i + 1] += b[i] * 9
    if t != 0:
        if t != 1 and a + 1 <= K:
            b[a + 1] += t - 1
        if a <= K:
            b[a] += 1
        a += 1

if a == K:
    print(b[K] + 1)
else:
    print(b[K])

Solution (Python):
s = input()
K = int(input())
N = len(s)
dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(105)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(4):
        for k in range(2):
            nd = ord(s[i]) - ord('0')
            for d in range(10):
                ni, nj, nk = i + 1, j, 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())
n = len(N)
dp = [[[0]*(K+1) for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(1, n+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] += dp[i-1][1][k-1]*9
            if l != 0:
                dp[i][0][k] += dp[i-1][0][k-1]
                dp[i][1][k] += dp[i-1][0][k-1]*(l-1)
                
print (dp[n][0][K]+dp[n][1][K])

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

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

for i in range(len(n)):
    now = int(n[i])
    for j in range(2):
        for non_zero in range(k+1):
            for m in range(10):
                if j == 1 or (j == 0 and m < now):
                    next_j = 1
                elif m == now:
                    next_j = 0
                else:
                    continue

                if non_zero == k and m != 0:
                    continue
                elif m == 0:
                    next_non_zero = non_zero
                else:
                    next_non_zero = non_zero + 1
                
                DP[i+1][next_j][next_non_zero] += DP[i][j][non_zero]

ans = DP[len(n)][1][k] + DP[len(n)][0][k]
print(ans)

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

l = len(N)

nozero = [0]*l
if N[0] != "0":
    nozero[0] = 1

for i in range(1, l):
    nozero[i] = nozero[i-1]
    if N[i] != "0":
        nozero[i] += 1 

dp0 = [[0]*2 for _ in range(l)]
dp1 = [[0]*2 for _ in range(l)]
dp2 = [[0]*2 for _ in range(l)]
dp3 = [[0]*2 for _ in range(l)]

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

def dp(K):
    dps = [dp0, dp1, dp2, dp3]
    return dps[K]

dp(1)[0][0] = int(N[0])

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

            
        if nozero[i] == k:
            dp(k)[i+1][1] += (sum(dp(k)[i])-1)*1
        else:
            dp(k)[i+1][1] += sum(dp(k)[i])*1

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

Solution (Python):
N=str(input())
K=int(input())
length=len(N)
dp=[[0]*10 for _ in range(length+1)]
dp[0][0]=1
def index(flag_less,k):
  if flag_less==0 and k==0:
    return 0
  elif flag_less==1 and k==0:
    return 1
  elif flag_less==0 and k==1:
    return 2
  elif flag_less==1 and k==1:
    return 3
  elif flag_less==0 and k==2:
    return 4
  elif flag_less==1 and k==2:
    return 5
  elif flag_less==0 and k==3:
    return 6
  elif flag_less==1 and k==3:
    return 7
  elif flag_less==0 and k==4:
    return 8
  else:
    return 9
  
for i in range(length):
  max_digit=int(N[i])
  for state in range(10):
    range_digit=9 if state%2 else max_digit
    for d in range(range_digit+1):          
      flag_less_next=0
      if state%2==1 or d<max_digit:
        flag_less_next=1
      prev_k=state//2
      if d!=0:
        next_k=min(4,prev_k+1)      
      else:
        next_k=prev_k
      next_state=index(flag_less_next,next_k)  
      dp[i+1][next_state]+=dp[i][state]

print(dp[length][2*K]+dp[length][2*K+1])

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

S = str(N)
keta = len(S)


dp1 = [ [ 0 ]* (keta + 1)  for _ in range(100) ] 
dp2 = [  [ 0 ]* (keta + 1)  for _ in range(100) ] 


i = int(S[0])
dp2[0][0] = 1 

for n in  range(0,keta):
    
    for k in range(0, K + 1):
        num = int(S[n])  
        num_to_9  = 9 - num  
        num_hiku1_to_1 = max(0,num - 1) 
        
        

        if num == 0:
            dp1[k + 1][n + 1] += dp1[k][n] * 9 
            dp1[k][n + 1] += dp1[k][n] 
            
            dp2[k][n + 1] += dp2[k][n] 

        else:
            dp1[k + 1][n + 1] += dp1[k][n] * 9 
            dp1[k + 1][n + 1] += dp2[k][n] * (num - 1)  
            dp2[k + 1][n + 1] += dp2[k][n] 

            
            dp1[k][n + 1] += dp1[k][n] 
            

            dp1[k][n + 1] += dp2[k][n] 
            
        


print(dp1[K][keta] + dp2[K][keta])

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
k = ii()


n = len(s)
dp = [[0]*(n) for _ in range(4)]
dp[0][0] = 1
for i in range(1,n):
    
    dp[0][i] = dp[0][i-1] 
    
    dp[1][i] = dp[0][i-1] * 9 + dp[1][i-1]
    
    dp[2][i] = dp[1][i-1]*9 + dp[2][i-1]
    dp[3][i] = dp[2][i-1]*9 + dp[3][i-1]

ans = 0
for i in range(n):
    ima = int(s[i])
    if i ==-1 :
        ans += (ima -1) * dp[k-1][n-1-i]
        k -= 1
    else:
        if ima != 0:
            ans += (ima -1) * dp[k-1][n-1-i] + dp[k][n-1-i]
            k -= 1
    if k == 0:
        ans += 1
        break
print(ans)

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

if len(n) <= k:
    cnt = 0
    for i in range(1,int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            cnt += 1
    print(cnt)
    exit()

cnt = 0
l = len(n)
def combi(n,k):
    ans = 1
    if k == 0:
        return ans
    for i in range(k):
        ans = ans * (n-i) // (i+1)
    return ans
flag = 0
for i in range(l):
    if flag > k:
        break
    if n[i] == '0':
        if i == l-1 and k == flag:
            cnt += 1
        continue
    flag += 1
    cnt += int(((int(n[i])-1)*9**(k-flag))*combi(l-i-1,k-flag) + 9**(k-flag+1)*combi(l-i-1,k-flag+1))

print(cnt)

Solution (Python):
def main():
    s = [int(char) for char in input()]
    l = len(s)
    k = int(input())

    tmp = 0
    nonzero = []
    for number in s:
        if number > 0:
            tmp += 1
        nonzero.append(tmp)
    nonzero.append(0)  

    def binomial(n, k):
        if n < k or n < 0 or k < 0:
            return 0
        if k == 0:
            return 1
        if k == 1:
            return n
        if k == 2:
            return n * (n-1) // 2
        if k == 3:
            return n * (n-1) * (n-2) // 6
        raise ValueError

    def dp(i, _cache={-1: 0}):
        if i in _cache:
            return _cache[i]
        if nonzero[i-1] > k or s[i] == 0:
            result = dp(i-1)
            _cache[i] = result
            return result
        if nonzero[i-1] == k:
            result = dp(i-1) + 1
            _cache[i] = result
            return result
        result = (
            dp(i-1) +
            (s[i] - 1) * binomial(l - 1 - i, k - nonzero[i-1] - 1) *
            9 ** (k - nonzero[i-1] - 1) +
            binomial(l - 1 - i, k - nonzero[i-1]) *
            9 ** (k - nonzero[i-1])
        )
        _cache[i] = result
        return result
    
    print(dp(l-1) + (nonzero[l-1] == k))


main()

Solution (Python):
def main():
    s = [int(char) for char in input()]
    l = len(s)
    k = int(input())

    tmp = 0
    nonzero = []
    for number in s:
        if number > 0:
            tmp += 1
        nonzero.append(tmp)
    nonzero.append(0)  

    def binomial(n, k):
        if n < k or n < 0 or k < 0:
            return 0
        if k == 0:
            return 1
        if k == 1:
            return n
        if k == 2:
            return n * (n-1) // 2
        if k == 3:
            return n * (n-1) * (n-2) // 6
        raise ValueError

    def dp(i, _cache={-1: 0}):
        if i in _cache:
            return _cache[i]
        if nonzero[i-1] > k or s[i] == 0:
            result = dp(i-1)
            _cache[i] = result
            return result
        if nonzero[i-1] == k:
            result = dp(i-1) + 1
            _cache[i] = result
            return result
        result = (
            dp(i-1) +
            (s[i] - 1) * binomial(l - 1 - i, k - nonzero[i-1] - 1) *
            9 ** (k - nonzero[i-1] - 1) +
            binomial(l - 1 - i, k - nonzero[i-1]) *
            9 ** (k - nonzero[i-1])
        )
        _cache[i] = result
        return result
    
    print(dp(l-1) + (nonzero[l-1] == k))


main()

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
n = int(input())
k = int(input())


@lru_cache(maxsize=None)
def f(n, k):
    if k == 0:
        return 1
    if len(str(n)) == 1:
        if k >= 2:
            return 0
        if k == 1:
            return n

    r = n % 10
    m = (n - r) // 10
    return r * f(m, k-1) + (9 - r) * f(m-1, k-1) + f(m, k)


print(f(n, k))

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
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 [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  l=len(s)
  _k=I()

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

  for i in range(l):
    nd=int(s[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 nd>d:
              nk=1
            if nd<d:
              continue

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

  return dp[l][_k][0]+dp[l][_k][1]


print(main())