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

"""
Created on Wed Feb 12 17:17:55 2020

@author: matsui
"""
def check(N,K):
    ans=0
    for i in range(N+1):
        c=0
        for s in str(i):
            if int(s)!=0: c+=1
        if c==K: ans+=1
    return ans

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

ans=0
if K==1:
    ans=int(N[0])+(L-1)*9
           
if K==2:
    dp=[0]*(L+1)
    for i in range(2,L):
        dp[i]=9*9*(i-1)
          
    dp[L]=(int(N[0])-1)*9*(L-1)
    
    for i in range(1,L):
        if int(N[i])!=0:
            dp[L]+=int(N[i])+9*(L-i-1)
            break
     
    ans=sum(dp)
    
if K==3:
    dp=[0]*(L+1)
    for i in range(3,L):
        dp[i]=9*(dp[i-1]/9+9*9*(i-2))
        
        
    dp[L]=(int(N[0])-1)*(dp[L-1]/9+9*9*(L-2))
    
    for i in range(1,L):
        if int(N[i])!=0:
            dp[L]+=(int(N[i])-1)*9*(L-i-1)+9*9*(L-i-1)*(L-i-2)/2
            break
        
    for j in range(i+1,L):
        if int(N[j])!=0:
            dp[L]+=int(N[j])+9*(L-j-1)
            break
        
    
    
           
    ans=sum(dp)
    
print(int(ans))

Solution (Python):


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

dp = {}


def rec(i, smaller, count):
    if (i, smaller, count) in dp:
        return dp[(i, smaller, count)]
    if i == len(n):
        dp[(i, smaller, count)] = 1 if count == k else 0
        return dp[(i, smaller, count)]
    ret = 0
    upper = 10 if smaller else int(n[i]) + 1
    for j in range(upper):
        ret += rec(
            i + 1,
            True if smaller or j < int(n[i]) else False,
            count + 1 if 0 < j else count,
        )
    dp[(i, smaller, count)] = ret
    return ret


print(rec(0, False, 0))

Solution (Python):
n=input()
l=len(n)
K=int(input())
dp=[[[0]*2 for i in range(4)]for j in range(105)]
dp[0][0][0]=1
for i in range(l):
    for j in range(4):
        for k in range(2):
            nd=int(n[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 nd>d:
                        nk=1
                    if nd<d:
                        continue
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[l][K][1]+dp[l][K][0])

Solution (Python):
"""

dp[i][k][s] 
上からi桁目までみて、
0じゃない数字がk個。
上i桁が一致していたら0,違っていたら1
"""
S = input()
K = int(input())
m = len(S) 

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


dp[0][0][0] = 1
for i in range(m):
    for j in range(4):
        for k in range(2):
            
            digit = int(S[i])
            i_next = i + 1            
            
            for d in range(10):
                
                if d == 0: 
                    j_next = j
                else: 
                    j_next = j + 1
                if j_next > K: 
                    
                    continue
                
                if k == 0:
                    if d > digit: 
                        continue 
                    elif d == digit: 
                        k_next = 0 
                    else: 
                        k_next = 1
                else:
                    k_next = 1 
                
                dp[i_next][j_next][k_next] += dp[i][j][k]

ans = sum(dp[m][K])
print(ans)

Solution (Python):
n = input()
K = int(input())
dp = [[[0]*(2) for _ in range(4)] for _ in range(105)]

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

for i in range(len(n)):
    for j in range(4):
        for k in range(2):
            nd=int(n[i])
            for d in range(10):
                ni=i+1
                nj=j
                nk=k
                if d:
                    nj+=1
                if nj>K:
                    continue
                if nk==0:
                    if d>nd:
                        continue
                    if d<nd:
                        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
import socket

hostname = socket.gethostname()

if hostname in ['F451C', 'N551J']:
    sys.stdin = open('e1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()

def solve(N, K):
  s = list(reversed(str(N)))
  a = [i for i in range(len(s)) if s[i] != '0']
  c = [int(s[i]) for i in range(len(s)) if s[i] != '0']

  
  
  res = 0
  if K == 1:
    for p in range(100):
      if p == a[-1]:
        res += c[-1]
      if p < a[-1]:
        res += 9

  if K == 2:
    for p in range(100):
      for q in range(p):
        if p < a[-1]:
          res += 9 * 9
        if p == a[-1]:
          if len(a) >= 2:
            if q < a[-2]:
              res += c[-1] * 9
            if q == a[-2]:
              res += (c[-1] - 1) * 9 + c[-2]
            if q > a[-2]:
              res += (c[-1] - 1) * 9
          if len(a) == 1:
            res += (c[-1] - 1) * 9

  if K == 3:
    for p in range(100):
      for q in range(p):
        for r in range(q):
          if p < a[-1]:
            res += 9 * 9 * 9
          if p == a[-1]:
            if len(a) >= 3:
              if q < a[-2]:
                res += c[-1] * 9 * 9
              if q == a[-2]:
                if r < a[-3]:
                  res += (c[-1] - 1) * 9 * 9
                  res += 1 * (c[-2] - 1) * 9
                  res += 1 * 1 * 9
                if r == a[-3]:
                  res += (c[-1] - 1) * 9 * 9
                  res += 1 * (c[-2] - 1) * 9
                  res += 1* 1 * c[-3]
                if r > a[-3]:
                  res += (c[-1] - 1) * 9 * 9
                  res += 1 * (c[-2] - 1) * 9
                  
              if q > a[-2]:
                res += (c[-1] - 1) * 9 * 9
            if len(a) == 2:
              if q < a[-2]:
                res += c[-1] * 9 * 9
              if q == a[-2]:
                res += (c[-1] - 1) * 9 * 9
                res += 1 * (c[-2] - 1) * 9
              if q > a[-2]:
                res += (c[-1] - 1) * 9 * 9
            if len(a) == 1:
              res += (c[-1] - 1) * 9 * 9


  return res


def solve_correct_but_slow(N, K):
  res = 0
  for i in range(1, N+1):
    s = str(i)
    nonzero = len(s) - s.count('0')
    if nonzero == K:
      res += 1
  return res


def find_mismatch():
  N = 1
  while True:
    for K in range(1, 4):
      expected = solve_correct_but_slow(N, K)
      output = solve(N, K)


      if output == expected:
        
        
        continue

      print()
      print('N, K, expected, output:', end=' ')
      print(N, K, expected, output)
      return
    N += 1




def main():
    N = read_int()
    K = read_int()
    res = solve(N, K)
    print(res)


main()

Solution (Python):
def comb(a, b):
    ans = 1
    for i in range(b):
        ans *= (a - i)
    for i in range(2, b + 1):
        ans //= i
    return ans

def solve_k1(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    ans += 9 * (len_N - 1)
    ans += int(N[0])
    return ans

def solve_k2(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    if len_N < 2:
        return 0
    ans = comb((len_N - 1), 2) * 9 ** 2 + (int(N[0]) - 1) * ((len_N - 1) * 9) + solve_k1(int(N[1:]))
    return ans

def solve_k3(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    if len_N < 3:
        return 0
    ans = comb(len_N - 1, 3) * 9 ** 3 + (int(N[0]) - 1) * comb(len_N - 1, 2) * 9 ** 2 + solve_k2(int(N[1:]))
    return ans

N = int(input())
K = int(input())
ans = 0
if K == 1:
    ans = solve_k1(N)
elif K == 2:
    ans = solve_k2(N)
else:
    ans = solve_k3(N)
print(ans)

Solution (Python):
import math
def check1(N):
    if N == 0:
        return 0
    n = int(math.log10(N))
    return 9*n+(N//(10**n))
def check2(N):
    if N == 0:
        return 0
    n = int(math.log10(N))
    return n*(n-1)/2*81+(N//(10**n)-1)*n*9+check1(N%(10**n))
def check3(N):
    if N == 0:
        return 0
    n = int(math.log10(N))
    summ = 0
    if n >= 3:
        for i in range(n):
            summ += i*(i-1)/2
    return summ*729+(N//(10**n)-1)*n*(n-1)/2*81+check2(N%(10**n))
def main():
    N = int(input())
    K = int(input())
    if K == 1:
        print(int(check1(N)))
    elif K == 2:
        print(int(check2(N)))
    elif K == 3:
        print(int(check3(N)))
        
main()

Solution (Python):


from functools import lru_cache

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

@lru_cache(None)
def f(n, k):
    assert n >= 0 
    if n < 10:
        if k == 0:
            return 1 
        elif k == 1:
            return n 
        return 0 
    
    q, r = divmod(n, 10)
    res = 0
    
    if k >= 1:
        
        res += f(q, k-1) * r
        res += f(q-1, k-1) * (9 - r)
    
    res += f(q, k)
    return res

print(f(n, k))

Solution (Python):
def solve2():
    N = raw_input()
    K = int(raw_input())
    L = len(N)
    digN = [int(d) for d in N]
    dp = [[[0 for k in range(2)] for j in range(K+1)] for i in range(L+1)]
    dp[0][0][0] = 1
    for i in range(L):
        for j in range(K+1):
            for k in range(2):
                for d in range(10):
                    ni = i + 1
                    nj = j
                    nk = k
                    if d != 0:
                        nj += 1
                    if nj > K:
                        continue
                    if k == 0:
                        if d > digN[i]:
                            continue
                        if d < digN[i]:
                            nk = 1
                    dp[ni][nj][nk] += dp[i][j][k]
    print dp[L][K][0] + dp[L][K][1]

if __name__ == '__main__':
    solve2()

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

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    
    
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        
        r += 1
    return r

def COUNT(N,K):
    digit = list(map(int, str(N)))
    M = len(digit)
    C = count(digit[0], M, K)
    N_ = N % pow(10, M-1)
    return C, N_
    

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

C = 0
while (N>0) and (K>0):
    c, N = COUNT(N, K)
    C+= c
    K-= 1

print(C)

Solution (Python):

def factorial(a):
    r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    
    
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        
        r += 1
    return r

def COUNT(N,K):
    digit = list(map(int, str(N)))
    M = len(digit)
    C = count(digit[0], M, K)
    if len(digit) > 1:
        N_ = int("".join(map(str, digit[1:])))
    else:
        N_ = 0
    return C, N_
    

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

C = 0
while (N>0) and (K>0):
    c, N = COUNT(N, K)
    C+= c
    K-= 1

print(C)

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

def dp(N,K):
    keta = len(str(N))
    table = [[[0,0] for i in range(K+1)] for j in range(keta+1)]
    table[0][0][0]=1
    for i in range(keta):
        for j in range(K+1):
            for k in range(2):
                enable_num = int(str(N)[i]) if k==0 else 9
                for x in range(enable_num+1):
                    if x==0:
                        next_j = j
                    else:
                        next_j = j + 1
                    if next_j > K: continue
                    if k == 0 and x == enable_num:
                        next_k = 0
                    else:
                        next_k = 1
                    table[i+1][next_j][next_k]+=table[i][j][k]
    return table[keta][K][0] + table[keta][K][1]
print(dp(N,K))

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32
from functools import lru_cache



def solve(N: int, K: int):
    @lru_cache(None)
    def f(n: int, k:int):
        if n < 10:
            if k == 0:
                
                return 1
            elif k == 1:
                
                return n
            else:
                
                return 0

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


    print(f(N, K))

    return



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

if __name__ == '__main__':
    main()

Solution (Python):
from math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

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

def rec(n, k, smaller):
    n = n.lstrip('0')

    if k == 0:
        return 1

    if len(n) < k:
        return 0

    if k == 1:
        if len(n) == 1:
            return int(n)


    if smaller:
        return nCr(len(n), k) * 9 ** k


    ret = 0
    ret += rec(n[1:], k-1, False)
    ret += rec('9'*(len(n)-1), k-1, True) * (int(n[0]) - 1)
    ret += rec('9'*(len(n)-1), k, True)

    return ret
    
ans = rec(N, K, False)
print(ans)

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

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

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

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

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

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

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

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

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

Solution (Python):










import numpy as np

nrow = input()
k = int(input())

l = len(nrow)

dp = np.zeros((l, 2, 4), int)
topmax = int(nrow[0])
dp[0, 0, 1] = 1  
dp[0, 1, 0] = 1  
dp[0, 1, 1] = topmax-1  

for i in range(1, l):
  topmax = int(nrow[i])

  dp[i, 1, 0] = dp[i-1, 1, 0]  
  for j in range(1,4):
    dp[i, 1, j] = dp[i-1, 1, j] + dp[i-1, 1, j-1] * 9  

  if topmax == 0:
    for j in range(1, 4):
      dp[i, 0, j] = dp[i-1, 0, j]  
  else:
    dp[i, 0, 2] = dp[i-1, 0, 1]  
    dp[i, 0, 3] = dp[i-1, 0, 2]  
    dp[i, 1, 1] += dp[i-1, 0, 1] 
    dp[i, 1, 2] += dp[i-1, 0, 2]+dp[i-1, 0, 1] * (topmax-1)  
    dp[i, 1, 3] += dp[i-1, 0, 3]+dp[i-1, 0, 2] * (topmax-1)  

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

Solution (Python):




"""
問題：
n以下の0以外の数字の数が丁度k個である整数の個数を求めよ。

解法：
桁DP
以下の条件があったら桁DPを疑うべし
・桁に関している
・制約が大きい
・整数nがある範囲を動くときの、〜〜〜の最大値を求めよ
・整数nがある範囲を動くときの、〜〜〜という条件を満たすものは何通りあるか←今回はコッチ

考え方：
桁DPでは上位桁から条件を絞っていって、下位桁にクエリを出すという再帰方法で解く。この時、何回もこの再帰をやっていると
下位桁が全く同じ条件になることが出現するので、それをメモ化、呼び出しして動的に解く。
そのためのdpテーブルは３次元で、各階層に対応するのは以下のようなデータ。

dp[i][j][k] = (上から)i桁まで見た,j個Kを使った,k=0:制約ありk=1:自由     の時の条件を満たす場合の個数(value)

問題により多少dpテーブルの内容や順番は異なるが、i桁目まで見た、と、自由度kについての制約は必ずテーブルの中に入る。
もうひとつ、今回で言えばjのテーブルは、kをいくつ使ったか、全桁の合計がD以下であるみたいな問題はいま合計はいくらか
みたいなデータになる。
"""

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

dp = [[[0]*2 for j in range(4)] for i in range(105)]
dp[0][0][0] = 1
for i in range(m): 
    for j in range(4): 
        for k in range(2): 
            
            nd = int(n[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[m][K][0] + dp[m][K][1] 

print(ans)

Solution (Python):
import math
def combi(n,r):
    if r > n:return 0
    return math.factorial(n) // (math.factorial(n - r)*(math.factorial(r)))


def solve(i,k,smaller):
    
    if i == N:
        if k == 0:return 1
        else: return 0

    
    if k == 0:return 1

    
    
    
    if smaller: return combi(N-i, k)*(9**k)
    else:
        
        if S[i] == '0':return solve(i+1,k,False)
        else:
            zero = solve(i+1, k, True)
            aida = solve(i+1, k-1, True) * (int(S[i])-1)
            icchi = solve(i+1, k-1, False)
            return zero + aida + icchi


S = input()
N = len(S)
K = int(input())
print((solve(0,K,False)))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def cmb(n, k):
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n)
    b = factorial(k)
    c = factorial(n - k)
    return a // b // c

def dfs(i, k, lenn, sn):
    if k == 0:
        return 1
    if i == lenn:
        return 0
    if sn[i] == "0":
        return dfs(i + 1, k, lenn, sn)
    return cmb(lenn - i - 1, k) * 9 ** k + cmb(lenn - i - 1, k - 1) * 9 ** (k - 1) * (int(sn[i]) - 1) + dfs(i + 1, k - 1, lenn, sn)


def solve():
    n, k = IR(2)
    lenn = len(str(n))
    sn = str(n)
    ans = dfs(0,k,lenn,sn)
    print(int(ans))
    return



if __name__ == '__main__':
    solve()

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




dp0=[[0]*(k+1) for _ in range(keta)]
dp1=[[0]*(k+1) for _ in range(keta)]
dp0[0][0]=1
dp0[0][1]=int(n[0])-1
dp1[0][1]=1
for i in range(1,keta):
	if n[i]=="0":
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp0[i-1][j-1]*9+dp0[i-1][j]
	else:
		for j in range(1,k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(int(n[i])-1)+dp0[i-1][j-1]*9+dp0[i-1][j]
print(dp0[-1][k]+dp1[-1][k])

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




dp0=[[0]*(k+1) for _ in range(keta)]
dp1=[[0]*(k+1) for _ in range(keta)]
dp0[0][0]=1
dp0[0][1]=int(n[0])-1
dp1[0][1]=1
for i in range(1,keta):
	
	
	
	
	
	
	if n[i]=="0":
		conf=dp0
		notconf=dp1
		for j in range(k+1):
			notconf[i][j]=notconf[i-1][j]
		conf[i][0]=conf[i-1][0]
		for j in range(1,k+1):
			conf[i][j]=9*conf[i-1][j-1]+conf[i-1][j]
	else:
		for j in range(1,k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(int(n[i])-1)+dp0[i-1][j-1]*9+dp0[i-1][j]
print(dp0[-1][k]+dp1[-1][k])

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

S = [ord(N[i]) - ord('0') for i in range(L)]

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

dp0[0][0] = 1
dp0[0][1] = S[0]-1
dp1[0][0] = 0
dp1[0][1] = 1

for i in range(1, L):
	for j in range(K+1):
		if j == 0:
			dp0[i][j] = dp0[i-1][j]
			dp1[i][j] = dp1[i-1][j]
		else:
			dp0[i][j] = dp0[i-1][j-1]*9 + dp0[i-1][j] 
			if S[i] > 0:
				dp0[i][j] = dp0[i][j] + dp1[i-1][j-1]*(S[i]-1) + dp1[i-1][j]
				
			dp1[i][j] = dp1[i-1][j-(S[i]>0)]
	
print(dp0[L-1][K] + dp1[L-1][K])

Solution (Python):
from functools import lru_cache
@lru_cache(None)
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 1
    else :
        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):
n=input()
k=int(input())
L=len(n)
conf=[[0 for i in range(k+1)] for j in range(L)]
conf[0][1]=int(n[0])-1
conf[0][0]=1
notconf=[[0 for i in range(k+1)] for j in range(L)]
notconf[0][1]=1
for i in range(1,L):
    if n[i]=="0":
        for j in range(k+1):
            notconf[i][j]=notconf[i-1][j]
        conf[i][0]=conf[i-1][0]
        for j in range(1,k+1):
            conf[i][j]=9*conf[i-1][j-1]+conf[i-1][j]
    else:
        looking=int(n[i])
        for j in range(1,k+1):
            notconf[i][j]=notconf[i-1][j-1]
        conf[i][0]=conf[i-1][0]
        for j in range(1,k+1):
            conf[i][j]=notconf[i-1][j]+notconf[i-1][j-1]*(looking-1)+conf[i-1][j-1]*9+conf[i-1][j]
print(notconf[-1][k]+conf[-1][k])

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

"""
dp[i][j][k]
i: 決定した桁数
j: N以下確定
k: 0出ない数字がちょうどk個(k = 0,1,2,3)
   4個以上(k=4)
"""

def solve(a):
	a = str(a)
	L = len(a)
	dp = [[[0]*5 for i in range(2)] for j in range(L+1)]
	dp[0][0][0] = 1
	for i in range(L):
		D = int(a[i])
		for j in range(2):
			for k in range(5):
				for d in range(10 if j else D+1):
					if k>=4:
						dp[i+1][j or (d<D)][k] += dp[i][j][k]
					else:
						if d!=0:
							dp[i+1][j or (d<D)][k+1] += dp[i][j][k]
						else:
							dp[i+1][j or (d<D)][k] += dp[i][j][k]
	return dp[L][0][K] + dp[L][1][K]

print(solve(N))

Solution (Python):

def solve():
    N = raw_input()
    K = int(raw_input())
    L = len(N)
    
    
    
    
    
    digN = [int(d) for d in N]
    dp0 = [[1 for i in range(K+1)] for i in range(L)]
    dp1 = [[1 for i in range(K+1)] for i in range(L)]
    dp0[0][0] = 1
    dp1[0][0] = 1
    dp0[0][1] = digN[L-1]
    dp1[0][1] = 9
    for i in range(2, K+1):
        dp0[0][i] = 0
        dp1[0][i] = 0
    for i in range(1, L):
        for j in range(1, K+1):
            if digN[L - 1 - i] > 0:
                dp0[i][j] = (digN[L - 1 - i] - 1) * dp1[i-1][j-1] + dp0[i-1][j-1] + dp1[i-1][j]
            else:
                dp0[i][j] = dp0[i-1][j]
            dp1[i][j] = 9 * dp1[i-1][j-1] + dp1[i-1][j]
    print dp0[L-1][K]

if __name__ == '__main__':
    solve()

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

keta = len(N)

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

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

for i in range(1, keta + 1):
    for j in range(K + 1):
        if j > 0:
            dp[i][0][j] += dp[i-1][0][j-1] * (N[i-1] != '0')
            dp[i][1][j] += dp[i-1][0][j-1] * (max((int(N[i-1]) - 1),0)) + dp[i-1][1][j-1] * 9

        dp[i][0][j] += dp[i-1][0][j] * (N[i-1] == '0')
        dp[i][1][j] += dp[i-1][0][j] * (N[i-1] != '0') + dp[i-1][1][j]
        
ans = dp[keta][0][K] + dp[keta][1][K]
print(ans)

Solution (Python):
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 1
    else :
        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):
"""
dp[i][j][k]
i桁で非零要素をj個含み, 
「k==0」→ Nのi桁目までと一致
「k==1」→ Nのi桁目までよりも小さい
"""

N = int(input())
K = int(input())
digit = len(str(N))
N_str = str(N)

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

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

for i in range(digit): 
    for j in range(4): 
        for k in range(2):
            for d in range(10):
                ni = i+1; nj = j; nk = k
                nd = int(N_str[i])
                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[digit][K][1]+dp[digit][K][0]

print(ans)

Solution (Python):
def f(n, k):
    if k == 0:
        return 1
    if k == 1 and n < 10:
        return n

    s = str(n)
    length = len(s)

    ans = g(length - 1, k)
    for i in range(1, int(s[0])):
        if 1 < k:
            ans += g(length - 1, k - 1)
        else:
            ans += 1
    if 1 < k:
        ans += f(n % 10 ** (length - 1), k - 1)
    elif k == 1:
        ans += 1
    return ans


def g(n, k):
    if n == 0:
        return 0
    if n < k:
        return 0
    if k == 1:
        return n * 9
    elif k == 2:
        return n * (n - 1) // 2 * 9 ** 2
    elif k == 3:
        return n * (n - 1) * (n - 2) // 6 * 9 ** 3


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

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

for i in range(len(N)):
    x = int(N[i])  
    for j in range(K):
        
        dp[i+1][j+1][0] += dp[i][j][0]*9  
        dp[i+1][j][0] += dp[i][j][0]  
        
        if x > 0:
            dp[i+1][j][0] += dp[i][j][1]  
            dp[i+1][j+1][0] += dp[i][j][1]*(x-1)  
            dp[i+1][j+1][1] += dp[i][j][1]  
        else:
            
            dp[i+1][j][1] += dp[i][j][1]  
    dp[i+1][K][0] += dp[i][K][0]
    dp[i+1][K][not x>0] += dp[i][K][1]
print(sum(dp[len(N)][K]))

Solution (Python):


ar = input()

k = int(input())

l = len(ar)


DP = [[[-1] * 2 for j in range(103)] for i in range(102)]


def dp(i, j, fl):
    if i == l:
        if j == k:
            return 1
        else:
            return 0

    if DP[i][j][fl] != -1:
        return DP[i][j][fl]

    res = 0

   
    if fl:
        for p in range(10):

            res += dp(i+1, j + (p != 0) , fl == 1)
    else:
        ko = ord(ar[i]) - ord('0')
        for p in range(ko + 1):

            res += dp(i + 1, j + (p != 0), p < ko)
    DP[i][j][fl] = res
    return res

print(dp(0, 0, 0))

Solution (Python):

"""dp1,2[i][j] 
i桁で0をj個含む数で, 
dp1→ Nの上からi桁目までを抽出した数より小さい
dp2→ Nの上からi桁目までを抽出した数に等しい
"""

N = int(input())
K = int(input())
digit = len(str(N))
N_str = str(N)

dp1 = [[0]*4 for _ in range(digit+1)]
dp2 = [[0]*4 for _ in range(digit+1)]

dp2[0][0] = 1

for i in range(1, digit+1):
    for j in range(4):
        if int(N_str[i-1]) != 0:
            if j >= 1:
                dp2[i][j] = dp2[i-1][j-1]
                dp1[i][j] = dp1[i-1][j]+9*dp1[i-1][j-1]+dp2[i-1][j]+dp2[i-1][j-1]*(int(N_str[i-1])-1)
            else:
                dp1[i][j] = dp1[i-1][j]+dp2[i-1][j]
        else:
            dp2[i][j] = dp2[i-1][j]
            if j >= 1:
                dp1[i][j] = dp1[i-1][j]+9*dp1[i-1][j-1]
            else:
                dp1[i][j] = dp1[i-1][j]

        

ans = dp1[digit][K]+dp2[digit][K]

print(ans)

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

def f(n,k):
    l=[int(i) for i in str(n)]
    if n<100000:
        cnt=0
        for i in range(1,n+1):
            s=str(i)
            if len(s)-s.count('0')==k:
                cnt+=1
        return cnt
    else:
        if k==1:
            cnt=(len(l)-1)*9
            cnt+=l[0]
        elif k==2:
            cnt=(len(l)-1)*(len(l)-2)//2*9*9
            cnt+=(l[0]-1)*(len(l)-1)*9
            cnt+=f(n-10**(len(l)-1)*l[0],1)
        elif k==3:
            cnt=(len(l)-1)*(len(l)-2)*(len(l)-3)//6*9*9*9
            cnt+=(l[0]-1)*(len(l)-1)*(len(l)-2)//2*9*9
            cnt+=f(n-10**(len(l)-1)*l[0],2)
        return cnt
print(f(n,k))

Solution (Python):
N = [int(i) for i in str(input())]
m = len(N)
K = int(input())
dp = [[[0 for i in range(K + 1)],[0 for i in range(K + 1)]]   for i in range(m)]

dp[0][1][0] = 1
dp[0][0][1] = 1
dp[0][1][1] = N[0] - 1
for i in range(1,m):
    for t in range(0,min(i+2,K+1)):
        if N[i] != 0:
            if t == 0:
                dp[i][1][t] = dp[i-1][1][t]
            else:
                dp[i][0][t] = dp[i-1][0][t-1]
                dp[i][1][t] = dp[i-1][0][t] + dp[i-1][0][t-1] * (N[i]-1) + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
        else :
            if t == 0:
                dp[i][0][t] = dp[i-1][0][t]
                dp[i][1][t] = dp[i-1][1][t] 
            else :
                dp[i][0][t] = dp[i-1][0][t]
                dp[i][1][t] = dp[i-1][1][t] + dp[i-1][1][t-1] * 9
print(dp[-1][0][K]+dp[-1][1][K])