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

sys.setrecursionlimit(10 ** 7)


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

ans = 0

if K == 1:
    c = 10
    # 桁ごと
    while N >= c:
        ans += 9
        c *= 10

    # あまり
    ans += int(str(N)[0])

elif K == 2:
    i = 2
    c = 100

    if N < 11:
        print(0)
        exit()

    # 桁毎
    while N >= c:
        ans += 9 * (i - 1) * 9
        i += 1
        c *= 10

    print(ans)

    # あまり
    l = len(str(N))
    d1 = int(str(N)[0])
    d2 = int(str(N)[1])

    # 1桁目 1 - d1-1
    if d1 > 0:
        ans += (d1 - 1) * (l - 1) * 9

    # 1桁目 d1
    # 2桁目 0
    if l > 2:
        ans += (l - 2) * 9

    # 2桁目 1-d2
    ans += d2


elif K == 3:
    i = 3
    c = 1000

    if N < 111:
        print(0)
        exit()

    # 桁毎
    while N >= c:
        ans += 9 * ((i-1) * (i-2) // 2) * 9 * 9
        i += 1
        c *= 10

    # あまり
    l = len(str(N))
    d1 = int(str(N)[0])
    d2 = int(str(N)[1])
    d3 = int(str(N)[2])

    # 1桁目 1 - d1-1
    if d1 > 0:
        ans += (d1 - 1) * ((l - 1) * (l - 2) // 2) * 9 * 9

    # 1桁目 d1
    # 2桁目 0
    if l > 3:
        ans += ((l - 2) * (l-3) // 2) * 9 * 9

    # 2桁目 1 - d2-1
    if d2 >= 1:
        ans += (d2 - 1) * (l - 2) * 9

    # 2桁目 d2
    # 3桁目 0
    if l > 3:
        ans += (l - 2) * 9

    # 3桁目 1-d3
    #ans += d3


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
from itertools import combinations

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


    a=list(range(0, 100))
    t=0

    if k==3:
        xx = combinations(a, k)
        for p in xx:
            if 0:
                continue
            elif 0:
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                        for k in range(1,10):
                            if n>=(10**p[0]*i+10**p[1]*j+10**p[2]*k):
                                t+=1
    elif k==2:
        xx = combinations(a, k)
        for p in xx:
            if 0:
                continue
            elif 0:
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                            if n>=(10**p[0]*i+10**p[1]*j):
                                t+=1
    elif k==1:
        xx = combinations(a, k)
        for p in xx:
            if 0:
                continue
            elif 0:
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                            if n>=(10**p[0]*i):
                                t+=1


    print(t)

    return

resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 4 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
    for smaller in range(2):
        for j in range(3):
            for x in range((9 if smaller else n[i]) + 1):
                dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])

Submission status: Wrong Answer

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

N = str(N)
N_keta = len(N)
p = N[0]

if K == 1:
    kotae = int(p) + 9 * (int(N_keta)-1)
    print(int(kotae))

else:
    M = int(N) - int(p)*(10**(int(N_keta)-1))
    M = str(M)
    M_keta = len(M)
    q = M[0]
    if K == 2:
        if int(N) <= 9:
            print(0)
        else:
            kotae = 9 * (int(N_keta)-1) * (int(p)-1) + int(q) + 9 * (int(M_keta)-1) + (int(N_keta)-1)*(int(N_keta)-2)*40.5
            print(int(kotae))
    else:
        if int(N) <= 99:
            print(0)
        else:
             L = int(M) - int(q)*(10**(int(M_keta)-1))
             L = str(L)
             L_keta = len(L)
             r = L[0]
             kotae = 9 * (int(M_keta)-1) * (int(q)-1) + int(r) + 9 * (int(L_keta)-1) + (int(p)-1)*(int(N_keta)-1)*(int(N_keta)-2)*0.5*81+(int(N_keta)-1)*(int(N_keta)-2)*(int(N_keta)-3)*121.5
             print(int(kotae))

Submission status: Wrong Answer

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

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	K = int(input())
	dig = len(str(N))
	ans = 0
	if K == 1:
		ans = 9 * (dig - 1) + int(str(N)[0])
	elif K == 2:
		if dig < K:
			ans = 0
		elif dig == K:
			ans = (int(str(N)[0]) - 1) * 9 + int(str(N)[1])
		else:
			a1 = (9 ** K) * combi(dig-1, K) # 0***
			a2 = (int(str(N)[0])-1) * (9 ** (K-1)) * combi(dig-1, K-1)
			a3 = 9 * combi(dig-2, K-1)
			a4 = int(str(N)[1]) * combi(dig-2, K-2)
			ans = a1 + a2 + a3 + a4
	else:
		if dig < K:
			ans = 0
		elif dig == K:
			a1 = (int(str(N)[0])-1) * (9 ** 2)
			a2 = (int(str(N)[1])-1) * 9
			a3 = int(str(N)[2])
			ans = a1 + a2 + a3
		else:
			a1 = (9 ** K) * combi(dig-1, K) # 0***
			a2 = (int(str(N)[0])-1) * (9 ** (K-1)) * combi(dig-1, K-1)
			a3 = (9 ** (K-1)) * combi(dig-2, K-1)
			a4 = (int(str(N)[1]) - 1) * 9 * combi(dig-2, K-2)
			a5 = 9 * (dig-3)
			a6 = int(str(N)[2])
			ans = a1 + a2 + a3 + a4 + a5 + a6

	print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	K = II()

	def comb(n, r):
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
	digits = len(str(N))
	ans = 0
	if(digits < K):
		print(0)
	else:
		for i in range(digits-1, K-1, -1):
			ans += comb(i-1,K-1) * (9**K)
		for i in range(0,K):
			a = int(str(N)[i])
			if(i==0 and a!=0):
				ans += comb(digits-i-1,K-i-1) * (9**(K-1-i)) * (a-1)
			elif(a!=0):
				ans += comb(digits-i-1,K-i-1) * (9**(K-1-i)) * (a-1)
				if(digits-1-i>=K-i):
					ans += comb(digits-i-1,K-i) * (9**(K-i))
		cnt = 0
		if(cnt==K):ans+=1
		if(K<digits):ans+=1
		print(ans)


main()

Submission status: Wrong Answer

Solution code:
# ABC154e


def main():
    import sys
    import math
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)
    MOD=10**9+7
    # 再帰関数を使わない限りPypyで出すこと

    n = int(input())
    ns = str(n)
    k = int(input())
    keta = len(ns)
    # dp[i+1][smaller][j]=i桁目までで、未満フラグをsmaller、0の個数j
    dp = [[[0]*(keta+1) for i in range(2)]
          for j in range(keta + 1)]

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

    for i in range(keta):
        for smaller in range(2):
            for j in range(i+1):
                for x in range(10 if smaller == 1 else int(ns[i])+1):
                    # if i == 0 and x == 0:
                    #    continue
                    dp[i + 1][1 if smaller == 1 or x < int(ns[i])
                              else 0][j if x != 0 else j+1] += dp[i][smaller][j]
    # print(dp)
    # print(dp[keta][0][keta-k])
    #print(dp[keta][1][keta - k])
    print(dp[keta][0][keta-k]+dp[keta][1][keta - k]%MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
keta = len(str(N))

def kosu(p):
  if p == 1:
    answer = [9, 0, 0]
  elif p == 2:
    answer = [9, 81, 0]
  elif p == 3:
    answer = [9, 162, 729]
  else:
    k1 = 9
    k2 = (9 ** 2) * (p - 1)
    k3 = int((9 ** 3) * (p - 1) * (p - 2) / 2)
    answer = [k1, k2, k3]
  return answer

if keta == 1:
  print(N)
  quit()
  
ans = 0  
for i in range(1, keta):
  ans += kosu(i)[K - 1]

#print(ans)  
if K == 1:
  ans += int(str(N)[0])
elif K == 2:
  y = 0
  i = 1
  while y == 0:
    if int(str(N)[i]) != 0:
      y = i
      ans += int(str(N)[i]) + 9 * (keta -y - 1)
    i += 1
    if i == keta:
      y = keta
    
  #print(x)
  ans += (int(str(N)[0]) - 1) * 9 * (keta - 1)
  
else:
  if keta >= 3:
    ans += int((int(str(N)[0]) - 1) * (9 ** 2) * (keta - 1) * (keta - 2) / 2)
    #print(ans)
    x = 0
    i = 1
    while x <= 1:
      if int(str(N)[i]) != 0:
        x += 1
        if x == 1:
          ans += (int(str(N)[i]) - 1) * (9 * (keta - i - 1))
          if i <= keta - 3:
            ans += (9 ** 2) * (keta - i - 1) * (keta - i - 2) / 2
        else:# x = 2
          ans += int(str(N)[i]) + 9 * (keta - i - 1)
      i += 1
      if (i == keta - 1) and (x == 0):
        x = 2
      if i == keta:
        x = 2
        

print(int(ans))

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = input()
n = len(N)
K = int(input())
ans = 0
if K == 1:
    for i in range(n):
        a = int(N[i])
        if i == 0:
            ans+=a
        else:
            ans+=9
    if ans <=0:
        ans = 0
    print(ans)
    exit()
if K == 2:
    for i in range(n-1):
        for j in range(i+1,n):
            a = int(N[i])
            b = int(N[j])
            if i == 0:
                if j == 1:
                    ans+= b + (a-1) * 9
                elif int(N[j-1])==0:
                    ans+= b + (a-1)*9
                else:
                    ans+=a * 9
            else:
                ans += 9**2
    if ans <=0:
        ans=0
    print(ans)
    exit()
if K == 3:
    for i in range(n-2):
        for j in range(i+1,n-1):
            for k in range(j+1,n):
                a = int(N[i])
                b = int(N[j])
                c = int(N[k])
                if i == 0:
                    if j ==1:
                        ans += (b-1) * 9 + c + (a-1) * 9 * 9
                    elif int(N[j-1]) == 0:
                        ans += (b-1) * 9 + c + (a-1) * 9 * 9
                    else:
                        ans+=a * 9 * 9
                else:
                    ans += 9*9*9
    if ans<=0:
        ans=0
    print(ans)
    exit()

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = [int(x) for x in input()]
    K = int(input())
    dp = np.zeros((len(n)+1, 2, K+1), dtype=int)

    if len(n) < K:
        print(0)
        return

    dp[0, 0, 0] = 1

    for i in range(len(n)):
        for k in range(0, K+1):
            # use 0
            dp[i+1, 1, k] += dp[i, 0, k] + dp[i, 1, k]
            for smaller in [0, 1]:
                # use 1~9
                r = 9 if smaller == 1 else n[i]
                for x in range(1, r+1):
                    # print(i+1, int(smaller==1 or x <n[i]), k+1, x)
                    if k+1 <= K:
                        dp[i+1, int(smaller == 1 or x < n[i]), k+1] += dp[i, smaller, k]
    print(dp[len(n), 0, K] + dp[len(n), 1, K])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    s = input()
    N = int(s)
    K = int(input())
    ans = 0
    d = len(s)
    if d < K:
        print(ans)
        return
    for i in range(1, d):
        if i < K:
            continue
        else:
            if i == 1 and K == 1:
                ans += 9
            elif i == 2 and K == 2:
                ans += 9*9
            elif i == 3 and K == 3:
                ans += 9*9*9
            else:
                if K == 1:
                    ans += 9
                elif K == 2:
                    ans += 9*9*(i-1)
                else:
                    ans += 9*9*9*(i-1)*(i-2)//2
    # print(ans)
    if K == 1:
        ans += int(s[0])
    elif K == 2:
        ans += int(s[1])
        if int(s[0]) > 1:
            ans += (int(s[0])-1)*9
        if d > K:
            ans += int(s[0])*(d-2)*9
    else:
        ans += int(s[2])
        if int(s[1]) > 1:
            ans += (int(s[1])-1)*9
            if int(s[0]) > 1:
                ans += (int(s[0])-1)*9*9
        if d > K:
            ans += int(s[0])*int(s[1])*(d-3)*9*2
            if d > K+1:
                ans += int(s[0])*9*9*(d-3)*(d-4)//2
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
import math

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

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

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

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

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

print(int(ans+t_ans))

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
ans=0
if k == 1 :
    if(len(n)>1):
        for i in range(1,len(n)):
            ans +=9
        print(ans +int(n[0]))
    else:
        print(int(n))

elif k == 2:
    if(len(n) ==1) :
        print(0)
    else:
        for i in range(2,len(n)):
            ans += 9 * (i-1) * 9

        print(ans+int(n[0])*(len(n)-1)*9)

else:
    for i in range(3,len(n)):
        ans += 9*81*(i-1)*(i-2)/2
    print(int(ans+(int(n[0])*81*(len(n)-1)*(len(n)-2)) /2))
    

# n,k= map(int, input().split())
# p = list(map(int,input().split()))

# count = 0
# val = sum(p[0:k])
# val_lis = [val]
# mx_val = val
# index = 0
# mx_index = 0
# for i,j in enumerate(p[k:]):
#     val = val - p[index] + j
#     val_lis.append(val)
#     index +=1
#     if val > mx_val:
#         mx_index = index
#         mx_val = val 
    
# ans = 0
# for i in range(k):
#     ans += ((p[mx_index + i]+1.0)*(p[mx_index+i]))/ (p[mx_index+i] *2.0)
# print(ans)  




# h = sorted(h,reverse = True)
# print(sum(h[k:]))

# s,t= map(str, input().split())
# a,b= map(int, input().split())
# u = input()
# print("x"*len(u))

# if(u == s):
#     print(a-1,b)
# else:
#     print(a,b-1)

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())

N_length = len(N)

fi_ans = 0

def one(N_str):
    ans = 0
    length = len(N_str)
    ans += (length-1)*9
    top = int(N_str[0])
    ans += top
    return ans

def two(N_str):
    length = len(N_str)
    ans = 0
    if length == 1:
        ans = 0
    elif length == 2:
        ans += (int(N_str[0])-1)*9
        ans += int(N_str[1])
    else:
        ans += comb(length-1, K) * 9 * 9
        top = int(N_str[0])
        first_n_0 = -1
        for i in range(length-1):
            if int(N_str[i+1]) != 0:
                first_n_0 = i+1
                break
        if 0 < first_n_0:
            ans += (top-1)*(length-1)*9
            ans += one(N_str[first_n_0:])
    return ans

if K == 1:
    fi_ans = one(N)
elif K == 2:
    fi_ans = two(N)
else:
    if N_length < 3:
        fi_ans = 0
    elif N_length == 3:
        fi_ans += (int(N[0])-1) * 9 * 9
        top = int(N[0])
        sec = int(N[1])
        thr = int(N[2])
        if sec != 0:
            fi_ans += (sec - 1) * 9
            fi_ans += thr
    else:
        fi_ans += comb(N_length-1, K) * 9 * 9 * 9
        top = int(N[0])
        first_n_0 = -1
        second_n_0 = -1
        for i in range(N_length-1):
            if int(N[i+1]) != 0:
                if first_n_0 < 0:
                    first_n_0 = i+1
                else:
                    second_n_0 = i+1
                    break
        if 0 < first_n_0 < N_length-1:
            fi_ans += (top-1)*comb(N_length-1, K-1)*9*9
            fi_ans += two(N[first_n_0:])

print(fi_ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n = input()
k = int(input())
ans = 0
li = range(len(n))
if k == 1:
    for x in combinations(li, k):
        if x[0] == len(n)-1:
            ans += int(n[0])
        else:
            ans += 9

elif k == 2:
    for x in combinations(li, k):
        if x[1] != len(n)-1:
            ans += 81
        elif x[1] == len(n)-1 and x[0] == len(n)-2:
            num = int(n[0:2])
            for i in range(1,num+1):
                if '0' not in str(i).zfill(2):
                    ans += 1
        else:
            ans += (int(n[0])) * 9
else:
    for x in combinations(li, k):
        if x[2] != len(n)-1:
            ans += 9**3
        elif x[2] == len(n)-1 and x[1] == len(n)-2 and x[0] == len(n)-3:
            num = int(n[0:3])
            for i in range(1,num+1):
                if '0' not in str(i).zfill(3):
                    ans += 1
        elif x[2] == len(n)-1 and x[1] == len(n)-2:
            num = int(n[0:2])
            for i in range(1, num + 1):
                if '0' not in str(i).zfill(2):
                    ans += 1
        else:
            ans += (int(n[0])) * 9
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
k = ii()
n2 = n

n_keta = 1
while n2:
    n2 = n2 //10
    if n2 == 0:
        break
    n_keta += 1

from math import factorial as fc
def func(keta,kazu,ima):
    ans = 0
    n = n_keta - keta -1
    r =  k - kazu
    if n-r <0:
        return 0
    ans += (ima-1) *fc(n) //fc (r)//fc(n-r)  * (9 **(k-kazu))
    if n - r -1 >= 0: ans += fc(n) // fc (r+1) // fc(n-r-1) *(9**(k-kazu +1))
    return ans
n_in = str(n)
kk = 0
lis = []

for i in range(n_keta):
    if n_in[i] != 0:
        lis.append([i,kk+1,int(n_in[i])]) 
        kk += 1
    if kk ==k:
        break
anss = 0
for lil in lis:
    anss += func(lil[0],lil[1],lil[2])
print(int(anss+1))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def binomial_coefficient(n, r, mod=10**9+7):
    """
    二項係数nCr, (n,r)をmodで除したあまりを返す
    """
    res = 1
    div = 1
    r = min(r, n - r)
    for i in range(r):
        res *= (n - i) % mod
        div *= (i + 1) % mod
    res *= pow(div, mod - 2, mod)
    return res % mod


def calc(N, K):
    if K == 0:
        return 1
    if K > len(N):
        return 0

    res = 0
    # 一番上が0の時

    if len(N)-1 > K:
        res += binomial_coefficient(len(N) - 1, K) * (9 ** K)

    # 一番上が1~N[0]-1の時
    if N[0] != 0:
        res += (int(N[0]) - 1) * (9**(K-1)) * \
            binomial_coefficient(len(N)-1, K-1)

    # 一番上がN[0]のとき
    res += calc(N[1:], K-1)

    return res


if __name__ == "__main__":
    N = int(input())
    K = int(input())
    d = len(str(N))
    N = str(N)
    ans = calc(N, K)
    print(ans)

Submission status: Wrong Answer

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

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

answer=0

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

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

Submission status: Wrong Answer

Solution code:
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod



N = int(input())
K = int(input())
SN = str(N)
LN = list(SN)
keta =len(LN)
Nzer = keta-K
Nsei = K
output = 0
if keta>=K:
    output += comb(keta,K,10**9+7)*9**K
    t = 0
    s = 0
    while (s<=K-1)and(t<=keta-1):
        if LN[t]!="0":
            output -= (9-int(LN[t]))*comb(keta-1-t,K-1-t,10**9+7)*9**(K-1-t)
            t += 1
            s += 1
        elif LN[t]=="0":
            output -= (9-int(LN[t]))*comb(keta-1-t,K-1-t+1,10**9+7)*9**(K-1-t)
            t+=1
print(int(output))

Submission status: Wrong Answer

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

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

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

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

if(ans == 0): print(1)
else: print(ans)

Submission status: Wrong Answer

Solution code:
su = 0
m = int(input())
nonZeros = int(input())
for i in range(1,m +1):
    num = i
    currNonZeros = 0
    while(num!=0):
    	if num % 10 != 0:
   		    currNonZeros += 1
    	num = int(num/10)
    print(currNonZeros)
    if currNonZeros == nonZeros:
    	su += 1
print(su)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def k_1(_n):
    _n_keta = len(str(_n))
    _sub_cnt=(9*(_n_keta-1))
    _top_fig = int(str(_n)[0])
    _sub_cnt+=_top_fig
    return _sub_cnt
def k_2(_n):
    _n_keta = len(str(_n))
    _sub_cnt = 0
    for i in range(2, _n_keta):
        _sub_cnt+=(81*(i-1))
    _top_fig = int(str(_n)[0])
    zan_fig = str(_n)[1:]
    _sub_cnt+=k_1(_n)
    return _sub_cnt


    return _sub_cnt


n = int(input())
k = int(input())
n_keta = len(str(n))
sub_cnt = 0
if k == 1:
    sub_cnt+=k_1(n)
elif k == 2:
    sub_cnt+=k_2(n)

print(sub_cnt)

Submission status: Wrong Answer

Solution code:
import math

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

# 10ごとに 9
# 100ごとに81
# 1000ごとに890


small = 10 ** (k - 1)
if n < small:
    print(0)
    exit()

ans = n / (10 ** 1) * 9 - (9 - int(n / (10 ** (len(ns) - 1))))

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
arr = []
arr_2 = []
for i in range(1,N+1):
    arr.append(str(i).strip('0'))
for j in arr:
    if len(j) == K:
        arr_2.append(j)
print (len(arr_2))

Submission status: Wrong Answer

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

def nCk(N, K):
    if K > n or K < 0:
        return 0
    return fact[N] // fact[K] // fact[N-K]


def digits(N):
    N = abs(N)
    ret = 0
    x = 1
    while x <= N:
        ret += 1
        x *= 10
    return ret

fact = [1]
for i in range(1, 101):
    fact += [fact[i-1] * i]

digit = digits(n)
ans = 0
k9 = 9 ** k
for i in range(k, digit):
    ans += k9 * nCk(i - 1, k - 1)
ans += (n // (10**(digit-1)) - 1) * (k9//9) * nCk(digit-1, k-1)

if k == 1:
    print(ans+1)
    exit()
elif k == 2:
    n10 = n%(10**(digit-1))
    if n10 == 0:
        print(ans)
        exit()
    d = digits(n10)
    top = n10 // (10**(d-1))
    print(ans + top + 9 * (d-1))
elif k == 3:
    n10 = n%(10**(digit-1))
    if n10 == 0:
        print(ans)
        exit()
    d10 = digits(n10)
    n100 = n10%(10**(d10-1))
    if n100 == 0:
        top = n10 // (10**(d10-1))
        print(ans + (top-1) * 9 * (d10-1))
        exit()
    d100 = digits(n100)
    top = n10 // (10**(d10-1))
    sec = n100 // (10**(d100-1))
    print(ans + sec + (top-1)*9*(d10-1) + 9 * 9 * nCk(d10-1, 2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
from itertools import combinations

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


    a=list(range(0, 100))
    t=0

    if k==3:
        xx = combinations(a, k)
        for p in xx:
            if n<(10**p[0]+10**p[1]+10**p[2]):
                continue
            elif n>=(10**p[0]*9+10**p[1]*9+10**p[2]*9):
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                        for k in range(1,10):
                            if n>=(10**p[0]*i+10**p[1]*j+10**p[2]*k):
                                t+=1
    elif k==2:
        xx = combinations(a, k)
        for p in xx:
            if n<(10**p[0]+10**p[1]):
                continue
            elif n>=(10**p[0]*9+10**p[1]*9):
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                            if n>=(10**p[0]*i+10**p[1]*j):
                                t+=1
    elif k==1:
        xx = combinations(a, k)
        for p in xx:
            if n<(10**p[0]):
                continue
            elif n>=(10**p[0]*9):
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                            if n>=(10**p[0]*i):
                                t+=1


    print(t)

    return

resolve()