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: Time Limit Exceeded

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

def sum10ofject(x):
  count=0
  while x!=0:
    if x%10!=0:
      count+=1
    x=x//10
  return count
numcount=0
for i in range(n+1):
  if sum10ofject(i)==k:
    numcount+=1
print(numcount)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = int(input())
L = []

for i in range(N+1):
  I = str(i)
  c = 0
  for j in range(len(I)):
    if I[j] != '0':
      c += 1
  if c == a:
    L.append(I)
    
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
ans = 0
for i in range(1, n+1):
    s = str(i)
    s = s.replace('0', '')
    if len(s) == k:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
coun = 0
for i in range(1,n+1):
	co = str(i).count("0")
	if len(str(i))-co==k:
		coun+=1
print(coun)

Submission status: Time Limit Exceeded

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

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for i3 in range(1,10):
                for j1 in range(len(str(N))-2):
                    for j2 in range(len(str(N))-2-j1):
                        for j3 in range(len(str(N))-2-j1-j2):
                            if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                                res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
k=int(input())
counter = 0
for i in range(1,n+1):
    if len(list(str(i))) - list(str(i)).count('0') == k:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import math
import calendar
import fractions
import itertools

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

ans = 0

for i in range(1, n + 1):
    if len(str(i)) - k == str(i).count("0"):
       ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
count = 0
for i in range(1, n+1):
  s = str(i)
  z = s.count('0')
  if len(s) - z == k:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

  _list = [i for i in range(1, n+1)]
  
  count = 0
  for i in _list:
    tmp = str(i)
    if len(tmp) - tmp.count('0') == k:
      count += 1

  print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
K=int(input())
i=1
m=0
for i in range(N+1):
    l=(len(str(i)))
    n=(str(i)).count('0')
    g=l-n
    if K == g:
        m+=1
    i+=1

print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
import math
ans = 0
for i in range(n):
  if int (math.log10(i+1) + 1) - str(i+1).count("0") ==k :
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
K=int(input())
ans=0
for i in range(N+1):
    if len(str(i).replace("0",""))==K:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
b = int(input())
flag = 0
for i in range (1,a + 1):
    i = str(i)
    if i.count('0') == len(i) - b:
        flag = flag + 1
print(flag)

Submission status: Time Limit Exceeded

Solution code:
N = input().strip()
K = input().strip()
cnt = 0
for i in range(int(N)):
  if len(str(i+1).replace('0', '')) == int(K):
    cnt = cnt + 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def getNum(num):
  lst = str(num)
  return len(lst) - lst.count('0')

n = int(input())
k = int(input())
start = int('1'*k)
count = 0

for i in range(start,n+1):
  if getNum(i) == k:
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

t=0
for i in range(1,n+1):
  s = [str(i)[j] for j in range(len(str(i))) if str(i)[j]!='0']
  if len(s)==k:
    t +=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
a = [len(str(i).replace("0","")) for i in range(1,n+1)]
print(a.count(k))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
counter = 0
for num in range(1, n+1):
    check = str(num)
    if len(check.replace('0', '')) == k:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

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

count = 0
i = 1
while i <= N:
  s = str(i)
  if K == (len(s) - s.count("0")):
    count = count + 1
  i = i + 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
K=int(input())
i=1
m=0
for i in range(N+1):
    l=(len(str(i)))
    n=(str(i)).count('0')
    if K == (l-n):
        m=m+1
    i=i+1

print(m)

Submission status: Time Limit Exceeded

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

ans = 0
for n in range(N+1):
    cnt_zero = str(n).count('0')
    if cnt_zero == len(str(n)) - K:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

print(np.alen(set(filter(lambda s: np.count_nonzero(list(map(int, str(s)))) == K, range(0, N+1)))))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
K=int(input())
a=0
for i in range(1,N+1):
  i=str(i)
  if((len(i)-i.count("0"))==K):
    a+=1
print(a)

Submission status: Time Limit Exceeded

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

count = 0

for i in range(1, N + 1):
  s = str(i)
  count_len = len(s)
  count_zero = s.count('0')
  count_not0 = count_len - count_zero
  if (count_not0 == K):
    count += 1

print(count)

Submission status: Time Limit Exceeded

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 a in range(1,10):
                        for b in range(1,10):
                            for c in range(1,10):
                                P=str(a)+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
    print(counter)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
k = int(input())
ans = 0

for i in range(1,n+1):
    i = str(i)
    if len(i) - i.count("0") == k:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
i = 1
while i <= N:
  n = len(str(i)) - str(i).count("0")
  if K == n:
    count = count + 1
  i = i + 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input())
ans = 0
for i in range(1,N+1):
    number = []
    for j in str(i):
        number.append(j)
    new = [s for s in number if s != "0"]
    if len(new) == K:
        ans += 1
    else:
        pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

print(len(set(filter(lambda s: np.count_nonzero(list(map(int, str(s)))) == K, range(0, N+1)))))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(input())
counter = 0
for num in range(n+1):
    nonzero = 0
    for i in str(num):
        if i != "0":
            nonzero += 1
    if nonzero == k:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

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

count=0
for i in range(1,N+1):
    if str(i).count('0')==len(str(i))-K:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

count = 0
for n in range(1, N + 1):
    n = list(str(n))
    
    if len(n) - n.count("0") == K:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input())
res = 0
for i in range(1, N+1):
  l = len(str(i)) - str(i).count("0")
  if (l == K):
    res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input())
ans = 0
for i in range(1,N+1):
    s = str(i).count("0")
    l = len(str(i))-s
    if l==K:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
  s = str(i + 1)
  c = len(s) - s.count("0")
  if c == K:
    sum = sum + 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
def zerokiller(n):
    return str(n).replace("0","")

ans=0
N=int(input())
K=int(input())
for i in range(1,N+1):
    if len(zerokiller(i))==K:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input())
c = 0
for i in range(1, N+1):
    if len(str(i).replace('0', '')) == K:
        c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
def check(n):
  tmp = str(n)
  count = 0
  for i in range(len(tmp)):
    if tmp[i] != "0":
      count+=1
  return count

n = int(input())
k = int(input())
count = 0

for i in range(n+1):
  tmp = check(i)
  if tmp == k:
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

def count_K_naive(N, K):
    def count_nonzero(n):
        num_nonzero = 0
        while n > 0:
            if n % 10 != 0:
                num_nonzero += 1
            n = n // 10
        return num_nonzero

    num_K = 0
    for n in range(1, N+1):
        if count_nonzero(n) == K:
            num_K += 1

    return num_K

print(count_K_naive(N, K))

Submission status: Time Limit Exceeded

Solution code:
L = [str(x).replace("0","") for x in range(int(input()) + 1)]
K = int(input())
print([len(x) == K for x in L].count(True))

Submission status: Time Limit Exceeded

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

count = 0
for i in range(1,N+1):
    char = str(i)

    if(K == len(char) - char.count("0")):
        count = count + 1

print(count)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, N + 1):
    string = str(i)
    string = string.replace('0', '')
    if len(string) == K:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

print(len(set(filter(lambda s: len(s.replace('0','')) == K, map(str, range(0, N+1))))))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
k=int(input())
count=0
for i in range(1,n+1):
  s=str(i)
  n=len(s)
  if n-s.count('0')==k:
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    counter = [0, 0, 0, 0]
    for i in range(1, N+1):
        cnt = len(str(i)) - str(i).count('0')
        if cnt <= 3:
            counter[cnt] += 1
    print(counter[K])


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

for i in range(n+1):
    if len(str(i))-str(i).count("0")==k:
        cnt +=1
    else:
        continue

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input())
nums = [i for i in range(1, N+1) if len(str(i).replace("0", "")) == K]
print(len(nums))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
k=int(input())
count=0
for i in range(1,n+1):
    if len(str(i).replace('0','')) == k:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#E

n = int(input())
k = int(input())
count = 0
for i in range(1,n+1):
    
    m = 0
    s = str(i)
    for j in range(len(s)):
        
        if s[j] != "0":
            m += 1
    
    if m == k:
        count += 1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
s = input()
n = int(s)
l = len(s)
k = int(input())

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

elif k == 2:
	if len(s) == 1:
		print(0)
	elif len(s) == 2:
		print(n - 9 - n//10)
	else:
		ans = 81 * (l-1) * (l-2) // 2
		for i in range(1, 10):
			for x in range(l-1):
				for j in range(1, 10):
					if i * (10**(l-1)) + j * (10**x) <= n:
						ans += 1
		print(ans)

else:
	if len(s) < 3:
		print(0)
	elif len(s) == 3:
		ans = 0
		for i in range(100, n+1):
			if "0" not in list(str(i)):
				ans += 1
		print(ans)
	else:
		ans = 729 * (l-1) * (l-2) * (l-3) // 6
		for i in range(1, 10):
			for x, y in combinations(range(l-1), 2):
				for z in range(81):
					j, k = (z//9) + 1, (z%9) + 1
					if i * (10**(l-1)) + j * (10**x) + k * (10**y) <= n:
						ans += 1
		print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
k=int(input())
count=0
for i in range(1,n+1):
    hoge=str(i).replace('0','')
    if len(hoge)==k:
        count+=1
print(count)

Submission status: Accepted

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

def comb(n,k):
    s=1
    for i in range(k):
        s*=n-i
    for i in range(k):
        s//=i+1
    return s

def ans(n,k):

    s=0
    if int(str(n)[0])==0:
        return 0
    if len(str(n))<k:
        return 0
    elif len(str(n))==k:
        s+=(int(str(n)[0])-1) * comb(len(str(n))-1,k-1)*9**(k-1)
        if k-1==0:
            s+= 1
        else:
            s+= ans(int(str(n)[1:]),k-1)
        return s
    else:
        s += (int(str(n)[0]) - 1) * comb(len(str(n)) - 1, k - 1) * 9 ** (k - 1)
        if k-1==0:
            s+= 1
        else:
            s+= ans(int(str(n)[1:]),k-1)
        s+=comb(len(str(n))-1,k)*9**(k)
        return s

print(ans(n,k))

Submission status: Accepted

Solution code:
def nCkpow(n,k):
    if n<k:
        return 0
    y=1
    for i in range(k):
        y*=n-i
        y//=i+1
        y*=9
    return y
def f(s,m,k):
    #print(m,k)
    if len(s)-m<k:
        return 0
    if  k==0:
        return 1
    if s[m]=='0':
        return f(s,m+1,k)
    l=len(s)-m
    y=nCkpow(l-1,k)
    y+=(int(s[m])-1)*nCkpow(l-1,k-1)
    return y+f(s,m+1,k-1)
N=input()
K=int(input())
print(f(N,0,K))

Submission status: Accepted

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

digit_n = len(n)

# dp[x][j][i]: x:n未満か否か, j:0でない数字の数, i:桁
dp = [[[0] * (digit_n + 1) for _ in range(k+1)] for _ in range(2)]
dp[0][0][0] = 1

for i in range(digit_n):
    m = int(n[i])
    for j in range(k+1):
        dp[1][j][i+1] = dp[1][j][i]
        if j > 0:
            dp[1][j][i+1] += dp[1][j-1][i] * 9
    for j in range(k+1):
        if m == 0:
            dp[0][j][i+1] = dp[0][j][i]
        else:
            dp[1][j][i+1] += dp[0][j][i]
            if j > 0:
                dp[1][j][i+1] += dp[0][j-1][i] * (m-1)
                dp[0][j][i+1] = dp[0][j-1][i]

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

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    S=input()
    N=len(S)
    K=I()
    
    dpl=[[0]*(K+1)for _ in range(N+1)]
    dpt=[[0]*(K+1)for _ in range(N+1)]
    
    #dp[i][j]はi桁目まで見て0以外がj個．tは上限
    dpt[0][0]=1
    
    for i in range(N):
        #とりあえずルーズな方
        for j in range(K+1):
            dpl[i+1][j]=dpl[i][j]# 0が増えた場合
            
        for j in range(1,K+1):
            dpl[i+1][j]+=dpl[i][j-1]*9 # 0以外が増えた場合
            
        s=int(S[i])
        #タイトな方
        if s==0:
            for j in range(K+1):
                dpt[i+1][j]=dpt[i][j]#0をつけるしかない
        else:
            for j in range(1,K+1):
                dpt[i+1][j]=dpt[i][j-1]#0以外をつける
            
            #ルーズに落ちる
            for j in range(K+1):
                dpl[i+1][j]+=dpt[i][j]#0をつける
            #ルーズに落ちる
            for j in range(K):
                dpl[i+1][j+1]+=dpt[i][j]*(s-1)#0以外をつける
                
    ans=dpt[-1][-1]+dpl[-1][-1]
    
    print(ans)
    
    # for i in range(N+1):
    #     print(dpt[i])
        
    # print()
    # for i in range(N+1):
    #     print(dpl[i])
                
            
            
        
        

main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect


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

def main():
    N = S()
    K = I()
    dig = len(N)
    if dig < K:
        print(0)
        exit()
    ans = 0
    for i in range(dig):
        if K == 0:
            ans += 1
            break
        if int(N[i]) == 0:
            continue
        if dig - i - 1 >= K:
            ans += combinations_count(dig - i - 1, K) * pow(9, K)
        if dig - i - 1 >= K - 1:
            ans += (int(N[i]) - 1) * combinations_count(dig - i - 1, K - 1) * pow(9, K - 1)
        if i == dig - 1:
            ans += 1
        K -= 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input()
a = list(n)
k = int(input())
n = len(a)
for i in range(n):
    a[i] = int(a[i])
dp = [[[0 for i in range(2)] for i in range(k+2)]for i  in range(n)]
dp[0][0][0] = 1
dp[0][1][0] = a[0]-1
dp[0][1][1] = 1
for i in range(n-1):
    for j in range(k+1):
        if a[i+1] == 0:
            dp[i+1][j][1] += dp[i][j][1]
            dp[i+1][j][0] += dp[i][j][0]
            dp[i+1][j+1][0] += dp[i][j][0]*9
        else:
            dp[i+1][j][0] += dp[i][j][0]+dp[i][j][1]
            dp[i+1][j+1][0] += dp[i][j][1]*(a[i+1]-1)+dp[i][j][0]*9
            dp[i+1][j+1][1] += dp[i][j][1]
print(dp[n-1][k][0]+dp[n-1][k][1])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-
# 桁DP
# 1以上n以下の整数であって、 10進法で表したときに、0でない数字がちょうど
# k個あるようなものの個数

n = input()
k = int(input())
l = len(n)
#dp[i][j][status]   status=0 は小さいのが未確定=i文字まで同じ
#                   status=1 は小さいことが確定
# i桁目まで決めて、0でない桁がj個
# 初期値は1 からスタート s=0,i=0,j=0
dp = [[[0]*2 for j in range(k+1)] for i in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    ni = int(n[i])
    for j in range(k+1):
        for st in range(2):
            for x in range(10):
                i_ = i+1
                j_ = j
                st_ = st
                if x != 0:
                    j_ += 1
                if j_ > k:
                    continue
                if st_ == 0 and x > ni:
                    continue
                if st_ == 0 and x < ni:
                    st_ = 1
                dp[i_][j_][st_] += dp[i][j][st]

print(sum(dp[l][k]))

Submission status: Accepted

Solution code:

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

l = len(N)

dp = [[[0]*(K+1) for _ in range(2)] for _ in range(l)]
dp[0][0][1] = 1
dp[0][1][1] = int(N[0]) - 1
dp[0][1][0] = 1
#print(dp[0])

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

  #print(dp[i])
print(dp[l-1][0][K]+dp[l-1][1][K])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def per(n, r, mod=10**9+7):  # 順列数
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per


def com(n, r, mod=10**9+7):  # 組み合わせ数
    bunshi = per(n, r, mod)
    bunbo = 1
    for i in range(1, r+1):
        bunbo = bunbo*i % mod
    return bunshi*pow(bunbo, -1, mod) % mod


def main():
    n = list(map(int, list(input())))
    k = int(input())
    keta = len(n)
    count = [n[0]-1+com(keta-1, 1)*9, (n[0]-1)*com(keta-1, 1)*9+com(keta-1, 2)
             * 9**2, (n[0]-1)*com(keta-1, 2)*9**2+com(keta-1, 3)*9**3]
    nonzero = 1
    #print(count)
    for i in range(1, keta):
        if n[i] != 0:
            nonzero+=1
            if nonzero==2:
                count[1]+=(n[i]-1)+com(keta-i-1,1)*9
                count[2]+=(keta-i-1)*(n[i]-1)*9+com(keta-i-1,2)*9**2
            elif nonzero==3:
                count[2]+=(n[i]-1)+com(keta-i-1,1)*9
        #print(count)
    print(count[k-1]+(nonzero>=k))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
s = "0" + str(N)
n = len(str(N))
K = int(input())

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

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

        dp[i][1][k] += 9 * dp[i-1][1][k-1]
        dp[i][1][k] += dp[i-1][1][k]

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

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
l = len(str(N))
ans = 0

def neq(n):
    r = 0
    for i in range(10**(len(str(n))-1),n+1):
        ml = 1
        for j in range(len(str(n))):
            ml *= int(str(i)[j])
        if ml != 0:
            r += 1
    return(r)

if l == K:
    print(neq(N))

elif K == 3:
    for i in range(l-2):
        for j in range(i+1,l-1):
            for k in range(j+1,l):
                if i == 0:
                    ans += (int(str(N)[0])-1)*9**2
                    if int(str(N)[1:max(j,2)])>0 and j != 1:
                        ans += 9**2
                    else:
                        if int(str(N)[j+1:max(k,j+2)])>0 and k != j+1:
                                ans += int(str(N)[j])*9
                        else:
                            if int(str(N)[j])*int(str(N)[k]) != 0:
                                ans += neq(int(str(N)[j])*10+int(str(N)[k]))
                            
                else:
                    ans += 9**3
    print(ans)

elif K == 2:
    for i in range(l-1):
        for j in range(i+1,l):
            if i == 0:
                ans += (int(str(N)[0])-1)*9
                if int(str(N)[1:max(j,2)])>0 and j != 1:
                        ans += 9
                else:
                    ans += int(str(N)[j])

            else:
                ans  += 9**2
    print(ans)

else:
    for i in range(l):
        if i == 0:
            ans += int(str(N)[0])
        else:
            ans += 9
    print(ans)

Submission status: Accepted

Solution code:
N=list(map(int,input()))
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(4)] for _ in range(2)]
dp[0][0][0] = 1
for i in range(2):
    for j in range(4):
        for k in range(L):
            for d in range(10 if i else N[k]+1):
                fl = 1 if i == 1 or d < N[k] else 0
                cnt = j+1 if d != 0 else j
                if cnt > K:
                    continue
                dp[fl][cnt][k+1] += dp[i][j][k]
print(dp[0][K][L]+dp[1][K][L])

Submission status: Accepted

Solution code:
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k == 0: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ
        else: # k >= 1
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]

#print(dp)
print(dp[m][0][K] + dp[m][1][K])

Submission status: Accepted

Solution code:
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k -1 >= 0:
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ

#print(dp)
print(dp[m][0][K] + dp[m][1][K])

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
def main(N,K):
  ans=0
  if N<=100+10**6:
    for i in range(1,N+1):
      a=str(i)
      if len(a)-list(a).count("0")==K:
        ans+=1
    return ans
  L=list(map(int,list(str(N))))
  ans=0
  L=list(map(int,list(str(N))))
  if K==1:#おけ
    return (len(str(N))-1)*9+int(str(N)[0])
  elif K==2:#おけ
    for i in range(len(L)-1):
      ans+=(9*(int(str(N)[0])-1))
      for j in range(i+1,len(L)):
        if i==0:
          if j==1:
            ans+=int(str(N)[1])
          else:
            ans+=9
        else:
          ans+=81
    return ans
  else:
    le=len(L)
    for i in range(le-2):
      for j in range(i+1,le-1):
        for k in range(j+1,le):
          if i==0:
            ans+=81*(int(str(N)[0])-1)
            if j==1:
              ans+=9*(int(str(N)[1])-1)
              if k==2:
                ans+=int(str(N)[2])
              else:
                ans+=9
            else:
              ans+=81
          else:
            ans+=729
    return ans
ans2=0
L=list(str(n))
a=len(L)
for i in range(a):
  L=list(str(n))
  s=L[:a-i-1]
  t=L[a-i-1:]
  t=int("".join(t))
  p=s.count("0")
  p=len(s)-p
  if p>k:
    n-=t+1
  elif p==k:
    n-=t+1
    ans2+=1
  else:
    ans2+=main(t,k-p)
    n-=t+1
print(ans2)

Submission status: Accepted

Solution code:
n = list(map(int, list(input())))
k = int(input())

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

Submission status: Accepted

Solution code:
n = list(map(int, list(input())))
k = int(input())

dp0 = [[0]*3]*len(n)
dp1 = [[0]*3]*len(n)
dp0[0][0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    if n[i]==0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = [0]+dp0[i-1][:2]

    dp1[i] = [
        dp1[i-1][0]+dp0[i-1][0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[i-1][1]*(n[i]!=0)+dp0[i-1][0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[i-1][2]*(n[i]!=0)+dp0[i-1][1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]

print(dp0[-1][k-1]+dp1[-1][k-1])

Submission status: Accepted

Solution code:
import functools
import sys


@functools.lru_cache(None)
def doit(n, k):
    if len(n) == 0 or k < 0:
        return k == 0
    d = int(n[0])
    return sum(doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k) for i in range(d + 1))


sys.setrecursionlimit(404)
print(doit(input(), int(input())))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(303)


def doit(n, k, m):
    if len(n) == 0 or k < 0:
        return k == 0
    if (n, k) not in m:
        d = int(n[0])
        m[(n, k)] = sum(doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k, m) for i in range(d + 1))
    return m[(n, k)]


print(doit(input(), int(input()), {}))