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 math
import sys

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

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

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


if k==3:
    if L<4:
        for a in range(10):
            for b in range(10):
                for c in range(10):
                    if a*100+b*10+c<=n: ans+=1
    else:
        for i in range(L):
            ans+=comb[i]
        ans*=9**3
        ans+=comb[L]* 81 * (int(s[0])-1) #1桁目 1-int(s[0])-1
        if int(s[1])>0:
            ans+=comb[L-1]*81
            ans+=(L-2)*9*(int(s[1])-1)


        m=int(s[2:])

        for i in range(L-1):
            for a in range(1,10):
                if a*(10**i)<=m: ans+=1
                

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

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

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


if k==3:
    if L<4:
        for a in range(10):
            for b in range(10):
                for c in range(10):
                    if a*100+b*10+c<=n: ans+=1
    else:
        for i in range(L):
            ans+=comb[i]
        ans*=9**3
        ans+=comb[L]* 81 * (int(s[0])-1) #1桁目 1-int(s[0])-1
        ans+=comb[L-1]*81
        ans+=(L-2)*9*(int(s[1])-1)


        m=int(s[2:])

        for i in range(L-1):
            for a in range(1,10):
                if a*(10**i)<=m: ans+=1
                

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

count = 0
ketasu = len(str(N))

# 先頭が0の場合
temp = len(list(itertools.combinations(range(ketasu-1), K)))
temp *= 9 ** K
count = temp

# 先頭が0以外の場合
for i in range(1, 10):
    exists = set()
    for j in itertools.product(*(['123456789']*(K-1))): # 81
        j = list(j)
        for k in itertools.combinations(range(ketasu-K+1), K-1): # 10000
            for l in itertools.permutations(k, len(k)): # 2
                temp = ['0'] * (ketasu - 1)
                for m, c in zip(l, j):
                    temp[m] = c
                temp2 = str(i) + ''.join(temp)
                if temp2 not in exists:
                    if int(temp2) <= N:
                        count += 1
                    exists.add(temp2)

print(count)

Submission status: Wrong Answer

Solution code:
import itertools

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

count = 0
ketasu = len(str(N))

# 先頭が0の場合
temp = len(list(itertools.combinations(range(ketasu-1), K)))
temp *= 9 ** K
count = temp

# 先頭が0以外の場合
for i in range(1, 10):
    for j in itertools.product(*(['123456789']*(K-1))): # 81
        j = list(j)
        #for k in itertools.permutations(''.join(j)+'0'*(ketasu-K), ketasu-1):
        #for k in set(list(itertools.permutations(''.join(j)+'0'*(ketasu-K), ketasu-1))):
        exists = set()
        for k in itertools.combinations(range(ketasu-K+1), K-1): # 10000
            for l in itertools.permutations(k, len(k)): # 2
                temp = ['0'] * (ketasu - 1)
                for m, c in zip(l, j):
                    temp[m] = c
                temp2 = str(i) + ''.join(temp)
                if temp2 not in exists:
                    if int(temp2) <= N:
                        count += 1
                    exists.add(temp2)

print(count)

Submission status: Wrong Answer

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

l = len(N)

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
K = int(input())
# keta → 10 なら 2
S = str(N)
keta = len(S)


dp = [ [ [ 0 ]* (keta + 1)  for _ in range(100)] for _ in range(2)]
# dp[以下確定済みフラグ][0でないの個数 k ][上からn桁目か] の条件を満たしたものの個数

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

for n in  range(0,keta):
    # for i in range(0,10): #次の桁に来る候補  #ここを省略して 1～9 と 0で場合分け
    for k in range(0, K + 1):
        num = int(S[n])  #実際の数字
        num_to_9  = 9 - num  # 5 だったら 6,7,8,9
        num_hiku1_to_1 = max(0,num - 1) #未満が確定する 0 以外の数
        # 確定から確定
        #確定済みには何をつけても良い

        dp[1][k+ 1 ][n + 1] += dp[1][k][n] * 9
        #0以外を付け加えるやつ
        dp[1][k][n + 1] += dp[1][k][n] * 1  #0 を付け加えるやつ
        #kが増えないやつ
        #0を付ける
        # 未確定から確定
        dp[1][k + 1][n + 1] += dp[0][k][n] * num_hiku1_to_1 #その桁未満のを付け加えれば確定 432 4で2,1
        dp[1][k][n + 1] += dp[0][k][n] * 1 # 0を付け加えるパターン 432 4で0

        # 未確定から未確定
        if num == 0: # 402 で 4 に 0を加える
            dp[0][k][n + 1] += dp[0][k][n]
        else: # 412 で 4 に 1を加える一通り
            dp[0][k + 1][n + 1] += dp[0][k][n]

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

Submission status: Wrong Answer

Solution code:
import itertools
import sys

def cmb(n, r):
	if n - r < r: r = n - r
	if r == 0: return 1
	if r == 1: return n
	if r < 0: return 0

	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

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

if l < k:
	print(0)
	sys.exit()
elif l == 1 and k == 1:
	print(n)
	sys.exit()

#dp[i][j] = i桁目までで、0でない数字がちょうどj個あるようなものの個数
dp = [[0 for _ in range(4)]for _ in range(l+1)]
dp[1][0] = 1

for i in range(1,l+1):
	for j in range(4):
		if i >= j:
			dp[i][j] = cmb(i,j) * (9**j)

ans = dp[l-1][k]
ans += (int(n[0]) - 1) * dp[l-1][k-1]

num = l
for i in range(1,l):
	if n[i] != '0':
		num = i
		break
if num == l:
	if n.count('0') == l-k:
		print(ans+1)
	else:
		print(ans)
	sys.exit()

tmp1 = (int(n[num])-1) * cmb(9,k-2)
tmp2 = 9**(k-1)

for v in itertools.combinations(range(num,l), k-1):
	if num in v:
		t = 1
		for i in range(1,len(v)):
			t *= int(n[v[i]])
		ans += tmp1 + t
	else:
		ans += tmp2

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys

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

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

if l < k:
	print(0)
	sys.exit()
elif l == 1 and k == 1:
	print(n)
	sys.exit()

#dp[i][j] = i桁目までで、0でない数字がちょうどj個あるようなものの個数
dp = [[0 for _ in range(4)]for _ in range(l+1)]
dp[1][0] = 1

for i in range(1,l+1):
	for j in range(4):
		if i >= j:
			dp[i][j] = cmb(i,j) * (9**j)

ans = dp[l-1][k]
ans += (int(n[0]) - 1) * dp[l-1][k-1]

num = l
for i in range(1,l):
	if n[i] != '0':
		num = i
		break
if num == l:
	if n.count('0') == l-k:
		print(ans+1)
	else:
		print(ans)
	sys.exit()
tmp1 = (int(n[num])-1) * cmb(9,k-2)
tmp2 = 9**(k-1)
for v in itertools.combinations(range(num,l), k-1):
	if num in v:
		t = 1
		for i in range(len(v)):
			t *= int(n[v[i]])
		t = t // int(n[num])
		ans += tmp1 + t
	else:
		ans += tmp2

print(ans)

Submission status: Wrong Answer

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

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

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

print(cnt)

Submission status: Wrong Answer

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

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

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

print(cnt)

Submission status: Wrong Answer

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

nn = str(n)
le = len(nn)
ans1 = 0
if le > k:
    ans1 = 1
    for i in range(k):
        ans1 = 9*ans1*(le-i-1)/(i+1)

ans2 = 0
if k==1:
    ans2 = int(nn[0])
elif k==2:
    ans2 += 9*(int(nn[0])-1)*(le-1)
    for i  in range(le-1):
        if int(nn[i+1])>0:
            ans2 += int(nn[i+1])+9*(le-i-2)
            break
elif k==3:
    ans2 += 81*(int(nn[0])-1)*(le-1)*(le-2)/2
    for i  in range(le-1):
        if int(nn[i+1])>0:
            ans2 += 9*(int(nn[i+1])-1)*(le-i-2)
            for j in range(i+2,le):
                if  int(nn[j])>0:
                    ans2 += int(nn[j])+9*(le-j-1)
                    break
if le >= k:
    print(int(ans1+ans2))
else:
    print(0)

Submission status: Wrong Answer

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

nn = str(n)
le = len(nn)
ans1 = 0
if le > k:
    ans1 = 1
    for i in range(k):
        ans1 = 9*ans1*(le-i-1)/(i+1)

ans2 = 0
if k==1:
    ans2 = int(nn[0])
elif k==2:
    ans2 += 9*(int(nn[0])-1)*(le-1)
    for i  in range(le-1):
        if int(nn[i+1])>0:
            ans2 += int(nn[i+1])+9*(le-i-2)
            break
elif k==3:
    ans2 += 81*(int(nn[0])-1)*(le-1)*(le-2)/2
    for i  in range(le-1):
        if int(nn[i+1])>0:
            ans2 += 9*(int(nn[i+1])-1)*(le-i-2)
            for j in range(i+2,le):
                if  int(nn[j])>0:
                    ans2 += int(nn[j])+9*(le-j-1)
                    break
print(int(ans1+ans2))

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
def solve(i,k,smaller):
    if i == len(S):
        if k == 0:
            #0以外の個数がkと等しいので答えとしてカウントできる
            return 1
        else:
            #0以外の個数がkと等しくないので答えとしてカウント不可
            return 0 
    
    if k ==0:
        #kの個数を使い切りこれ以上下の桁は0で埋まり1通りの為
        return 1
    
    if smaller :
        return comb(len(S)-i,k)*pow(9,k)
    else:
        if S[i] =="0":
            return solve(i+1,k,False)
        else:
            zero = solve(i+1,k,True)
            aida = solve(i+1,k-1,True)*(int(S[i])-1)
            ici  = solve(i+1,k-1,False)
            
            return zero+aida+ici
            
N = int(input())
S = str(N)
K = int(input())

ans = solve(0,K,False)
print(round(ans))

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
def solve(i,k,smaller):
    if i == len(S):
        if k == 0:
            #0以外の個数がkと等しいので答えとしてカウントできる
            return 1
        else:
            #0以外の個数がkと等しくないので答えとしてカウント不可
            return 0 
    
    if k ==0:
        #kの個数を使い切りこれ以上下の桁は0で埋まり1通りの為
        return 1
    
    if smaller :
        return comb(len(S)-i,k)*pow(9,k)
    else:
        if S[i] =="0":
            return solve(i+1,k,False)
        else:
            zero = solve(i+1,k,True)
            aida = solve(i+1,k-1,True)*(int(S[i])-1)
            ici  = solve(i+1,k-1,False)
            return zero+aida+ici
            
N = int(input())
S = str(N)
K = int(input())

ans = solve(0,K,False)
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
def solve(i,k,smaller):
    print("i="+str(i))
    if i == len(S):
        if k == 0:
            #0以外の個数がkと等しいので答えとしてカウントできる
            return 1
        else:
            #0以外の個数がkと等しくないので答えとしてカウント不可
            return 0 
    
    if k ==0:
        #kの個数を使い切りこれ以上下の桁は0で埋まり1通りの為
        return 1
    
    if smaller :
        return comb(len(S)-i,k)*pow(9,k)
    else:
        if S[i] =="0":
            return solve(i+1,k,False)
        else:
            zero = solve(i+1,k,True)
            aida = solve(i+1,k-1,True)*(int(S[i])-1)
            ici  = solve(i+1,k-1,False)
            return zero+aida+ici
            
N = int(input())
S = str(N)
K = int(input())

ans = solve(0,K,False)
print(ans)

Submission status: Wrong Answer

Solution code:
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp=[[[0]*5,[0]*5] for i in range(x)]
dp[0][0][0]=1
r=0
#dp 0=n, 1=under
for i in range(1,x):
    for j in range(2):
        dp[i][1][0]=1
        for p in range(1,k+1):
            if j==0 and l[i]==0:
                dp[i][0][p]=dp[i-1][0][p]
            elif j==0 and l[i]!=0 and dp[i-1][0][p-1]:
                dp[i][0][p]=1
            if j==1:
                dp[i][1][p]=dp[i-1][1][p]+(dp[i-1][1][p-1]*9)+(dp[i][0][p]*max(0,l[i]-1))+(dp[i-1][0][p])
print(dp[-1][0][k]+dp[-1][1][k])

Submission status: Wrong Answer

Solution code:
def C(n, r):
    ans = 1
    for v, i in enumerate(range(n, n - r, -1), start=1):
        ans *= i / v
    return int(ans)

ans = 0
n, k = input(), int(input())
if len(n) != k:
    ans += C(len(str(n)) - 1, k) * (9 ** k)

if k == 1:
    ans += int(n[0])

if k == 2:
    ans += ((int(n[0])) - 1) * C(len(n) - 1, 1) * 9
    for v, i in enumerate(n[1:], start=2):
        if i != '0':
            ans += (len(n) - v) * 9 + int(i)
            break

if k == 3:
    ans += ((int(n[0])) - 1) * 81 * C(len(n) - 1, 2)
    for v, i in enumerate(n[1:], start=2):
        if i != '0':
            ans += ((int(n[v - 1]) - 1)) * 9 * C(len(n[v:]), 1)
            for s, j in enumerate(n[v:], start=v+1):
                if s != '0':
                    ans += (len(n) - s) * 9 + int(j)
                    break

print(ans)

Submission status: Wrong Answer

Solution code:
n_str = input()  # 3***
k = int(input())

dp1 = [[0] * (k + 2) for _ in range(len(n_str) + 1)]
dp2 = [[0] * (k + 2) for _ in range(len(n_str) + 1)]
# dp1[i][j] : 上から i 桁はnと一致していて、0でない数が j 個現れているような数
# dp2[i][j] : 上から i 桁が既にnより小さく、0でない数が j 個現れているような数

dp1[0][0] = 1
# dp2[0][1] = int(n_str[0]) - 1
# dp2[0][0] = 1

for i in range(len(n_str)):
    for j in range(k + 1):
        if n_str[i] != '0':
            dp1[i + 1][j + 1] += dp1[i][j]

            dp2[i + 1][j + 1] += dp1[i][j] * (int(n_str[i]) - 1)
            dp2[i + 1][j + 1] += dp2[i][j] * 9

            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            print(i, j)
            dp1[i + 1][j] += dp1[i][j]

            dp2[i + 1][j + 1] += dp2[i][j] * 9
            dp2[i + 1][j] += dp2[i][j]

# print(*dp1, sep='\n')
# print(*dp2, sep='\n')
ans = dp1[len(n_str)][k] + dp2[len(n_str)][k]
print(ans)

Submission status: Wrong Answer

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


dp0 = [[0]*(k+1) for i in range(len(n)+1)]
dp1 = [[0]*(k+1) for i in range(len(n)+1)]

dp0[0][0] = 1
dp1[0][0] = 0


for i in range(1, len(n)+1):
    for j in range(k):
        dp0[i][j] += dp0[i-1][j]*(int(n[i-1]==0))
        dp1[i][j] += dp1[i-1][j] + dp0[i-1][j]*(int(n[i-1])!=0)
        dp0[i][j+1] += dp0[i-1][j]*(int(n[i-1])!=0)
        dp1[i][j+1] += dp1[i-1][j]*9 + dp0[i-1][j]*(int(n[i-1])-1)*(int(n[i-1])!=0)
    dp0[i][k] += dp0[i-1][k]
    dp1[i][k] += dp1[i-1][k]
print(dp0[len(n)][k]+dp1[len(n)][k])

Submission status: Wrong Answer

Solution code:
import numpy as np

N=int(input())
n=[int(i) for i in str(N)]
K=int(input())
L=len(n)
dp=np.zeros((L+1,2,K+1),dtype=int)
dp[0,0,0]=1

for i in range(L):
  for smaller in [0,1]:
    for j in range(0,K):
      m=10 if smaller else n[i]+1
      for x in range(m):
        if ( (j+(x!=0)) <= K ):
          #i桁目がxだったときにdp[i][smaller][j]をどこに足しますか？
          dp[i+1][smaller or x<n[i]][j+(x!=0)]+=dp[i][smaller][j]
        
print(dp[L,:,K].sum())

Submission status: Wrong Answer

Solution code:
import numpy as np

N=int(input())
n=[int(i) for i in str(N)]
K=int(input())
L=len(n)
dp=np.zeros((L+1,2,K+1),dtype=int)
dp[0,0,0]=1

for i in range(L):
  for smaller in [0,1]:
    for j in range(0,K):
      m=10 if smaller else n[i]+1
      for x in range(m):
        #i桁目がxだったときにdp[i][smaller][j]をどこに足しますか？
        dp[i+1][smaller or x<n[i]][j+(x!=0)]+=dp[i][smaller][j]
        
print(dp[L,:,K].sum())

Submission status: Wrong Answer

Solution code:
n = list(input())
k = int(input())
length = len(n)
numerator = 1
denominator = 1
ans = 0
count_zero = 0

if length >= k:
    #第i桁が決定されている
    for i in range(length):
        if int(n[i]) == 0:
            count_zero += 1
        if k-i+count_zero == 0:
            break
        for s in range(int(n[i])):
            #第i桁が0のとき
            if s == 0:
                for t in range(k-i+count_zero):      
                    numerator = numerator*(length-(i+1)-t)
                    denominator = denominator*(t+1)
                ans += numerator//denominator*(9**(k-i))
                numerator = 1
                denominator = 1
            #第i桁が0でないとき
            else:
                for t in range(k-i-1+count_zero):
                    numerator = numerator*(length-(i+1)-t)
                    denominator = denominator*(t+1)
                ans += numerator//denominator*(9**(k-i-1))
                numerator = 1
                denominator = 1


print(ans+1)

Submission status: Wrong Answer

Solution code:
n = list(input())
k = int(input())
length = len(n)
numerator = 1
denominator = 1
ans = 0

if length >= k:
    #第i桁が決定されている
    for i in range(length):
        if k-i == 0:
            break
        for s in range(int(n[i])):
            #第i桁が0のとき
            if s == 0:
                for t in range(k-i):      
                    numerator = numerator*(length-(i+1)-t)
                    denominator = denominator*(t+1)
                ans += numerator//denominator*(9**(k-i))
                numerator = 1
                denominator = 1
            #第i桁が0でないとき
            else:
                for t in range(k-i-1):
                    numerator = numerator*(length-(i+1)-t)
                    denominator = denominator*(t+1)
                ans += numerator//denominator*(9**(k-i-1))
                numerator = 1
                denominator = 1


print(ans+1)

Submission status: Wrong Answer

Solution code:
n = list(input())
k = int(input())
length = len(n)
numerator = 1
denominator = 1
ans = 0

if length-1 >= k:
    for t in range(k):
        numerator = numerator*(length-1-t)
        denominator = denominator*(t+1)
    ans += numerator//denominator*pow(9,k)
    numerator = 1
    denominator = 1

if length >= k:
    for s in range(length):
        if s != 0:
            for t in range(k-s):
                numerator = numerator*(length-(s+1)-t)
                denominator = denominator*(t+1)
            ans += numerator//denominator*pow(9,(k-s))
            denominator = 1
            numerator = 1
            if k-s == 0:
                break
        for t in range(k-(s+1)):
            numerator = numerator*(length-(s+1)-t)
            denominator = denominator*(t+1)
        ans += numerator//denominator*pow(9,(k-s-1))*(int(n[s])-1)
        denominator = 1
        numerator = 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = list(input())
k = int(input())
length = len(n)
numerator = 1
denominator = 1
ans = 0

#１桁目が0としたときの、条件を満たす整数の数
if length-1 >= k:
    for t in range(k):
        numerator = numerator*(length-1-t)
        denominator = denominator*(t+1)
    ans += numerator//denominator*pow(9,k)
    numerator = 1
    denominator = 1

if length >= k:
    for s in range(length):
        if s != 0:
            for t in range(k-s):
                numerator = numerator*(length-(s+1)-t)
                denominator = denominator*(t+1)
            ans += numerator//denominator*pow(9,(k-s))
            denominator = 1
            numerator = 1
 
        for t in range(k-(s+1)):
            numerator = numerator*(length-(s+1)-t)
            denominator = denominator*(t+1)
        ans += numerator//denominator*pow(9,(k-s-1))*(int(n[s])-1)
        denominator = 1
        numerator = 1

        if k-s-1 == 0:
            break 

print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

# m digits, k, less than flag
n = input()
K = int(input())


def func(i, k, free=False):
    # rest digits
    m = len(n) - i

    # cannot fill m digits with 0 * k
    if k > m:
        return 0

    if m == 0:
        return 1
    # fill all digits with 0
    if k == 0:
        return 1

    if free:
        a = 9 ** k
        # print(a)
        for j in range(k):
            a *= (m - j)
        for j in range(k):
            a = a // (j + 1)
        # print(a)
        return a

    else:
        # start with 0
        a = func(i + 1, k, free=True)

        # 1, 2, ..., n[i] - 1
        b = (int(n[i]) - 1) * func(i + 1, k - 1, free=True)

        # n[i]
        c = func(i + 1, k - 1, free=False) 
        # print(i, a, b, c, k, m)
        return a + b + c

print(func(0, K, free=False))

Submission status: Wrong Answer

Solution code:
import functools

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

@functools.lru_cache(maxsize=2048)
def nCk(n, k):
    if k == 0:
        return 0
    elif k == 1:
        return n
    elif k == 2:
        return (n * (n-1)) // 2
    return (n * (n-1) * (n-2)) // 6

def slowsolve(N, K):
    ans = 0
    meta = {}
    for i in range(int(N) + 1):
        if len(str(i)) - str(i).count("0") == K:
            meta.setdefault(len(str(i)), 0)
            meta[len(str(i))] += 1
            ans += 1
    return ans, meta

@functools.lru_cache(maxsize=2048)
def solve(N, K):
    if len(N) <= 3:
        return slowsolve(N, K)[0]
    elif K == 0:
        # すべて0の1通り
        return 1
    else:
        m = int(N[0])

        # 一番上を0にする
        ans = solve("9" * len(N[1:]), K)

        if K == 3:
            # 一番上を1 ~ m - 1にする
            # => 下の部分から2か所選び、それぞれ1 ~ 9
            ans += (m - 1) * nCk(len(N[1:]), 2) * 9 * 9
            # 一番上をmにする
            ans += solve(N[1:], K - 1)
        elif K == 2:
            # 一番上を1 ~ m - 1にする
            # => 下の部分から1か所選び、1 ~ 9
            ans += (m - 1) * len(N[1:]) * 9
            # 一番上をmにする
            ans += solve(N[1:], K - 1)
        elif K == 1:
            ans += m
        return ans


print(solve(N, K))

Submission status: Wrong Answer

Solution code:

import numpy as np

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

dp = np.zeros((len(N), 2, K+1), dtype=np.int)

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

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

Submission status: Wrong Answer

Solution code:

import numpy as np

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

dp = np.zeros((len(N), 2, K+1))

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

print( int(dp[len(N)-1][0][K] + dp[len(N)-1][1][K]) )

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    k = int(args[1])

    N = list(map(int, '0' + str(n)))
    d = len(str(n))
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            # set zero on i_th digit
            F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]*(0 < N[i])

            # set non-zero on i_th digit
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
            U[i][j] += U[i-1][j-1]*(0 < N[i])

    return str(sum(x[k] for x in F+U))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import numpy as np

N=int(input())
n=[int(i) for i in str(N)]
K=int(input())
L=len(n)
dp=np.zeros((L+1,2,K+1),dtype=int)
dp[0,0,0]=1

for i in range(L):
  for smaller in [0,1]:
    for j in range(0,K):
      m=10 if smaller else n[i]+1
      for x in range(m):
        #i桁目がxだったときにdp[i][smaller][j]をどこに足しますか？
        dp[i+1][smaller or x<n[i]][j+(x!=0)]+=dp[i][smaller][j]
        
print(dp[L,:,K].sum())

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
n_len = len(str(n))

x = [1]*(n_len)
for i in range(n_len-1):
    x[i+1] = x[i]*(i+1)

def calc(i,j):
    return x[i]/x[j]/x[i-j]

m = 0
i = 0
m_ind = []
while i < n_len:
    if int(n[i]) != 0:
        m_ind += [i]
        m += 1
    if m == k:
        break
    i += 1

if n_len < k:
    print(0)
    
elif n_len == k:
    if k == 3:
        if m == 2 and m_ind[1] == 1:
            count = 0
        else:
            count = (int(n[0])-1)*9**2 + (max(1,int(n[1]))-1)*9 + int(n[2])
    if k == 2:
        count = (int(n[0])-1)*9 + int(n[1])
    if k == 1:
        count = int(n)
    print(count)
    
else:
    count = 0
    count += calc(n_len-1,k)*9**k
    if k == 1:
        count += int(n[0])
     
    else:
        count += calc(n_len-1,k-1)*9**(k-1)*(int(n[0])-1)
        if k == 2:
            if m == 2:
                count += calc(n_len-m_ind[1]-1,k-1)*9**(k-1)
                count += int(n[m_ind[1]])
            
        if k == 3:
            if m == 2:
                count += calc(n_len-m_ind[1]-1,k-1)*9**(k-1)
                count += calc(n_len-m_ind[1]-1,k-2)*9**(k-2)*(int(n[m_ind[1]])-1)
            elif m == 3:
                count += calc(n_len-m_ind[1]-1,k-1)*9**(k-1)
                count += calc(n_len-m_ind[1]-1,k-2)*9**(k-2)*(int(n[m_ind[1]])-1)
                count += calc(n_len-m_ind[2]-1,k-2)*9**(k-2)
                count += int(n[m_ind[2]])
            
    print(int(count))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
n_len = len(str(n))

x = [1]*(n_len)
for i in range(n_len-1):
    x[i+1] = x[i]*(i+1)

def calc(i,j):
    return x[i]/x[j]/x[i-j]*9**(j)

if n_len < k:
    print(0)
else:
    count = 0
    non_zero = 0
    for ind,i in enumerate(str(n)):
        if i != '0':
            non_zero += 1
            if n_len-ind-1 > k-non_zero:
                count += calc(n_len-ind-1,k-non_zero+1)
            if non_zero < k and ind != n_len-1:
                count += calc(n_len-ind-1,k-non_zero)*(int(i)-1)
            elif non_zero == k:
                count += int(i)
                break
    
    print(int(count))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
n_len = len(str(n))

x = [1]*(n_len)
for i in range(n_len-1):
    x[i+1] = x[i]*(i+1)

def calc(i,j):
    return x[i]/x[j]/x[i-j]*9**(j)

if n_len < k:
    print(0)
else:
    count = 0
    non_zero = 0
    for ind,i in enumerate(str(n)):
        if i != '0':
            non_zero += 1
            if n_len-ind-1 > k-non_zero:
                count += calc(n_len-ind-1,k-non_zero+1)
            if non_zero < k:
                count += calc(n_len-ind-1,k-non_zero)*(int(i)-1)
            elif non_zero == k:
                count += int(i)
                break
    
    print(int(count))

Submission status: Wrong Answer

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


count = 0
for i in range(n):
  if str(i+1).count("[1-9]") == k:
    count += 1
    
print(count)