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:
n=int(input())
lenn=len(str(n))

k=int(input())
#k:1~3

result=0

if n <=9:
    if k==1:
        print(n)
    else:
        print(0)
    exit()
elif n <=99:
    if k==1:
        print(n//10+9)
    elif k==2:
        print((n//10-1)*9+n%10)
    else:
        print(0)
    exit()
    """
elif n <=999:
    if k==1:
        print(n//100+9+9)
    elif k==2:
        print((n//100-1)*9+9*9)
    else:
        print(0)
    exit()
    """
else:
    if k==1:
        print(9*(lenn-1)+n//(10**(lenn-1)))
    elif k==2:
        result=0
        #先頭の文字を抜いた状態で
        result+=9*9*(lenn-1)*(lenn-2)//1//2
        #print(result)
        #先頭の文字を1ひいて
        result+=(n//(10**(lenn-1))-1)*9*(lenn-1)
        #print(result)

        for i in str(n)[1:]:
            result+=int(i)
        print(result)
    else:
        if lenn==3:
            result=(n//(10**(lenn-1))-1)*9*9
            temp=1
            for i in str(n)[1:]:
                temp=temp*int(i)
            result+=temp
            print(result)
            exit()
        else:
            result=0
            #先頭の文字を抜いた状態で
            result+=9*9*9*(lenn-1)*(lenn-2)*(lenn-3)//1//2//3
        #先頭の文字を1ひいて
            result+=(n//(10**(lenn-1))-1)*9*9*(lenn-1)*(lenn-2)
            temp=1
            i=1
            while i<lenn:
                j=i+1
                while j<lenn:
                    result+=int(str(n)[i])*int(str(n)[j])
                    j+=1
                i+=1

            print(result)

Submission status: Wrong Answer

Solution code:
from math import factorial

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

strN = str(N)
keta = len(strN)
top = int(strN[0])

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

res = 9**K*nCr((keta-1), K)

if K == 1:
    res += top

else:
    res += (top-1)*9**(K-1)*nCr((keta-1), K-1)

    if K == 2:
        for i in range(1, keta):
            if int(strN[i]) == 0:
                continue
            res += int(strN[i])
            res += 9*(keta-i-1)
            break

    else:
        flag = True
        for i in range(1, keta):
            if int(strN[i]) == 0:
                continue
            for j in range(i+1, keta):
                if int(strN[j]) == 0:
                    continue
                res += int(strN[i]) * int(strN[j])
                res += int(strN[i]) * 9 *(keta-j-1)
                break
            else:
                flag = False
            
            if flag:
                res += 9**(K-1)*nCr((keta-i-1), K-1)
            break

print(res)

Submission status: Wrong Answer

Solution code:

def solve(n,k):
    l = len(n)
    ans = 0
    # n-1桁からKこ取る
    tmp = 1
    for i in range(1, k+1):
        tmp = tmp*9*(l-i)
    for i in range(1, k+1):
        tmp = tmp // i
    ans += tmp

    # 最上位から1つ（最上位の数以外）とる。
    tmp = n[0]-1
    for i in range(1, k):
        tmp = tmp*9*(l-i)
    for i in range(1, k):
        tmp = tmp // i
    ans += tmp

    # 最上位からその数をとる。
    tmp = 0
    if k == 3:
        tmp += solve(n[1:],k-1)

    elif k == 2:
        for i in range(1, l):
            if n[i] != 0:
                tmp += n[i] + 9*(l-i-1)
                break
    else:
        tmp += 1
    ans += tmp
    return ans

n = list(map(int, input()))
k = int(input())

print(solve(n,k))

Submission status: Wrong Answer

Solution code:
N_str = input().strip()
L = len(N_str)
N_list = list(map(int, N_str))
N = int(N_str)
K = int(input())

def count1(s):
	total = 0
	for i in range(s, L):
		if i == s:
			total += N_list[i]
		else:
			total += 9
	return total

def count2(s):
	total = 0
	for i in range(s, L - 1):
		if N_list[i] > 0:
			if i == s:
				total += (N_list[i] - 1) * (L - i - 1) * 9
				total += count1(i + 1)
			else:
				total += 81 * (L - i - 1)
	return total

if K == 1:
	total = count1(0)
elif K == 2:
	total = count2(0)
else:
	total = 0
	for i in range(0, L - 2):
		if N_list[i] > 0:
			if i == 0:
				total += (N_list[i] - 1) * (L - i - 1) * 9 * (L - i - 2) * 9 // 2
				total += count2(i + 1)
			else:
				total += 729 * (L - i - 1) * (L - i - 2) // 2

print(total)

Submission status: Wrong Answer

Solution code:
from math import ceil


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

print([x for x in range(pow(10, K - 1), N + 1) if len(str(ceil(x)).replace('0', '')) == K])

Submission status: Wrong Answer

Solution code:
#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

#選び方（コンビネーション nCr）
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n_given = input_one_number()
k_given = input_one_number()

ans = 0
ndigits = len(str(n_given))
if k_given == 1:
    msd = n_given
    while msd >= 10:
        msd //=10

    ans = (ndigits-1)*9+msd

elif k_given == 2:
    if ndigits < 2:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 100:
            msd1 //=10
        msd2 = msd1%10
        msd1 = msd1//10

        if(ndigits > 2):
            ans += cmb(ndigits-1,2)*pow(9,2)
        ans += (msd1-1)*(ndigits-1)*9
        ans += (ndigits-2)*9+msd2

else:
    if ndigits < 3:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 1000:
            msd1 //=10
        msd3 = msd1%10
        msd1 = msd1//10
        msd2 = msd1%10
        msd1 = msd1//10
        
        if(ndigits > 3):
            ans += cmb(ndigits-1,3)*pow(9,3)
        if(ndigits > 3):
            ans += cmb(ndigits-2,2)*pow(9,2)*(msd1)
        if(ndigits > 3):
            ans += (ndigits-3)*msd1*msd2*9
        ans += msd1 * msd2 *msd3

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
def cmb(n,r):
    if n<0 or r<0:
        return 0
    else:
        return int(factorial(n) / factorial(r) / factorial(n - r))

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

def zero(n,k,l):
    saidai=n//(10**(l-1))
    small=n-10**(l-1)*saidai
    if l<k:
        return 0
    elif k==0:
        return 1
    elif l==1:
        return n
    elif l==k:
        return (cmb(l-1,k-1)*9**(k-1)*(saidai-1)+zero(small,k-1,l-1))
    else:
        ans = cmb(l-1,k)*9**k+cmb(l-1,k-1)*9**(k-1)*(saidai-1)+zero(small,k-1,l-1)
        return ans

print(zero(n,k,l))

Submission status: Wrong Answer

Solution code:
import sys
n=list(input())
N=len(n)
k=int(input())
x=int(n[0])
if N<k:
  print(0)
  sys.exit()

def s1(m):
  N=len(m)
  x=int(m[0])
  ans=0
  ans+=(N-1)*9
  ans+=x
  return ans

def s2(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s2(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=(N-1)*(N-2)*81//2
    ans+=(x-1)*(N-1)*9
    m2=m[1:N+1]
    ans+=s1(m2)
    return ans
  
def s3(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s3(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=(N-1)*(N-2)*(N-3)*729//6
    ans+=(x-1)*(N-1)*(N-2)*81//2
    m2=m[1:N+1]
    ans+=s2(m2)
    return ans

if k==1:
  print(s1(n))
  sys.exit()

if k==2:
  print(s2(n))
  sys.exit()

if k==3:
  print(s3(n))
  sys.exit()

Submission status: Wrong Answer

Solution code:
def cmb(a,b):
    if b == 0 :
        ans=1
    else:
        Nu = 1
        Di = 1
        for i in range(b):
            Nu = Nu*(a-i)
            Di = Di*(b-i)
        ans = Nu/Di
    return ans


def f(a,keta,K):
    ans = cmb(keta,K)*9**K
    if K == 1:
        ans += a
    else:
        ans += cmb(keta, K-1)*9**(K-1)*(a-1)
    return ans



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

    ans = 0
    while K>0 and N>0:
        keta = len(str(N))-1
        if keta == 0:
            if K==1 :ans += N
        a = int(N/(10**(keta)))
        ans += f(a,keta,K)
        N -= a*10**keta
        K -= 1
        print(a,keta,ans)
    print(int(ans))
    return

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def f2(n):
    c = len(n)-1
    nn = n[1:]
    s = c*(c-1)//2 * 9*9 
    s += c * (int(n[0])-1)*9
    s += (len(nn)-1)*9 + int(nn[0])
    return s

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

if k == 1:
    print((len(n)-1)*9 + int(n[0]))
if k == 2:
    if len(n) >= 2:
        print(f2(n))
    else:
        print(0)
        
if k == 3:
    if len(n) >= 3:
        c = len(n)-1
        nn = n[1:]
        s = c*(c-1)*(c-2)//(3*2) * 9*9*9
        s += (int(n[0])-1) * c*(c-1)//2 * 9*9 
        s += f2(nn)
        print(s)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
su = 0
m = int(input())
numOfZeros = int(input())
for i in range(1,m +1):
  if str(i).count("0") == numOfZeros:
    su+= 1
    
print(su)

Submission status: Wrong Answer

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

# 桁数調べる
# tmp = N
# digit = 1
# while tmp >= 10:
#     tmp //= 10
#     digit += 1
# print(digit)

if K > len(str(N)):
    print(0)
    exit()

if K == 1:  # done
    N = str(N)
    ans = (len(N)-1) * 9
    ans += int(N[0])
    print(ans)

elif K == 2:
    N = str(N)
    # 最上位を避けた, (n-1)C2 * 9の二乗
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位の桁2つのみ, 最上位がN[0]のパターン, N[0]の1通りと, N[1]通り
    ans += 1 * int(N[1])
    # 最上位の桁2つののみ, 最上位!=N[0]のパターン
    ans += (int(N[0])-1) * 9
    # 最上位とその他(二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    # 最上位を避けた選び方, n-1C3 * 9の三乗
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他, 最上位がN[0]の場合
    ans += 1 * int(N[1]) * (len(N)-2) * 9
    # 上位二桁とその他, 最上位!=N[0]の場合, int(N[0])-1なのはN[0]のパターンを除くため
    ans += (int(N[0])-1) * 9 * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
ans = 0
while N!=0:
    n = str(N)
    if len(n)<K:break

    if n[1:].count("9")==len(n)-1:
        if K==1:ans+=int(n[0])
        elif K==2:
            for i in range(1,len(n)):
                ans+=int(n[0])*9
        else:
            for i in range(1,len(n)-1):
                for j in range(i+1,len(n)):
                    ans+=int(n[0])*9*9
    else:
        if K==1:ans+=1
        elif K==2:
            for i in range(1,len(n)):
                if i==1:
                    ans += int(n[i])
                else:
                    ans+=9
        else:
            for i in range(1,len(n)-1):
                for j in range(2,len(n)):
                    ans += int(n[i])*9
    if len(n)==1:N = 0
    elif n[1:].count("9")==len(n)-1:N = 10**(len(n)-1)-1
    else:N = int(n[0])*(10**(len(n)-1))-1
print(ans)

Submission status: Wrong Answer

Solution code:
N=input()
K=input()
a=1
a1=1
c=0
ans=0
while (a<=int(N)):
  a1=a
  while not(c==(len(str(N))-1)):
    a1=str(a1).rstrip("0")
  L=len(str(a1))
  a=int(a)+1
  if(int(L)==int(K)):
    ans=ans+1
print(ans)
print(len(str(N))-1)

Submission status: Wrong Answer

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

l = len(str(N))
a = N // 10**(l - 1)

if K == 1:
    ans = 9 * (l - 1) + a
    print(ans)
elif K == 2:
    b = N // 10**(l - 2)
    d = b - 10 * a
    if l == 1:
        print(0)
    else:
        ans = 81 * (l - 1) * (l - 2) // 2
        ans += (a - 1) * 9 * (l - 1) + 9 * (l - 2) + d
        print(ans)
elif K == 3:
    b = N // 10**(l - 2)
    c = N // 10**(l - 3)
    d = b - 10 * a
    e = c - 100 * a - 10 * d
    if l == 1 or l == 2:
        print(0)
    else:
        ans = 729 * (l - 1) * (l - 2) * (l - 3) // 6
        ans += (a - 1) * 81 * (l - 1) * (l - 2) // 2
        if d != 0:
            ans += 81 * (l - 2) * (l - 3) // 2
            ans += (d - 1) * 9 * (l - 2)
            ans += (l - 3) * 9 + e
        elif e != 0:
            ans += 81 * (l - 3) * (l - 4) // 2
            ans += e * 9 * (l - 3) 
        else:
            ans += 81 * (l - 3) * (l - 4) // 2
        print(ans)

Submission status: Wrong Answer

Solution code:
N_str = input().strip()
L = len(N_str)
N_list = list(map(int, N_str))
N = int(N_str)
K = int(input())

def count1(s):
	total = 0
	for i in range(s, L):
		if i == s:
			total += N_list[i]
		else:
			total += 9
	return total

def count2(s):
	total = 0
	for i in range(s, L - 1):
		if i == s:
			if N_list[i] > 0:
				total += (N_list[i] - 1) * (L - i - 1) * 9
				total += count1(i + 1)
		else:
			total += 81 * (L - i - 1)
	return total

if K == 1:
	total = count1(0)
elif K == 2:
	total = count2(0)
else:
	total = 0
	for i in range(0, L - 2):
		if i == 0:
			if N_list[i] > 0:
				total += (N_list[i] - 1) * (L - i - 1) * 9 * (L - i - 2) * 9 // 2
				total += count2(i + 1)
		else:
			total += 729 * (L - i - 1) * (L - i - 2) // 2

print(total)

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
import math
def k1(n):
    if n < 10:
        ans = n
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = 9 * (len(n1) - 1) + n2
    return ans

def k2(n):
    if n < 100:
        ans = n - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (81 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 3)) / 2) +  (n2 - 1) * k1(10 ** (len(n1) - 1) - 1) + k1(n - n2 * 10 ** (len(n1) - 1))
    return ans
def k3(n):
    if n < 1000:
        ans = n - k2(n) - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (729 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 4)) / 6) + (n2 - 1) * k2(10 ** (len(n1) - 1) - 1) + k2(n - n2 * 10 ** (len(n1) - 1))
    return ans

if k == 1:
    print(k1(n))
elif k == 2:
    print(k2(n))
else:
    print(k3(n))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
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 cnt(i):
  c = 0
  for l in str(i):
    if l != "0":
      c += 1
  return c
if n < 1000:
  q = 0
  for i in range(1,n+1):
    if cnt(i) == k:
      q += 1
  print(q)
  quit()
if k == 1:
  print(9*(len(str(n))-1)+int(str(n)[0]))
if k == 2:
  ans = 0
  top = int(str(n)[0])
  if top > 1:
    ans += (top-1)*(9*(len(str(n))-1))
  ans += cmb(len(str(n))-1,2)*81
  n = n - top*10**(len(str(n))-1)
  if n <1000:
    q = 0
    for i in range(1,n+1):
      if cnt(i) == 1:
        q += 1
    ans += q
  else:
    ans += 9*(len(str(n))-1)+int(str(n)[0])
  print(ans)
  quit()

#k==3
ans = 0
top = int(str(n)[0])
if top > 1:
  ans += (top-1)*cmb(len(str(n))-1,2)*81
ans += cmb(len(str(n))-1,3)*729
n = n - top*10**(len(str(n))-1)
if n < 1000:
  q = 0
  for i in range(1,n+1):
    if cnt(i) == 2:
      q += 1
  ans += q
  print(ans)
  quit()
top = int(str(n)[0])
if top > 1:
  ans += (top-1)*(9*(len(str(n))-1))
ans += cmb(len(str(n))-1,2)*81
n = n - top*10**(len(str(n))-1)
if n < 1000:
  q = 0
  for i in range(1,n+1):
    if cnt(i) == 1:
      q += 1
  ans += q
  print(ans)
  quit()
ans += 9*(len(str(n))-1)+int(str(n)[0])
print(ans)

Submission status: Wrong Answer

Solution code:
n=list(map(int,input()))
l=len(n)
k=int(input())
#print(n)
ans=0
if k==1:
	#最上位に0でない数字
	ans=n[0]+9*(l-1)
elif k==2:
	if k<=l: #lは2以上
		#最上位にn[0]次に0以外
		ans+=n[1]
		#最上位にn[0]次に0
		ans+=9*(l-2)
		#最上位にn[0]以外
		ans+=(n[0]-1)*9*(l-1)
		#最上位は0
		ans+=81*(l-1)*(l-2)//2
elif k==3:
	if k<=l: #lは3以上
		#最上位にn[0]次にn[1]
		ans+=n[2]+9*(l-3)
		#最上位にn[0]次にn[1]以外
		ans+=(n[1]-1)*9*(l-2)
		#最上位にn[0]次に0
		ans+=81*(l-2)*(l-3)//2
		#最上位にn[0]以外
		ans+=(n[0]-1)*81*(l-1)*(l-2)//2
		#最上位はなし
		ans+=729*(l-1)*(l-2)*(l-3)//6
print(ans)

Submission status: Wrong Answer

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

def nCmMOD(A,B,Mod):
    #a conb b を　Mod で割った余り
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

L=len(str(N))
ans=0
if L-1>=K:
    ans=nCmMOD(L-1,K,10**9+7)*(9**K)
#print(ans)

List=[]
for i in range(1,10):
    List.append(i*10**(L-1))
#print(List)

import sys
if K==1:
    for i in List:
        if i<=N:
            ans+=1
        else:
            print(ans)
            sys.exit()
    print(ans)
if K==2:
    for i in List:
        for j in range(L-1):
            for k in range(1,10):
                T=i+k*10**j
                if T<=N:
                    ans+=1
                else:
                    print(ans)
                    sys.exit()
    print(ans)
elif K==3:
    List3=[]
    for i in List:
        for j in range(L-1):
            for k in range(j+1,L-1):
                if i+9*10**j+9*10**k<=N:
                    ans+=81
                else:
                    for l in range(1,10):
                        for m in range(1,10):
                            T=i+m*10**j+l*10**k
                            if T<=N:
                                ans+=1
                            else:
                                print(ans)
                                sys.exit()
    print(ans)

Submission status: Wrong Answer

Solution code:
n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())

#割り算のやーつ
MOD = 1000000007

# 二項係数関連.
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0
if(n_digit < k):
    # 満たす物は無い.
    print(0)
else:
    # 最大桁数-1の桁の数について.
    if(n_digit > k):
        # 何が入っても問題ないので、3箇所選んで1-9をそれぞれ選ぶ.
        ans += com.calc_COM(n_digit-1, k) * (9 ** k)
    # 最大桁の桁の数について.
    n_top = int(n_str[0])
    if(k-1 <= 0):
        # これで終わりだから自由
        ans += n_top
    else:
        # 最大桁がn_top未満なら残りは自由
        ans += com.calc_COM(n_digit-1, k-1) * (9 ** (k-1)) * (n_top - 1)
        # 最大桁がn_topなら、残りは自由じゃない……
        n_sec = 0
        count = n_digit - 1
        i = 1
        for nc in n_str[1:]:
            i += 1
            n_sec = int(nc)
            if(n_sec > 0):
                break
            count -= 1
        if(count >= k-1):
            # まだ可能性がある！
            # 次に来る1以上の数字がcountよりも先だったら二つとも自由
            ans += com.calc_COM(count-1, k-1) * (9 ** (k-1))
            # 次の1以上の数字がcountの位置に来る.
            if(k-2 <= 0):
                ans += n_sec # これで終わりだからその下は考えないでいいのじゃ.
            else:
                # 次に来る1以上の数字がn_sec未満なら残りは自由
                ans += (count-1) * 9 * (n_sec - 1)
                # 次に来る1以上の数字がn_secと同じなら、残りは自由じゃない……
                sec_count = count - 1
                n_third = 0
                for nc in n_str[i:]:
                    n_third = int(nc)
                    if(n_sec > 0):
                        break
                    sec_count -= 1
                if(sec_count >= k-2):
                    # まだ可能性がある！
                    # 最後の数字がsec_countよりも下の位置
                    ans += (sec_count-1) * 9
                    # 最後の数字がsec_countの位置
                    ans += n_third

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()
S = str(N)

def calc1(S):
    flag = False
    ans = 0
    for s in S:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    return ans

def calc2(S):
    bl = len(S)
    ans = 0
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    if int(S[0])>=1 and bl>=2:
        ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    if bl>=2:
        if bl==2 and S[0]=='0':
            pass
        else:
            ans += calc1(S[1:])
    return ans

def calc3(S):
    bl = len(S)
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=3:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    if bl>=3:
        if bl==3 and S[0]=='0':
            pass
        else:
            ans += calc2(S[1:])
    return ans

if K==1:
    print(calc1(S))
if K==2:
    print(calc2(S))
if K==3:
    print(calc3(S))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys


def count(n):
    c = 0
    for s in str(n):
        if s != "0":
            c += 1
    return c


@lru_cache()
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)


def C(i, j):
    return fact(i) // (fact(j) * fact(i - j))


def calc(N, K):
    if K<0:
        return 0
    if N < 10000:
        retval = 0
        for i in range(N + 1):
            if count(i) == K:
                retval += 1
        return retval

    keta = len(str(N))
    retval = C(keta - 1, K) * (9**K)
    retval += int(str(N)[0])*(calc(int(str(N)[1:]),K-1))
    return retval



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

print(calc(N,K))

Submission status: Wrong Answer

Solution code:
from math import factorial

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

strN = str(N)
keta = len(strN)
top = int(strN[0])

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

res = 9**K*nCr((keta-1), K)

if K == 1:
    res += top

else:
    res += (top-1)*9**(K-1)*nCr((keta-1), K-1)

    if K == 2:
        for i in range(1, keta):
            if int(strN[i]) == 0:
                continue
            res += int(strN[i])
            res += 9*(keta-i-1)
            break

    else:
        for i in range(1, keta):
            if int(strN[i]) == 0:
                continue
            for j in range(i+1, keta):
                if int(strN[j]) == 0:
                    continue
                res += int(strN[i]) * int(strN[j])
                res += int(strN[i]) * 9 *(keta-j-1)
                break
            
            res += 9**(K-1)*nCr((keta-i-1), K-1)
            break

print(res)

Submission status: Wrong Answer

Solution code:
def cmb(a,b):
    if b == 0 :
        ans=1
    else:
        Nu = 1
        Di = 1
        for i in range(b):
            Nu = Nu*(a-i)
            Di = Di*(b-i)
        ans = Nu/Di
    return ans


def f(a,keta,K):
    ans = cmb(keta,K)*9**K
    if K == 1:
        ans += a
    else:
        ans += cmb(keta, K-1)*9**(K-1)*(a-1)
    return ans



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

    ans = 0
    while K>0 and N>0:
        keta = len(str(N))-1
        a = int(N/(10**(keta)))
        ans += f(a,keta,K)
        N -= a*10**keta
        K -= 1
        print(a,keta,ans)
    print(int(ans))
    return

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = input()
K = int(input())
len_n = len(n)
ans = 0
#自由な数字を選んでいいのかどうか？、今使った0以外、今の桁数
def calc(free, count, now):
    global ans
    if count == K:
        ans += 1
        return
    if now == len_n:
        return 
    if free:
        for _ in range(9):
            calc(free, count + 1, now+1)
        #この数字を0にするとき
        calc(free, count, now+1)
    else:
        #自由に数字選べない時
        if int(n[now]) >= 1:
            for _ in range(int(n[now])-1):
                calc(not free, count + 1, now+1)
            #この数字を元の数字と同じ
            calc(free, count+1, now+1)
        #このすうじを0にする
        calc(not free, count, now+1)
calc(False, 0,0)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k = get_all_int()

# m桁の数値でf(n)=kとなる数の個数
# dp[k][m]
dp = [ [None]*101 for _ in range(4)]

for i in range(101):
    dp[0][i] = 1
dp[0][0] = 0
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0
dp[1][1] = 9
dp[2][1] = 0
dp[3][1] = 0

dp[1][2] = 1 * dp[1][1] + 9 * dp[0][1]
for i in range(2,101):
    dp[1][i] = 1 * dp[1][i-1] + 9 * dp[0][i-1]
    dp[2][i] = 1 * dp[2][i-1] + 9 * dp[1][i-1]
    dp[3][i] = 1 * dp[3][i-1] + 9 * dp[2][i-1]

# log(dp[1])
# log(dp[2])

ans = 0

keta = 0
x = n
while x > 0:
    keta += 1
    x //= 10

def sol(n, keta, k):
    if k == 0:
        return 1
    if k < 0:
        return 0
    if keta < k:
        return 0
    if keta == 0:
        return 1
    
    top = n//10**(keta-1)%10
    ans = 0
    # 0のとき
    ans += 1 * (0 if keta==1 else dp[k][keta-1])
    # log(keta,top,k,ans)

    # 1～top-1のとき
    ans += (top-1) * (1 if keta==1 else dp[k-1][keta-1])
    # log(keta,top,k,ans)

    # topのとき
    ans += sol(n, keta-1, k-1)
    # log(keta,top,k,ans)
    return ans

if keta < k:
    print(0)
    exit()
ans += sol(n, keta, k)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

answer=0

n=int(input())
k=int(input())
now=n
keta=0
alist=[]
while now!=0:
    amari=now%10
    now=now//10
    alist.append(amari)
    keta+=1
alist.reverse()
zlist=[]
for al in range(len(alist)):
    if alist[al]!=0:
        zlist.append([al, alist[al]])

if k>keta:
    print(0)
else:
    moto=10**(keta-1)
    first=n//moto
    if k>=2:
        second=(n-first*moto)//(moto//10)
        if k>=3:
            third=(n-first*moto-second*(moto//10))//(moto//100)
    #print(keta)
    #print(first, second)
    if keta-1>=k:
        answer+=cmb(keta-1, k)*(9**k)
    answer+=max(first-1, 0)*cmb(keta-1, k-1)*(9**(k-1))
    if k==1:
        answer+=1
    elif k==2:
        if keta-1>=k and second!=0:
            answer+=cmb(keta-2, k-1)*(9**(k-1))
        answer+=cmb(keta-2, k-2)*max(second-1, 0)*(9**(k-2))
        if second!=0:
            answer+=1
        else:
            swit=0
            kaz=0
            for zl in zlist:
                if zl[0]>=2 and swit==0:
                    swit=zl[0]
                    kaz=zl[1]
            answer+=(keta-swit-1)*9
            answer+=1
    else:
        if keta-1>=k and second!=0:
            answer+=cmb(keta-2, k-1)*(9**(k-1))
        answer+=cmb(keta-2, k-2)*max(second-1, 0)*(9**(k-2))
        if keta-1>=k and third!=0:
            answer+=cmb(keta-3, k-2)*(9**(k-2))
        if keta-1>=k:
            if third!=0:
                answer+=third
            else:
                swit=0
                kaz=0
                for zl in zlist:
                    if zl[0]>=3 and swit==0:
                        swit=zl[0]
                        kaz=zl[1]
                answer+=(keta-swit-1)*9
                answer+=1
        else:
            if third!=0:
                answer+=third
    
    print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(N: str, K: int):
    M = len(N)
    DP = [[[0]*2 for __ in range(K+1)] for _ in range(M+1)]
    Nstr = N

    DP[0][0][False] = 1

    for i in range(M):
        DP[i+1][0][True] = 1
        DP[i+1][0][False] = 0
        for k in range(K):
            DP[i+1][k+1][True] = DP[i][k][True]*9 + DP[i][k+1][True]*1
            DP[i+1][k+1][True] += DP[i][k+1][False]
            if int(Nstr[i]) != 0:
                DP[i+1][k+1][True] += DP[i][k][False]*(int(Nstr[i])-1)
            if i+1 == k+1:
                DP[i+1][k+1][False] = 1
    print(DP[M][K][True]+DP[M][K][False])
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if m < K:
        return ans
    else:
        if K == 1:
            y = Z[0]
            ans += (m-1) * 9 + y
            #print(ans)
        elif K == 2:
            #0 
            ans += ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * (m-1) * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            ans += nn(Z,K,m)
            #print(ans)
        elif K == 3:
            #0 
            ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break
            ans += nn(Z,K,m)
        return ans
if len(str(N)) < K:
    ans = 0
else:
    ans = nn(Z,K,m)        
print(ans)