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



Sample input:
100
1


Sample output:
19

Submission status: Wrong Answer

Solution code:
import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

## コンビネーション計算（mod inv なし）
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
## ----------------


def ABC154E(n, k):
  ## n is string, k is int
  digit = len(n)
  higher = int(n[0])
  lower = n[1:]
  if digit < k:
    return 0
  elif k == 0:
    return 1
  elif digit == 1:
    return int(n)
  elif n == '9' * digit:
    return cmb(digit, k) * 9 ** k
  else:
    var0 = ABC154E('9' * (digit - 1), k)
    var1 = (higher - 1) * ABC154E('9' * (digit - 1), k - 1) if digit >= 2 else 0
    varn = ABC154E(lower, k - 1) if digit >= 1 else 0
    return var0 + var1 + varn


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

ans = ABC154E(N, K)
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

def combi(n, r):
  num = 1
  for i in range(1, r+1):
    num = num * (n - i + 1) // i
  return num

ans = 0

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

# 0(k non 0 digits)
ln = len(str(n))
ans += combi(ln-1, k) * 9**k

sn = str(n)
ntopd = int(sn[0])

if k == 1:
  ans += ntopd
elif k == 2:
  for topd in range(1, ntopd):
    if topd < ntopd:
      ans += 9 * (ln - 1)
    elif topd == ntopd:
      for i in range(1, ln):
        ans += int(sn[i])
elif k == 3:
  for topd in range(1, ntopd):
    if topd < ntopd:
      ans += 9 * 9 * combi(ln-1, 2)
    elif topd == ntopd:
      for i in range(1, ln-1):
        for j in range(i+1, ln):
          snid = int(sn[i])
          if snid != 0:
            ans += int(sn[j]) + (snid - 1) * 9
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
K = int(input())
ans = 0
keta = len(str(N))
a = list(str(N))
def comb(n, k):
	return math.factorial(n) / (math.factorial(k) * math.factorial(n - k))

# N - 1 桁で表現できるとき
if keta >= 2:
	for i in range(1, keta):
		# i 桁の中に、 i - K 個　0 を入れなければいけない
		if i < i - K: continue
		# i - K は正でなけれなばならない
		if i - K <= 0: continue 
		
		# 0 を入れる場所が (i) C (i - K) 箇所ある
		# あとは何が入っても大丈夫
		ans += comb(i, i - K) * (9 ** K)
		
	
# N 桁で表現するとき
# 上1桁の数字が最大値でないならば、もう何でもいい
for i in range(keta):
	need_zero = a[0 : i].count("0")
	if keta - (i + 1) < 0 or keta - K - need_zero < 0 or (keta - (i + 1)) - (keta - K - need_zero) < 0 : continue
	if i == 0:
		ans += (int(str(N)[i]) - 1) * comb(keta - (i + 1), keta - K - need_zero) * (9 ** (K - (i + 1)))
	else:
		print(keta - K - need_zero)
		ans += int(str(N)[i]) * comb(keta - (i + 1), keta - K - need_zero) * (9 ** (K - (i + 1)))
	print(ans)

	
print(ans)

Submission status: Wrong Answer

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

def k1(n_str):
	n_len = len(n_str)
	return 9*(n_len-1) + int(n_str[0])

def k2(n_str):
    s = 0
    n_len = len(n_str)
    if n_len < 2:
        return 0
    s += k2('9'*(n_len - 1))
    s += k1('9'*(n_len - 1)) * (int(n_str[0]) - 1)
    s += k1(n_str[1:])
    return s
                      
def k3(n_str):
    s = 0
    n_len = len(n_str)
    if n_len < 3:
        return 0
    s += k3('9'*(n_len - 1))
    s += k2('9'*(n_len - 1)) * (int(n_str[0]) - 1)
    s += k2(n_str[1:])
    return s

if k == 1:
    print(k1(n_str))
elif k == 2:
    print(k2(n_str))
elif k == 3:
    print(k3(n_str))

Submission status: Wrong Answer

Solution code:
import math

N=input().replace('\n','')
K=int(input().replace('\n',''))

def C(n,k):
    return (math.factorial(n)//math.factorial(n-k))//math.factorial(k)

def calc(n,k):
    if n<k or k<0:
        return 0
    return (9**k)*C(n,k)

s=0
l=len(N)
counter=0
for i,num in enumerate(N):
    if (K-counter)==0:
        s+=1
        break
    if int(num)==0:
        continue
    s+=(int(num)-1)*calc(l-i-1,K-counter-1)
    s+=calc(l-i-1,K-counter)
    counter+=1

print(s)

Submission status: Wrong Answer

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

mm1 = [0,0,0,0]
mm2 = [0,0,0,0]
mm3 = [1,0,0,0,0]

lgt = len(str(N))

for i in range(lgt):
    for j in range(3):
        mm1[j+1] = mm2[j]*9
        mm1[j] += mm2[j]
        mm1[0] = mm2[0]

    for k in range(10):
        mm = list(str(N))
        if k < int(mm[i]) and k != 0:
            mm1[3] += mm3[2]
            mm1[2] += mm3[1]
            mm1[1] += mm3[0]
        elif k < int(mm[i]) and k == 0:
            mm1[3] += mm3[3]
            mm1[2] += mm3[2]
            mm1[1] += mm3[1]
            mm1[0] += mm3[0]
        elif k==int(mm[i]) and k!=0:
            for l in range(4):
                if mm3[l] == 1:
                    mm3[l+1] = 1
                    mm3[l] = 0 
                    break
    # print(mm1,mm3)
    mm2 = mm1.copy()

print(mm2[K]+mm3[K])

Submission status: Wrong Answer

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

mm1 = [0,0,0,0]
mm2 = [0,0,0,0]
mm3 = [1,0,0,0,0]

lgt = len(str(N))

for i in range(lgt):
    for j in range(3):
        mm1[j+1] = mm2[j]*9
        mm1[j] += mm2[j]
        mm1[0] = mm2[0]

    for k in range(10):
        mm = list(str(N))
        if k < int(mm[i]) and k != 0:
            mm1[3] += mm3[2]
            mm1[2] += mm3[1]
            mm1[1] += mm3[0]
        elif k < int(mm[i]) and k == 0:
            mm1[3] += mm3[3]
            mm1[2] += mm3[2]
            mm1[1] += mm3[1]
            mm1[0] += mm3[0]
        elif k==int(mm[i]) and k!=0:
            for l in range(4):
                if mm3[l] == 1:
                    mm3[l+1] = 1
                    mm3[l] = 0 
                    break
    print(mm1,mm3)
    mm2 = mm1.copy()

print(mm2[K]+mm3[K])

Submission status: Wrong Answer

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

mm1 = [0,0,0,0]
mm2 = [0,0,0,0]
mm3 = [1,0,0,0,0]

lgt = len(str(N))

for i in range(1,lgt):
    for j in range(3):
        mm1[j+1] = mm2[j]*9
        mm1[j] += mm2[j]
        mm1[0] = mm2[0]

    for k in range(10):
        mm = list(str(N))
        if k < int(mm[i]) and k != 0:
            mm1[3] += mm3[2]
            mm1[2] += mm3[1]
            mm1[1] += mm3[0]
        elif k < int(mm[i]) and k == 0:
            mm1[3] += mm3[3]
            mm1[2] += mm3[2]
            mm1[1] += mm3[1]
            mm1[0] += mm3[0]
        elif k==int(mm[i]) and k!=0:
            for l in range(4):
                if mm3[l] == 1:
                    mm3[l+1] = 1
                    mm3[l] = 0 
                    break
    # print(mm1,mm3)
    mm2 = mm1.copy()

print(mm2[K]+mm3[K])

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
dp0 = [0] * 4
dp1 = [1,0,0,0]
for i in n:
  i = int(i)
  pdp0,pdp1,dp0 = dp0,dp1,[0]*4
  if i != 0:
    dp1 = [0] + pdp1[:-1]
  else:
    dp1 = pdp1
  dp0[0] = pdp0[0]+(i!=0)*pdp1[0]
  for j in range(1,4):
    dp0[j] = 9*pdp0[j-1] + pdp0[j] + (i-1)*pdp1[j-1] + (i!=0)*pdp1[j]
print(dp0[k]+dp1[k])

Submission status: Wrong Answer

Solution code:
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 0
    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))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#main

@lru_cache(maxsize=None)#メモ化デコレータ
def f(num,k):
    if(num==0 and k==0):return 1
    elif(num<=0 or k<=0):return 0
    else:
        r=num-(num//10)*10
        m=num//10
        return f(m,k-1)*r+f(m-1,k-1)*(10-r)+f(m,k)
s=int(input())
k=int(input())
print(f(s,k))

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
L = len(str(N))
dp1 = [[0 for _ in range(K+1)] for _ in range(L+1)]
dp2 = [[0 for _ in range(K+1)] for _ in range(L+1)]
count = 0
for i in range(L+1):
    dp1[i][0] = 0
count = 0
for i, c in enumerate(str(N)):
    c = int(c)

    for j in range(0, K+1):
        if i == 0 and j == 0:
            dp1[i+1][j] = 1
        else:
            dp1[i+1][j] += dp1[i][j]
            dp2[i+1][j] += dp2[i][j]

        if j != K:
            if i == 0 and j == 0:
                dp1[i+1][j+1] = c-1
                dp2[i+1][j+1] = 1
            if count >= K:
                dp1[i+1][j+1] += dp2[i][j] * 9
                dp1[i+1][j+1] += dp1[i][j] * 9
            else:
                dp2[i+1][j+1] += dp2[i][j]
                dp1[i+1][j+1] += dp2[i][j]*(c-1)
                dp1[i+1][j+1] += dp1[i][j]*9

    if c != 0:
        count += 1
    #print(dp1)
    #print(dp2)
print(dp1[-1][-1] + dp2[-1][-1])

Submission status: Wrong Answer

Solution code:
def comb(a, b):
    ans = 1
    for i in range(b):
        ans *= (a - i)
    for i in range(1, 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, 3) * 9 ** 3 + solve_k2(int(N[1:]))
    return ans

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

Submission status: Wrong Answer

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    n=0
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    n=0
    for i in range(1,d-1):
      if int(str(N)[i])!=0 and i==d-2:
        n=(int(str(N)[i])-1)*9+int(str(N)[i+1])
        break
      elif int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

Submission status: Wrong Answer

Solution code:

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):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

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

digit = list(map(int, str(N)))
M = len(digit)

C = 0
if M >= K:
    for i in range(K):
        if digit[i] > 0:
            C += count(digit[i], M-i, K-i)

print(C)

Submission status: Wrong Answer

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    n=0
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  elif d==3 and int(str(N)[1])!=0:
    print((int(str(N)[1])-1)*9+int(str(N)[2]))
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    n=0
    for i in range(1,d-1):
      #if int(str(N)[i])!=0 and i==d-2:
        #n=(int(str(N)[i])-1)*9+int(str(N)[i+1]
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

Submission status: Wrong Answer

Solution code:

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):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

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

digit = list(map(int, str(N)))
M = len(digit)

C = 0
if M >= K:
    for i in range(K):
        C += count(digit[i], M-i, K-i)

print(C)

Submission status: Wrong Answer

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    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']

  # print(a)
  # print(c)
  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 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 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 len(a) == 1:
              res += (c[-1] - 1) * 9 * 9


  return res


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


main()

Submission status: Wrong Answer

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    n=0
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    n=0
    for i in range(1,d-1):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i])-1)*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

Submission status: Wrong Answer

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    n=0
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    n=0
    for i in range(1,d-1):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

Submission status: Wrong Answer

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
      n=0
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
      n=0
    print(int(l+m+n))

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
K=int(input())
d = len(str(N)) #桁数

#nCr組み合わせ
def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if K>d:
    print(0)
elif d==1:
    print(N)
elif N<9999:
    answer=0
    for i in range(N+1):
        if (d- str(i).zfill(d).count('0'))==K:
            answer+=1
    print(answer)
else:
    max_d_val= int(str(N)[-d])
    max_d_val_2= int(str(N)[-(d-1)])
    max_d_val_3 = int(str(N)[-(d-2)])
    if K==1:
        answer = combinations_count(d,K)*(9**K)- combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        print(answer)
    if K==2:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        answer=mother - f1-f2
        print(answer)
    if K==3:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        f3 = combinations_count(d-3,K-3)*(9**(K-3))*(9-max_d_val_3)
        answer= mother - f1-f2-f3
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
K=int(input())
d = len(str(N)) #桁数

#nCr組み合わせ
def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if K>d:
    print(0)
elif d==1:
    print(N)
elif N<9999:
    answer=0
    for i in range(N):
        if (d- str(i).zfill(d).count('0'))==K:
            answer+=1
    print(answer)
else:
    max_d_val= int(str(N)[-d])
    max_d_val_2= int(str(N)[-(d-1)])
    max_d_val_3 = int(str(N)[-(d-2)])
    if K==1:
        answer = combinations_count(d,K)*(9**K)- combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        print(answer)
    if K==2:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        answer=mother - f1-f2
        print(answer)
    if K==3:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        f3 = combinations_count(d-3,K-3)*(9**(K-3))*(9-max_d_val_3)
        answer= mother - f1-f2-f3
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
K=int(input())
d = len(str(N)) #桁数

#nCr組み合わせ
def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if N<9999:
    answer=0
    for i in range(N):
        if (d- str(i).zfill(d).count('0'))==K:
            answer+=1
    print(answer)
else:
    max_d_val= int(str(N)[-d])
    max_d_val_2= int(str(N)[-(d-1)])
    max_d_val_3 = int(str(N)[-(d-2)])
    if K==1:
        answer = combinations_count(d,K)*(9**K)- combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        print(answer)
    if K==2:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        answer=mother - f1-f2
        print(answer)
    if K==3:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        f3 = combinations_count(d-3,K-3)*(9**(K-3))*(9-max_d_val_3)
        answer= mother - f1-f2-f3
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
K=int(input())
d = len(str(N)) #桁数

#nCr組み合わせ
def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if N<9999:
    answer=0
    for i in range(N):
        if (d- str(i).zfill(d).count('0'))==K:
            answer+=1
    print(answer)
elif d > K:
    max_d_val= int(str(N)[-d])
    max_d_val_2= int(str(N)[-(d-1)])
    max_d_val_3 = int(str(N)[-(d-2)])
    if K==1:
        answer = combinations_count(d,K)*(9**K)- combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        print(answer)
    if K==2:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        answer=mother - f1-f2
        print(answer)
    if K==3:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        f3 = combinations_count(d-3,K-3)*(9**(K-3))*(9-max_d_val_3)
        answer= mother - f1-f2-f3
        print(answer)

#else: #d=Kのとき
    if K==2:
        print(N-(9+N//10))
    if K==3:
        answer=0
        for i in range(N):
            if str(i).count('0')==0:
                answer+=1
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
K=int(input())
d = len(str(N)) #桁数

#nCr組み合わせ
def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if K>d:
    print(0)
elif d==1:
    print(N)
elif d > K:
    max_d_val= int(str(N)[-d])
    max_d_val_2= int(str(N)[-(d-1)])
    max_d_val_3 = int(str(N)[-(d-2)])
    if K==1:
        answer = combinations_count(d,K)*(9**K)- combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        print(answer)
    if K==2:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        answer=mother - f1-f2
        print(answer)
    if K==3:
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2))*(9-max_d_val_2)
        f3 = combinations_count(d-3,K-3)*(9**(K-3))*(9-max_d_val_3)
        answer= mother - f1-f2-f3
        print(answer)
else: #d=Kのとき
    if K==2:
        print(N-(9+N//10))
    if K==3:
        answer=0
        for i in range(N):
            if str(i).count('0')==0:
                answer+=1
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

N=int(input())
K=int(input())
d = len(str(N)) #桁数

#nCr組み合わせ
def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if K>d:
    print(0)
elif d==1:
    print(N)
elif d > K:
    max_d_val= int(str(N)[-d])
    max_d_val_2= int(str(N)[-(d-1)])
    i2=0
    i3=0
    if K==1:
        answer = combinations_count(d,K)*(9**K)- combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        print(answer)
    if K==2:
        max_d_val_3 = int(str(N)[-(d-2)])
        if max_d_val_2==0:
            i2=1
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2)+i2)*(9-max_d_val_2)
        answer=mother - f1-f2
        print(answer)
    if K==3:
        max_d_val_3 = int(str(N)[-(d-2)])
        max_d_val_4 = int(str(N)[-(d-3)])
        if max_d_val_2==0:
            i2=1
        if max_d_val_3==0:
            i3=1
        mother = combinations_count(d,K)*(9**K)
        f1 = combinations_count(d-1,K-1)*(9**(K-1))*(9-max_d_val)
        f2 = combinations_count(d-2,K-2)*(9**(K-2)+i2)*(9-max_d_val_2)
        f3 = combinations_count(d-3,K-3)*(9**(K-3)+i3)*(9-max_d_val_3)
        answer= mother - f1-f2-f3
        print(answer)
#else: #d=Kのとき

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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):
    # print(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)

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


#main
if __name__ == '__main__':
    solve()