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

M = int(input())
N = list(str(M))
K = int(input())

keta = len(N)
if K == 1:
    ans = 9*(keta-1)+int(N[0])
elif K == 2:
    if keta > 2:
        ans = cmb(keta-1,2)*81+max(0,int(N[0])-1)*9*(keta-1)
        for i in range(1,keta):
            if int(N[i]) != 0:
                ans += 9*(keta-i-1)+int(N[i])
                break
    else:
        ans = 0
        for i in range(11,M+1):
            if '0' not in str(i):
                 ans += 1
else:
    if keta > 3:
        ans = cmb(keta-1,3)*729+(int(N[0])-1)*81*cmb(keta-1,2)+max(0,int(N[1])-1)*(keta-2)*9
        for i in range(1,keta):
            if int(N[i]) != 0:
                ans += cmb(keta-i-1,2)*81+int(N[i+1])
                for j in range(i,keta):
                    if int(N[j]) != 0:
                        ans += 9*(keta-j-2)
                        break
                break
    else:
        ans = 0
        for i in range(111,M+1):
            if '0' not in str(i):
                ans += 1

print(int(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=input()
K=int(input())
km = len(N)
res = 0
dic = {}
dic['1'] = 0
dic['2'] = 0
dic['3'] = 0
if int(N)<=100:
    for i in range(int(N)):
        c = Counter(str(i+1))
        if len(str(i+1)) - c['0']==K:
            res += 1
    print(res)
    exit()
else:
    for i in range(1,100):
        c = Counter(str(i))
        k = len(str(i)) - c['0']
        dic[str(k)] += 1
def rec(n,k):
    re = 0
    if int(n)<100:
        return dic[str(k)]
    if k==1:
        return 9*(len(n)-1)+int(n[0])
    # 0
    t = ''.join(['9']*(len(n)-1))
    return rec(t, k) + (int(n[0])-1)*rec(t, k-1) + rec(n[1:], k-1)
print(rec(N,K))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

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


def main():
    n = II()
    k = II()
    keta = []
    l = n
    while True:
        amari = l % 10
        keta.append(amari)
        l = l // 10
        if l < 1:
            break

    if len(keta) < k:
        print(0)
        return

    ans = 0
    for i in range(1, len(keta)):
        if i < k:
            continue
        ans += cmb(i - 1, k - 1) * pow(9, k)
    ans += cmb(len(keta) - 1, k - 1) * pow(9, k-1) * (keta[-1] - 1)
    # print(ans)
    if k == 1:
        print(ans + 1)
    elif k == 2:
        for i in range(len(keta)-1):
            if sum(keta[i+1:-1]) == 0:
                ans += keta[i]
            else:
                ans += 9
        print(ans)

    else:
        for i in range(len(keta)-1):
            for j in range(i+1, len(keta)-1):
                if sum(keta[j+1:-1]) == 0:
                    ans += (max(keta[j]-1, 0)) * 9
                    if sum(keta[i+1:j]) == 0:
                        ans += keta[i]
                    else:
                        ans += 9
                else:
                    ans += 81

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ar = list(map(lambda x: len(str(x).replace('0', '')), range(1, N+1)))
print(ar)
print(ar.count(K))

Submission status: Wrong Answer

Solution code:
import itertools

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


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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = input()
d_num = len(N) #ケタ数
K = int(input())
ans = 0

if(K == 1):
 top = int(N[0]) #最高位
 ans += (d_num-1)*9  
 ans += top

elif(K == 2):
 if(d_num >= 2): 
     top, semi = int(N[0]), int(N[1]) #最高位, 準最高位
 
   #Top以外2つ選んだ場合
     ans += (((d_num-1)*(d_num-2))//2)*9*9 #nC2*9*9  
   #Top含む2つ
    #Top<top を選んだ場合
     ans += 1*(d_num-1)*(top-1)*9
    #Top==top + Semi を選んだ場合
     ans +=  1*1*1*(semi)
    #Top==top + Semi以外 を選んだ場合
     ans +=  1*(d_num-2)*1*9

elif(K == 3):
 if(d_num >= 3): 
     top, s1, s2 = int(N[0]), int(N[1]), int(N[2]) #最高位, 準最高位,準々最高位
 
   #Top以外3つ選んだ場合
     ans += (((d_num-1)*(d_num-2)*(d_num-3))//6)*9*9*9 #nC3*9*9  
   #Top含む3つ
    #Top<top を選んだ場合
     ans += 1*(((d_num-1)*(d_num-2))//2)*(top-1)*9*9
    #Top==top + S1 を選んだ場合
     #S1 < s1 のとき
     ans += 1*1*(d_num-2)*1*(s1-1)*9
     #S1 = s1のとき
      #S2を選んだ場合
     ans += 1*1*1*1*1*s2
      #S2以外を選んだ場合
     ans += 1*1*(d_num-3)*1*1*9
    #Top==top + S1以外 を選んだ場合
     ans +=  1*(((d_num-2)*(d_num-3))//2)*1*9*9

print(ans)

Submission status: Wrong Answer

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

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

if K == 2:
    if len(N) < 2:
        print(0)
        exit()
    c = 0
    if N[0] == 1:
        d = 0
        d += int(N[1])
        d += (len(N) - 2) * 9
        d += int((len(N) - 1) * (len(N) - 2) / 2 * 81)
        print(d)
    else:
        d = 0
        d += int(N[1])
        d += (len(N) - 2) * 9
        d += (len(N) - 1) * 9 * (int(N[0]) - 1)
        d += int((len(N) - 1) * (len(N) - 2) / 2 * 81)
        print(d)

if K == 3:
    if len(N) < 3:
        print(0)
        pass
    d = 0
    e = 0
    e += int(N[2])
    e += (len(N) - 3) * 9
    e += (len(N) - 2) * 9 * (int(N[1]) - 1)
    d += e
    d += (len(N) - 1) * (len(N) - 2) // 2 * 81 * (int(N[0]) - 1)
    d += (len(N) - 1) * (len(N) - 2) * (len(N) - 3) // 6 * 729
    print(d)

Submission status: Wrong Answer

Solution code:
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[99-i])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[99-i])-1)
    print(counter)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
w=[int(i) for i in str(n)]
x=len(w)
ans=chk=0
if n<10000:
    for i in range(1,n+1):
        chk=0
        p=i
        while p>0:
            if p%10>0:
                chk+=1
            p//=10
        ans += chk==k
    print(ans)
    exit()

if k==3:
    for a in range(x-2):
        e=1
        for b in range(a+1,x-1):
            f=1
            for c in range(b+1,x):
                if a==0 and e and f:
                    ans+=(w[a]-1)*w[b]*9
                    ans+=1*(w[b]-1)*9
                    ans+=1*1*w[c]
                    if w[c]!=0:
                        f=0
                elif a==0 and e:
                    ans+=(w[a]-1)*w[b]*9
                    ans+=1*(w[b]-1)*9
                    ans+=1*1*w[c]
                    if w[b]!=0:
                        e=0
                else:
                    ans+=9**3
elif k==2:
    for a in range(x-1):
        for b in range(a+1,x):
            if a==0 and b==1:
                ans+=(w[a]-1)*9
                ans+=1*w[b]
            elif a==0:
                ans+=w[a]*9
            else:
                ans+=9**2
else:
    ans=w[0]*(9**(x-1))
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):
	if N_list[s] == 0:
		return 0
	total = 0
	for i in range(s, L):
		if i == s:
			total += N_list[i]
		else:
			total += 9
	return total

def count2(s):
	if N_list[s] == 0:
		if s < L - 1:
			return count2(s + 1)
		else:
			return 0
	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=input()
k=int(input())

p=len(n)
q=int(n[0])

if k==1:
    ans=9*(p-1)+q
if k==2:
    if int(n)>9:
        q2=int(n[1])
        ans=int(81*0.5*(p-1)*(p-2))
        ans+=9*(p-1)*(q-1)
        ans+=q2+9*(p-2)
    else:
        ans=0
    
if k==3:
    if int(n)>110:
        q2=int(n[1])
        q3=int(n[2])
        ans=int(729*((p-1)*(2*p-3)*(p-2)-3*(p-1)*(p-2))/12)
        print(ans)
        ans+=81*(q-1)*(p-1)*(p-2)/2
        ans+=81*(p-2)*(p-3)/2
        ans+=9*(p-3)*q2
        ans+=(q2-1)*9
        ans+=q3
    else:
        ans=0

print(int(ans))

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
N=input()
K=int(input())
if len(N)<K:
    print(0)
    exit()
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += (int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*(len(N)-2)+int(N[1])
else:
    ans += int(N[2])+(len(N)-3)*9+(int(N[1])-1)*(len(N)-2)*9+comb(len(N)-2,2)*81
print(ans)

Submission status: Wrong Answer

Solution code:
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
elif L == K:
    if N == "10":
        res = 0
    elif int(N) >= 100 and int(N) <= 110:
        res = 0
    else:
        if L == 1:
            res = int(N)
        elif L == 2:
            if N[1] == "0":
                N = str(int(N) - 1)
            res = (int(N[0]) - 1) * 9 + int(N[1])
        elif L == 3:
            if N[1] == "0":
                if N[2] == "0":
                    N = str(int(N) - 1)
                else:
                    N = str(int(N) - int(N[2]) - 1)
            res = (int(N[0]) - 1) * 81 + (int(N[1]) - 1) * 9 + int(N[2])
    print(res)
else:
    if K == 1:
        res = (L - 1) * 9 + int(N[0])
    elif K == 2:
        res = (
            (((L - 1) * (L - 2)) // 2) * 81
            + (L - 1) * 9 * (int(N[0]) - 1)
            + (L - 2) * 9
            + int(N[1])
        )
    elif K == 3:
        res = (
            (((L - 1) * (L - 2) * (L - 3)) // 6) * (9 ** 3)
            + (((L - 1) * (L - 2)) // 2) * 81 * (int(N[0]) - 1)
            + (((L - 2) * (L - 3)) // 2) * 81
            + (L - 2) * 9 * (int(N[1]) - 1)
            + (L - 3) * 9
            + int(N[2])
        )
    print(res)

Submission status: Wrong Answer

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

ar = list(map(lambda x: len(str(x).replace('0', '')), range(1, N+1)))
# print(ar)
print(ar.count(1))

Submission status: Wrong Answer

Solution code:
su = 0
m = int(input())
numOfZeros = int(input())
for i in range(1,m +1):
    num = i
    currZeros = 0
    while(i>=10):
    	if num % 10 == 0:
   		    currZeros += 1
    	num /= 10

    if currZeros == numOfZeros:
    	su += 1
print(su)

Submission status: Wrong Answer

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n = input()
    k = int(input())

    num = int(n)

    if k == 1:
        ans = (len(n)-1) * 9
        ans += int(n[0])
        print(ans)
        return

    elif k == 2:
        if num < 100:
            print(num-10-(int(n[0])-1))
            return
        else:
            ans = 0
            ans = int(n[1])+9*(len(n)-2)
            ans += (int(n[0])-1) * 9 * (len(n)-1)
            ans += 9*9 * combinations_count(len(n)-1, 2)
            print(ans)
            return

    elif k == 3:
        if num < 111:
            print(0)
            return
        elif num < 1000:
            ans = (int(n[0])-1) * 81
            ans += (int(n[1])-1) * 9
            ans += (int(n[2]))
            print(ans)
            return
        else:
            n_len = len(n)
            ans = 9*9*9 * combinations_count(n_len-1, 3) # 一桁めが０
            ans += (int(n[1])-1) * (9*(n_len-2)) + int(n[2])+(9*(n_len-3)) # 一桁めがmax & 二桁めが1-9
            ans += (9*9) * combinations_count(n_len-2, 2)
            ans += (int(n[0])-1) * (9*9)*combinations_count(n_len-1, 2)
            print(ans)
            return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
elif L == K:
    if N == "10":
        res = 0
    elif int(N) >= 100 and int(N) <= 110:
        res = 0
    else:
        if L == 1:
            res = int(N)
        elif L == 2:
            if N[1] == "0":
                N = str(int(N) - 1)
            res = (int(N[0]) - 1) * 9 + int(N[1])
        elif L == 3:
            if N[1] == 0:
                if N[2] == 0:
                    N = str(int(N) - 1)
                else:
                    N = str(int(N) - int(N[2]) - 1)
            res = (int(N[0]) - 1) * 81 + (int(N[1]) - 1) * 9 + int(N[2])
    print(res)
else:
    if K == 1:
        res = (L - 1) * 9 + int(N[0])
    elif K == 2:
        res = (
            (((L - 1) * (L - 2)) // 2) * 81
            + (L - 1) * 9 * (int(N[0]) - 1)
            + (L - 2) * 9
            + int(N[1])
        )
    elif K == 3:
        res = (
            (((L - 1) * (L - 2) * (L - 3)) // 6) * (9 ** 3)
            + (((L - 1) * (L - 2)) // 2) * 81 * (int(N[0]) - 1)
            + (((L - 2) * (L - 3)) // 2) * 81
            + (L - 2) * 9 * (int(N[1]) - 1)
            + (L - 3) * 9
            + int(N[2])
        )
    print(res)

Submission status: Wrong Answer

Solution code:
def countInRangeUtil(pos, cnt, tight, num): 
    if pos == len(num):
        if cnt <= K: 
            return 1
        return 0
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
    ans = 0
    limit = 9 if tight else num[pos] 
    for dig in range(limit + 1): 
        currCnt = cnt
        if dig != 0: 
            currCnt += 1
        currTight = tight
        if dig < num[pos]: 
            currTight = 1
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight]
def countInRange(x): 
    global dp, K, M 
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
    num.reverse() 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  
dp = [] 
M = 1000

K = 0

L = 1
R = int(input())
K = int(input())
print(countInRange(R) - countInRange(L - 1))

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)) // 6) * (9**3)
    # 上位二桁とその他, 最上位が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) // 2 * (9**2)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

input = sys.stdin.readline
n = int(input())
k = int(input())
t = n
m = 0
while t:
    m += 1
    t //= 10

def comb(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 9 ** k * comb(m-1, k)
tk = k

def dfs(i, mt, kt):
    a = i // 10 ** mt
    b = n // 10 ** mt
    if kt < 0:
        return 0
    if mt < kt:
        return 0
    if a < b:
        if mt > 0:
            return 9 ** kt * comb(mt, kt)
        else:
            return 1
    elif a > b:
        return 0
    if i == n:
        return 1
    ret = 0
    for j in range(10):
        f = 0
        if j:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

t_ans = 0
for i in range(1, n // 10 ** (m-1)+1):
    ti = i * 10 ** (m-1)
    t_ans += dfs(ti, m-1, k-1)

print(ans+t_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:
            k = 0
            for i in range(1,len(n)):
                if k==0:
                    ans += int(n[i])
                    if n[i]!="0":k=1
                else:
                    ans+=9
        else:
            k = 0
            for i in range(1,len(n)-1):
                for j in range(2,len(n)):
                    if k==0:
                        ans += int(n[i])*9
                    else:
                        ans += 9*9
                if n[i]!="0":k=1
    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:
import itertools
#nCr
import math
def com(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n=input()
k=int(input())
m=len(n)
if k==1:
    x=int(n[0])
    print(9*(m-1)+x)
    exit()
ans=0
x=int(n[0])
ans+=9**k*com(m-1,k)+(x-1)*com(m-1,k-1)*9**(k-1)
# print(9**k*com(m-1,k),(x-1)*com(m-1,k-1)*9**(k-1))
i=1
while i<m and n[i]=="0":
    i+=1
if k==3:
    if m<3:
        print(0)
        exit()
    if i<=2:
        x=int(n[1])
        ans+=9**2*com(m-2,2)+(x-1)*com(m-2,1)*9
        ans+=int(n[2])+9*(m-3)
elif k==2:
    if m==1:
        print(0)
        exit()
    if i==1:
        ans+=int(n[1])+9*(m-2)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    n = input()
    k = int(input())

    num = int(n)

    if k == 1:
        ans = (len(n)-1) * 9
        ans += int(n[0])
        print(ans)
        return

    elif k == 2:
        if num < 100:
            print(num-10-(int(n[0])-1))
            return
        else:
            ans = 0
            ans = int(n[1])+9*(len(n)-2)
            ans += (int(n[0])-1) * 9 * (len(n)-1)
            ans += 9*9 * combinations_count(len(n)-1, 2)
            return

    elif k == 3:
        if num < 111:
            print(0)
            return
        elif num < 1000:
            ans = (int(n[0])-1) * 81
            ans += (int(n[1])-1) * 9
            ans += (int(n[2]))
            print(ans)
            return
        else:
            n_len = len(n)
            ans = 9*9*9 * combinations_count(n_len-1, 3) # 一桁めが０
            ans += (int(n[1])-1) * (9*(n_len-2)) + int(n[2])+(9*(n_len-3)) # 一桁めがmax & 二桁めが1-9
            ans += (9*9) * combinations_count(n_len-2, 2)
            ans += (int(n[0])-1) * (9*9)*combinations_count(n_len-1, 2)
            print(ans)
            return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools as it
import math

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

keta = len(N)

ans = 0
num = "9" *K
def perm(n,k):
    return math.factorial(n)//math.factorial(n-k)

ans=0
if keta > K:
    ans += (9**K)*perm(keta-1, K)//math.factorial(K)
#print(ans)

if K>keta:
    ans = 0
elif K==1:
    ans += int(N[0])
elif K==2:
    ans += (int(N[0])-1) * 9 * (keta-1)#あたまが1小さい
    ans += int(N[1])#頭が同じ
    if keta >= 3:
        ans += 9 * (keta-2)
else:
    ans += (int(N[0]) - 1 )*(9**2)*perm(keta-1, 2)//2 ##頭が1小さい
    ##頭が同じ
    if int(N[1])>0:#上2桁目-1
        ans += (int(N[1])-1) * 9 * (keta-2)
    #上2桁目まで同じ
    ans += int(N[2])
    ans += 9*(keta-3)

# if K==1:
#     ans += int(N[0])
# elif K==2:
#     ans += int(N[0:2])
#     for i in range(keta-2):
#         ans += int(N[0]) * 9 
# else:
#     ans += int(N[0:3])
#     ans += int(N[0]) * 99 * perm(keta-2, 2)

print(ans)

Submission status: Wrong Answer

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

def nCmMOD(A,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)
elif 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:
    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:
import sys 
N = list(input())
K = int(input())

L = len(N)
if K>L:
    print(0)
    sys.exit()
#%%
def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        L2 -= 1
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)* int((L2-1)>0)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    print(i,L2,K2,ans)
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == K:
    ans += 1
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s, t = input().split()
    a, b = LI()
    u = input()
    if u == s:
        print("{} {}".format(a - 1, b))
    elif u == t:
        print("{} {}".format(a, b - 1))
    return


# B
def B():
    s = input()
    print('x' * len(s))
    return


# C
def C():
    n = I()
    a = LI()
    s = set()
    for i in a:
        s.add(i)
    if len(s) == n:
        print('YES')
    else:
        print('NO')
    return


# D
def D():
    N, K = LI()
    p = LI()
    map_p = list(map(lambda x: (1 + x), p))
    cumsum_p = [0] * N
    ans_p = [0] * N
    cumsum_p[0] = map_p[0]
    ans_p[0] = map_p[0]
    for i in range(1, N):
        cumsum_p[i] = cumsum_p[i - 1] + map_p[i]
        ans_p[i] = ans_p[i - 1] + map_p[i]
    for i in range(K, N):
        ans_p[i] -= cumsum_p[i - K]
    print(max(ans_p[K - 1:]) / 2.0)
    return


# E
def E():
    N = list(map(int, list(input())))
    K = I()
    l = len(N)
    if K == 1:
        ans = N[0] + 9 * (l - 1)
        print(ans)
    elif K == 2:
        if l < 2:
            print(0)
            return
        ans = (l - 1) * (l - 2) * 81 // 2 + N[0] * 9 * (l - 1) - (9 - N[1])
        print(ans)
    elif K == 3:
        if l < 3:
            print(0)
            return
        ans = (l - 1) * (l - 2) * (l - 3) * (9 ** 3) // 6 + N[0] * (l - 2) * (l - 3) * 81 // 2 + N[0] * N[1] * (
                    l - 2) * 9 - (9 - N[2])
        print(ans)
    return


# F
def F():
    return


# Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

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

M = len(str(N)) # 桁数

def solve_1(n,m):
    ans = 0
    ans += 9*(m-1)
    x = n//(10**(m-1))
    ans += x
    return ans

def solve_2(n,m):
    ans=0
    if m<2:
        return ans
    elif m>2:
        ans+= (9**2)*int((m-2)*(m-1)/2) 

    x = n//(10**(m-1))
    ans+= (x-1)*(m-1)*9
    ans+= int(str(n)[1])+9*(m-2)
    return ans

def solve_3(n,m):
    ans=0
    if m<3:
        return ans
    elif m>3:
        ans+=int((9**3)*(1/6)*(m-1)*(m-2)*(m-3))
    
    x = n//(10**(m-1))
    ans+=int((x-1)*(m-1)*(m-2)/2*81)
    
    y= int(str(n)[1:])

    ans+=solve_2(y,len(str(y)))
    return ans

if K==1:
    ans = solve_1(N,M)
if K==2:
    ans = solve_2(N,M)
if K==3:
    ans = solve_3(N,M)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
#nCr
import math
def com(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n=input()
k=int(input())
m=len(n)
if k==1:
    x=int(n[0])
    print(9*(m-1)+x)
    exit()
ans=0
x=int(n[0])
ans+=9**k*com(m-1,k)+(x-1)*com(m-1,k-1)*9**(k-1)
# print(9**k*com(m-1,k),(x-1)*com(m-1,k-1)*9**(k-1))
i=1
while i<m and n[i]=="0":
    i+=1
if k==3:
    if m<3:
        print(0)
        exit()
    if i<=2:
        x=int(n[1])
        ans+=9**2*com(m-2,2)+(x-1)*com(m-2,1)*9
        ans+=int(n[2])+9*(m-3)
elif k==2:
    if m==1:
        print(0)
        exit()
    if i<=2:
        ans+=int(n[1])+9*(m-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:
            k = 0
            for i in range(1,len(n)):
                if k==0:
                    ans += int(n[i])
                    if n[i]!="0":k=1
                else:
                    ans+=9
        else:
            k = 0
            for i in range(1,len(n)-1):
                for j in range(2,len(n)):
                    if k==0:
                        ans += int(n[i])*9
                        if n[i]!="0":k=1
                    else:
                        ans += 9*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)