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 sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
tmpn=int(str(n)[:k]+("0"*(len(str(n))-k)))
# print(tmpn)
if k==2 and n<11:
    print(0)
    quit()
if k==3 and n<111:
    print(0)
    quit()

ans=0
def combinations_count(n, r):
    if n<=0 or r<=0 or n-r<=0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if k==1:
    ans+=int(str(n)[:k])
    ans+=(keta-1)*9
if k==2:
    ans+=int(str(n)[1])+(int(str(n)[0])-1)*9
    # print(ans)
    ans+=int(str(n)[0])*(keta-2)*9
    # print(ans)
    ans+=combinations_count(keta-1,k)*81
if k==3:
    ans+=int(str(n)[2])+(int(str(n)[1])-1)*9+(int(str(n)[0])-1)*81
    ans+=int(str(n)[0])*int(str(n)[1])*(keta-k)*9
    ans+=int(str(n)[0])*combinations_count(keta-2,2)*81
    ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
l = len(N)
if K == 1:
    a = int(N[0])
    ans1 = 9*(l-1)+a
if K == 2:
    a=int(N[0])
    ans2 =(a-1)*9*(l-1)
    state = 0
    for n in N[1:]:
        if state:
            ans2 += 9
            continue
        if int(n) != 0:
            state = 1
        n = int(n)
        ans2 += n
    for i in range(2,l):
        ans2 += 81*(i-1)
if K == 3:
    a = int(N[0])
    ans3 = (a-1)*81*(l-1)*(l-2)/2
    state = 0
    for i in range(1,l):
        n = int(N[i])
        if state:
            ans3 += 81*(l-i-1)
            continue
        if n !=0:
            state = 1
        else:
            continue
        State = 0
        for j in range(i+1,l):
            m = int(N[j])
            if State:
                ans3 += n*9
                continue
            if m != 0:
                State = 1
            ans3 += n*m
    for i in range(3,l):
        ans3 += 729*(i-1)*(i-2)/2
if K == 1:
    print(ans1)
if K == 2:
    print(int(ans2))
if K == 3:
    print(int(ans3))

Submission status: Wrong Answer

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

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

ans = 0
if len(n) == k:
    ans +=1

for i in range(len(n)):
    if len(n)-i > k:
        ans += calc(i, k)
    k -= 1
    if k < 0:
        break
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)

print(ans)

Submission status: Wrong Answer

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

dp = [[[0,0] for i in range(len(n)+1)] for j in range(len(n)+1)]

# print(dp)
num_d = len(n)

dp[0][0][0] = 1

for i in range(len(n)):
    num = int(n[i])

    if num == 0:
        for j in range(num_d):
            dp[i+1][j+1][0] = dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][1]

        for j in range(num_d+1):
            dp[i+1][j][1] += dp[i][j][1]*9

    else:
        for j in range(num_d):
            dp[i+1][j][0] = dp[i][j][0]

        for j in range(num_d+1):
            dp[i+1][j][1] += dp[i][j][0]*(num-1)
            dp[i+1][j][1] += dp[i][j][1]*9

        for j in range(num_d):
            dp[i+1][j+1][1] += dp[i][j][0] + dp[i][j][1]

# print(dp[-1])
print(sum(dp[-1][num_d-k]))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def main():
    N = list(map(int, input()))
    K = int(input())
    A = len(N)
    if A < K:
        return 0
    if K == 1:
        return N[0] + 9 * (A - 1)
    if K == 2:
        t = 9 * 9 * (A - 1) * (A - 2) // 2
        t += (N[0] - 1) * 9 + N[1] + (A - 2) * N[0] * 9
        return t
    if K == 3:
        t = 9 * 9 * 9 * (A - 1) * (A - 2) * (A - 3) // 6
        t += (N[0] - 1) * 9 * 9 * (A - 2) + (N[1] - 1) * 9 * (A - 2) + 9 * (A - 3) + N[2]
        for i, j in combinations(N[2:], 2):
            t += N[0] * 9 * 9
        return t

    

print(main())

Submission status: Wrong Answer

Solution code:
def comb(n,k):
    if k==0:
        return 1
    elif k==1:
        return n
    elif k==2:
        return n*(n-1)/2

n = input()
k = int(input())
ans=0
for dgt in range(1,len(n)):
    if dgt<len(n):
        ans+=9**k*comb(dgt-1,k-1)
dgt=len(n)
cnt=0
for i in range(len(n)):
    if n[i] != '0' and cnt<k:
        cnt+=1
        ans+=(int(n[i])-1)*9**(k-cnt)*comb(dgt-i-1, k-cnt)
        if i:
            ans+=9**(k-cnt+1)*comb(dgt-i-1, k-cnt+1)

ans+=1
print(int(ans))

Submission status: Wrong Answer

Solution code:
def main():
    NOT_DET = 0
    SMALLER = 1

    s = input()
    n = len(s)  # 桁数

    k = int(input())

    dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
    # dp[上から何桁決めたか][0でない数字の個数][smaller=1]
    dp[0][0][0] = 1

    for i, ci in enumerate(s):
        for j in range(k + 1):
            dp[i + 1][j][SMALLER] = (
                    dp[i][j][SMALLER]
                    + dp[i][j][NOT_DET] * (1 if ci != '0' else 0)
                    + (dp[i][j - 1][SMALLER] if j > 0 else 0) * 9
                    + (dp[i][j - 1][NOT_DET] if j > 0 else 0) * (int(ci) - 1)
            )

            dp[i + 1][j][NOT_DET] = dp[i][j][NOT_DET] if ci == '0' else (
                dp[i][j - 1][NOT_DET] if j > 0 else 0)

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


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def countInRangeUtil(pos, cnt, tight, num): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt <= K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x): 
    global dp, K, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  
dp = [] 
M = 100
R = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
K = 3
a = countInRange(R)

dp = [] 
M = 100
R = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
K = 2
b = countInRange(R)

print(a - b)

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
m = len(n)
if k == 1:
    print(int(n[0])+9*(m-1))
elif k == 2:
    if m<2:ans = 0
    else:
        ans = 81*(m-1)*(m-2)//2
        ans += (int(n[0])-1)*(m-1)*9+int(n[1])+(m-2)*9
    print(ans)
else:
    if m<3:ans = 0
    else:
        ans1 = (m-1)*(m-2)*(m-3)//6*9**3
        ans2=(int(n[0])-1)*(m-1)*(m-2)//2*81
        ans3 =(m-2)*(m-3)//2*81
        ans = ans1+ans2+ans3
        if int(n[1]) > 0:
            ans += (int(n[1])-1)*(m-2)*9 + (m-3)*9+int(n[2])
    print(ans)

Submission status: Wrong Answer

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

k = len(N)
ans = 0

if k < K:
    print(0)
    exit()


def solve(N,K):
    if K == 1:
        return (len(N)-1)*9+int(N[0])
    res = 0
    if K == 2:
        res += (9**2)*(len(N)-1)*(len(N)-2)//2
        res += 9*(len(N)-1)*(int(N[0])-1)
        res += solve(N[1:],K-1)
    if K == 3:
        res += (9**3)*(len(N)-1)*(len(N)-2)*(len(N)-3)//6
        res += (9**2)*(len(N)-1)*(len(N)-2)//2*(int(N[0])-1)
        res += solve(N[1:],K-1)
    return res


print(solve(N,K))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


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

def solve(S: str, K: int):
    N = len(S)
    if N < K:
        print(0)
        return 0
    ret = comb(N, K) * (9 ** K)
    #print(ret)
    for i in range(min(N, K)):
        h = int(S[i])
        ret -= (9 - h) * comb(N - i - 1, K - i - 1) * (9 ** (K - i - 1))
        ret = max(0, ret)
        #print(h, ret)
    print(ret)
    return

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


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

def solve(S: str, K: int):
    N = len(S)
    ret = comb(N, K) * (9 ** K)
    for i in range(min(N, K)):
        h = int(S[i])
        ret -= (9 - h) * comb(N - i - 1, K - i - 1) * (9 ** (K - i - 1))
    print(ret)
    return

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

Submission status: Wrong Answer

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

def f(N,K):
    if K==0: return 1
    if N=="": return 0
    l = len(N)
    n0 = int(N[0])
    return f(N[1:],K-1) + f("9"*(l-1),K-1)*(n0-1) + f("9"*(l-1),K)

print(f(N,K))

Submission status: Wrong Answer

Solution code:
N = input()
A = [x for x in input().split()]
if len(A) == len(set(A)):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = input().rstrip('\n')
    L = len(N)
    K = int(input())

    dp0 = [[0] * (K+1) for _ in range(L+1)]
    dp1 = [[0] * (K+1) for _ in range(L+1)]
    dp0[0][0] = 1
    for i in range(L):
        for k in range(K+1):
            m = int(N[i])
            if m == 0:
                dp0[i+1][k] += dp0[i][k]
                dp1[i+1][k] += dp1[i][k]
            else:
                dp1[i+1][k] += dp0[i][k] + dp1[i][k]
            if k+1 <= K:
                if m != 0:
                    dp0[i+1][k+1] += dp0[i][k]
                    dp1[i+1][k+1] += dp0[i][k] * (m-1) + dp1[i][k] * 9
                else:
                    dp1[i + 1][k + 1] += dp0[i][k] * (m - 1) + dp1[i][k] * 9
    print(dp0[-1][-1] + dp1[-1][-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N=[int(x) for x in list(input())]
    k=int(input())
    digit=len(N)
    DP=[[[0]*(digit+1) for _ in range(2)] for _ in range(digit+1)] #DP[上からd桁][less][0の個数]
    DP[0][0][0]=1
    for d in range(digit):
        for less in range(2):
            for num in range(digit):
                limit=9 if less else N[d]
                for l in range(limit+1):
                    DP[d+1][less or l<limit][num+(l==0)]+=DP[d][less][num]
    print(DP[-1][0][digit-k]+DP[-1][1][digit-k])
    #print(DP)
    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# 90分かけて書いたTLE解法を供養

import heapq
# import sys

# Nは文字列のまま持つ
N = input()
K = int(input())

# K が小さいのがポイントだと思う。
# dpっぽさを感じている。
# O(N)だとあふれるので、桁数についての何を行ってO(logN)にしたい

# K = 1のとき
# 1桁について、1~9の9個
# 2桁について、10~90の9個
# 3桁について、100~900の9個

# K = 2のとき
# 1桁について、0個
# 2桁について、出てくる数字はa, b 9*8=72個
# 3桁について、出てくる数字はa, b, 0。 9 * 8 = 72個に対して、ゼロを末尾に入れるか2ケタ目に入れるかで*2。9 * 8 * 2
# 4桁について、出てくる数字はa, b, 0。 9 * 8 = 72個に対して、bを1~3桁目のどこに置くかで * 3

# K = 3のとき
# 1桁について、0個
# 2桁について、0個
# 3桁について、出てくる数字はa, b, c。 9 * 8 * 7
# 4桁について、出てくる数字はa, b, c, 0。 9 * 8 * 7 = 72*7個に対して、b,cを1~3桁目のどこに置くか 3C2
# 5桁について、出てくる数字はa, b, c, 0。 9 * 8 * 7 = 72*7個に対して、b,cを1~4桁目のどこに置くか 4C2

# ある程度までは上記の考えで進めることができるが、Nが中途半端な位置の時にどう打ち切るかが困る

# queueに突っ込んで小さい順に生成できないか?

# K = 1 のとき
# 1,2,...9,10,20,30...90, 100 ...
# なので、「取り出して、末尾に0をつけてキューに入れる」でFA

# K = 2 のとき
# 12, 13, ... 19, 21, 23, ...29, ... 98の 9*8 = 72通り
# 12と13を比較した時に、そこから生成したいのは、120, 102, 103, 130
# 102 103 というふうに交差している

# 制約の範囲で求める個数は高々117879300=10^8だし、Priority QueueでO(logN)で処理できそう
# あとは、10^100の整数をPythonが高速に扱えるかどうかの問題


# 整数に変換すると遅くなるので、文字列のままで数値としての大小を判定する
# だめだ、is_smaller()という判定方法そのものをheapqに渡すことはできない
# なので、heapqに入れる値は、(桁数, 文字列)として、まず桁数が小さいものが優先されるようにする
# def is_smaller(s1, s2):
#     if len(s1) != len(s2):
#         return len(s1) < len(s2)

#     return s1 < s2


# 初期化フェーズ
# 解き始めてから80分間、ゼロでない「異なる数字」と勘違いしてた…
# 何を使ったかを記憶しておく必要が無いならもっと簡単に解けたかもしれない…
# h = []
# if K == 1:
#     for i in range(1,10):
#         tpl = (1, str(i))
#         heapq.heappush(h, tpl)

# if K == 2:
#     for i in range(1,10):
#         for j in range(1,10):
#             if i == j:
#                 continue

#             val = i * 10 + j
#             tpl = (2, str(val))
#             heapq.heappush(h, tpl)

# if K == 3:
#     for i in range(1,10):
#         for j in range(1,10):
#             if i == j:
#                 continue

#             for k in range(1,10):
#                 if i == k or j == k:
#                     continue

#                 val = i * 100 + j * 10 + k
#                 tpl = (3, str(val))
#                 heapq.heappush(h, tpl)

h = []
if K == 1:
    for i in range(1,10):
        tpl = (1, str(i))
        heapq.heappush(h, tpl)

if K == 2:
    for i in range(1,10):
        for j in range(1,10):
            val = i * 10 + j
            tpl = (2, str(val))
            heapq.heappush(h, tpl)

if K == 3:
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                val = i * 100 + j * 10 + k
                tpl = (3, str(val))
                heapq.heappush(h, tpl)

ans = 0
max_digit = len(N)

# 同じ値が複数の挿入で生成されうるので、取り出したことがある数値の最大値を持っておいてスキップ判定に使う
max_popped = (0, '')

while len(h) > 0:
    # h[0] を 答えとして採用
    digit, a = heapq.heappop(h)
    if digit > max_digit or (digit == max_digit and a > N):
        break

    # もう見た
    if (digit, a) <= max_popped:
        continue
    max_popped = (digit, a)

    # sys.stderr.write("popped: {}\n".format(a))
    ans += 1

    # h[0]のどこかに0を挿入して新しい数を作り、queueに投入
    # 10に[0]を挿入する際に1[0]0も10[0]も100になるので、ここでuniqしておく
    new_set = set()
    for i in range(1, len(a)+1):
        new_s = "{}0{}".format(a[:i], a[i:])
        new_set.add(new_s)

    for new_val in new_set:
        tpl = (digit + 1, new_val)
        # sys.stderr.write("pushed: {}\n".format(new_val))
        heapq.heappush(h, tpl)

    # sys.stderr.write("---\n")


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
str_n = input()
n = int(str_n)
k = int(input())

def dfs(A,rest):
    if int(A) <= n and rest == 0:
        num = 1
    elif int(A) <= n:
        num = 0
    else:
        return 0

    if rest == 0:
        num += dfs(A+'0',0)
    else:
        for new in range(10):
            if new == 0:
                num += dfs(A+str(new),rest)
            else:
                num += dfs(A+str(new),rest-1)

    return num

ans = 0
for i in range(1,10):
    ans += dfs(str(i),k-1)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())

def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N = int(input())
K = int(input())
DP = [[0] * (K * 10) for _ in range(N * 10)]

@lru_cache(None)
def calc(a, b):
    assert a >= 0
    if a < 10:
        if b == 0:
            return 1
        if b == 1:
            return a
        else:
            return 0
    if DP[a][b] != 0:
        return DP[a][b]
    x = a % 10
    ans = 0
    if b >= 1:
        ans = x * calc(a // 10, b - 1) + (9 - x) * calc(a // 10 - 1, b - 1)
    ans += calc(a//10, b)
    DP[a][b] = ans
    return ans

print(calc(N, K))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
k = int(input())
def dfs(s, count):
    global ans
    if int(s) > n:
        return
    if count == 0:
        ans += 1
        dfs(s + "0", count)
    else:
        dfs(s + "0", count)
        count -= 1
        for i in range(1, 10):
            dfs(s + str(i), count)
ans = 0
for i in range(1,10):
    dfs(str(i), k-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(s,x):
    global ans
    if 1 <= s <= n and x == k:
        ans += 1
    elif s > n:
        return s
    if x < k:
        for i in range(1,10):
            nexts = s*10 + i
            f(nexts,x+1)
    if s != 0:
        nexts = s*10
        f(nexts,x)
    return s
ans = 0
n = int(input())
k = int(input())
f(0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
        else:
            ans=0
        if l-1>=nextK:
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        return ans
ans=solve(N,K)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        else:
            return 0
ans=solve(N,K)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import queue
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

n = readInt()
k = readInt()

arr = [[1,2,3,4,5,6,7,8,9]]
two = []
for i in range(1,10):
	for j in range(1,10):
		two.append(int(str(i)+str(j)))
arr.append(two)
thr = []
for i in range(1,10):
	for j in range(1,10):
		for l in range(1,10):
			thr.append(int(str(i)+str(j)+str(l)))
arr.append(thr)


ans = 0
tar = arr[k-1]
l = len(tar)
ten = 1
tenb = 0

while ten*tar[-1]<n:
	ans+=l*comb(k-1+tenb,k-1)
	ten*=10
	tenb+=1

for i in range(ten*10**(k-1),ten*10**k):
	if i>n:
		break
	#print(i,len(str(i))-list(str(i)).count("0"))
	if len(str(i))-list(str(i)).count("0")==k:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    K = int(input())
    num = []
    dfs(0,0,num,N,K)
    print(len(num))

def dfs(now,cnt,lst,N,K):
    if now > N:
        return
    
    if cnt == K:
        lst.append(now)
    
    for i in range(10):
        next = now * 10 + i
        if i == 0:
            if now == 0:
                continue
            dfs(next,cnt,lst,N,K)
        else:
            dfs(next,cnt+1,lst,N,K)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# ABC154E

def f(n, k):
    count = 0
    for i in range(1, n+1):
        s = str(i)
        count_not_zero = 0
        for j in s:
            if j != '0':
                count_not_zero += 1
            if count_not_zero > k:
                break
        else:
            if count_not_zero == k:
                count += 1
    print(count)


n = int(input())
k = int(input())
f(n, k)

Submission status: Time Limit Exceeded

Solution code:
i1 = input()
i2 = input()
num = int(i2)
st = ''
for n in range(0 ,int(i2)):
    st += '1'
st_n = int(st)
    
c = 0
for n in range(st_n, int(i1)+1):
    st = str(n)
    st_sp = st.split('0')
    if((len(st)-len(st_sp)+1)==num):
        c+=1
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
def f(n, k):
    count = 0
    for i in range(1, n+1):
        s = str(i)
        count_not_zero = 0
        for j in s:
            if j != '0':
                count_not_zero += 1
            if count_not_zero > k:
                break
        else:
            if count_not_zero == k:
                count += 1
    print(count)


n = int(input())
k = int(input())
f(n, k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
K = int(input())
list_N = []
for i in range(N):
    list_N.append(str(i+1))
list_N_n=[]
count=0
for i in range(len(list_N)):
    a=0
    for j in range(len(list_N[i])):
        if not list_N[i][j]=="0":
            a+=1
    if a == K:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

temp_dict = {}
for i in range(1, k + 1):
    temp_dict[i] = []

flag = True
d = 0
while flag:
    base = 10 ** d
    for i in range(1, 10):
        num = i * base
        if num > n:
            flag = False
            break
        temp_dict[1].append(num)

        for j in range(1, k):
            l = bisect_left(temp_dict[j], base)
            temp_list = [num + temp for temp in temp_dict[j][:l] if num + temp <= n]
            temp_dict[j + 1].extend(temp_list)
    d += 1

ans = len(temp_dict[k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
n=int(input())
k=int(input())
def comb(n,k):
    return len(list(itertools.combinations(range(n), k)))
x=str(n)
m=len(x)
ans=0
for i in range(1,m):
    ans+=(comb(i-1,k-1)*(9**k))
if k==1:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            ans+=1
elif k==2:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        ans+=1
                    else:
                        break
        else:
            break
else:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        for b in range(j):
                            for c in range(1,10):
                                if i*(10**(m-1))+a*(10**(j))+c*(10**(b))<=n:
                                    ans+=1
                                else:
                                    break
                    else:
                        break
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product
from math import factorial

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

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else (nCr(size - 1, k) * (9 ** k))
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  for digits in combinations(range(size - 1), k - 1):
    digits = [size - 1] + list(digits)
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n
      for nums in product(range(1, 10), repeat=k)
    )
print(count)

Submission status: Time Limit Exceeded

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

sum=0
for i in range(1,n+1):
    a=list(str(i))
    b=(math.log(i,10)//1)
    if a.count('0')==(b+1-k):
        sum+=1

print(sum)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(1, n+1):
    if len(str(i).replace('0', '')) == k:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

l1 = []
for i in range(1, n+1):
    if len(str(i).replace('0', '')) == k:
        l1.append(i)
print(len(l1))

Submission status: Time Limit Exceeded

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

def choose(n,r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x *= (n - i + 1)
        y *= i
    return int(x / y)

keta = len(str(n))
ans = 0
ans += choose(keta-1, k) * pow(9, k)
for i in range(10**(keta-1), n + 1):
    str_i = str(i)
    if len(str_i) - str_i.count('0') == k:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=input()
K=input()
list=[]
#mist=[]
nist=[]
for i in range(int(N)):
    list.append(str(i+1))
import re
for i in range(int(N)):
#    mist.append('0')
    nist.append('A')
#    j=re.search('0',list[i])
#    if j!=None:
        #文字列.replace('変換元','変換後')
#        mist[i]=list[i].replace('0','A')
for i in range(int(N)):
    nist[i]=len(list[i])-list[i].count('0')
judge=0
for i in range(int(N)):
    if nist[i]==int(K):
        judge+=1
print(judge)

Submission status: Time Limit Exceeded

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

total_count = 0

for i in range(n):
    count = 0
    tmp = i + 1
    # print("i = {}".format(i + 1))
    while tmp >= 1:
        if (tmp % 10 != 0):
            count = count + 1
        tmp = tmp // 10
    if (count == k):
        total_count = total_count + 1

print(total_count)

Submission status: Time Limit Exceeded

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


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