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

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

from operator import mul
from functools import reduce

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

if k==1:
    syo = int(str(n)[0])
    ans = 9*(len(str(n))-1)+syo
if k==2:
    fir = int(str(n)[0])
    sec = int(str(n)[1])
    ans = 9**2*cmb(len(str(n))-1,2)
    ans+=(fir-1)*9+sec
    ans += 9*cmb(len(str(n))-2,1)*fir

if k==3:
    fir = int(str(n)[0])
    sec = int(str(n)[1])
    thi = int(str(n)[2])
    ans = 9**3*cmb(len(str(n))-1,3)
    ans += (fir-1)*81+(sec-1)*9+thi
    ans += 9*9*cmb(len(str(n))-2,2)*fir
    ans += ((fir-1)*9+sec)*9*cmb(len(str(n))-3,1)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = input()
    length = len(N)
    K = int(input())

    # 左からi桁目まで見て，N以下が確定していて，0でない数字がk個ある数字の個数
    dp_1 = [[0] * (10) for _ in range(length)]

    # 左からi桁目まで見て，N以下が確定していなくて，0でない数字がk個ある数字の個数
    dp_2 = [[0] * (10) for _ in range(length)]

    dp_1[0][0] = 1
    dp_1[0][1] = int(N[0]) - 1

    dp_2[0][1] = 1

    for i in range(1, length):
        # 小さいのが確定しているものに対して，0以外のものを追加
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        # 小さいものが確定しているものに対して，0を追加
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        # 大小がわからないものから，小さいのが確定する
        if N[i] == "0":
            for i in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            # 0を追加する
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            # その他の数字を追加
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            # 依然として大小関係がわからない
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
NS = input()
N = int(NS)
Nle = len(NS)
K = int(input())
ans = 0

if K == 1:
    ans = (Nle-1) * 9 + int(NS[0])
elif K == 2:
    ans = Nle * (Nle-1) * 9 * 9//2 - (9 - int(NS[0])) * (Nle-1) * 9 - 1 * (9 - int(NS[1]))
else:
    ans = Nle * (Nle-1) * (Nle-2) * (9**3) // 6 - \
          (9 - int(NS[0])) * (Nle-1) * (Nle-2) * 9 * 9 // 2 -\
          1 * (9 - int(NS[1])) * (Nle-2) * 9 -\
          1 * 1 * (9 - int(NS[2]))

print(ans)

Submission status: Runtime Error

Solution code:
n = str(input())
p = int(input())

keta = len(n)
Dp = [[[0 for _ in range(2)] for _ in range(keta+1)]for _ in range(keta+1)]

Dp[0][0][1] = 1

for i in range(keta):
    for j in range(i+1):
        for k in range(10):
            if k == 0:
                if k < int(n[i]):
                    Dp[i+1][j][0] += Dp[i][j][0]
                    Dp[i+1][j][0] += Dp[i][j][1]
                    
                elif k == int(n[i]):
                    Dp[i+1][j][1] += Dp[i][j][1]
                    Dp[i+1][j][0] += Dp[i][j][0]
                
                else:
                    Dp[i+1][j][0] += Dp[i][j][0]
            
            else:
                if k < int(n[i]):
                    Dp[i+1][j+1][0] += Dp[i][j][0]
                    Dp[i+1][j+1][0] += Dp[i][j][1]
                elif k == int(n[i]):
                    Dp[i+1][j+1][1] += Dp[i][j][1]
                    Dp[i+1][j+1][0] += Dp[i][j][0]
                else:
                    Dp[i+1][j+1][0] += Dp[i][j][0]

print(sum(Dp[-1][p]))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(N,K))

Submission status: Runtime Error

Solution code:
def comb(n, k):
    nume, deno = 1, 1
    for i in range(k):
        deno *= n - i
        nume *= i + 1
    return deno // nume


def ans(N, K):
    ret = sum([9 ** K * comb(max(dig - 1, 1), K - 1)
               for dig in range(K, len(N))])
    ret += (int(N[0]) - 1) * 9 ** (K - 1) * comb(len(N) - 1, K - 1)
    if K == 1:
        return ret + 1
    elif K == 2:
        return ret + ans(N[1:], 1)
    elif K == 3:
        return ret + ans(N[1:], 2)


N = input()
K = int(input())
print(ans(N, K))

Submission status: Runtime Error

Solution code:
s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) #与えられた数字よりも一桁少ない999999999・・・までの個数
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) == 0:
    print(tasumae)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) #与えられた数字よりも一桁少ない999999999・・・までの個数
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) = 0:
    print(tasumae)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis1):
    ketak1=len(lis1)
    if ketak1==1 and lis1[0]=="0":
      return 0
    k1res=int(lis1[0])+9*(ketak1-1)
    return k1res

def k2(lis2):
    ketak2=len(lis2)
    if ketak2==0 and (lis2[0]=="0" or (lis2[0]=="1" and lis2[1]=="0")):
      return 0
    k2res=0
    if not lis2[0]=="0":
      k2res+=(int(lis2[0])-1)*(ketak2-1)*9
    k2_copy=lis2.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis3):
    ketak3=len(lis3)
    if ketak3==3 and (lis3[0]=="0" or (lis3[0]=="1" and (lis3[1]=="0" or (lis3[1]=="1" and lis3[2]=="0")))):
      return 0
    k3res=0
    k3res+=(int(lis3[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis3.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=(((ketak3-1)*(ketak3-2)*(ketak3-3))//6)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis1):
    ketak1=len(lis1)
    if ketak1==1 and lis1[0]=="0":
      return 0
    k1res=int(lis1[0])+9*(ketak1-1)
    return k1res

def k2(lis2):
    ketak2=len(lis2)
    if ketak2==0 and (lis2[0]=="0" or lis2[1]=="0"):
      return 0
    k2res=0
    if not lis2[0]=="0":
      k2res+=(int(lis2[0])-1)*(ketak2-1)*9
    k2_copy=lis2.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis3):
    ketak3=len(lis3)
    if ketak3==3 and(lis3[0]=="0" or lis3[1]=="0" or lis3[2]=="0"):
      return 0
    k3res=0
    k3res+=(int(lis3[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis3.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=(((ketak3-1)*(ketak3-2)*(ketak3-3))//6)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis1):
    ketak1=len(lis1)
    if ketak1==1 and lis1[0]=="0":
      return 0
    k1res=int(lis1[0])+9*(ketak1-1)
    return k1res

def k2(lis2):
    ketak2=len(lis2)
    if ketak2==0 and (lis2[0]=="0" or lis2[1]=="0"):
      return 0
    k2res=0
    if not lis2[0]="0":
      k2res+=(int(lis2[0])-1)*(ketak2-1)*9
    k2_copy=lis2.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis3):
    ketak3=len(lis3)
    if ketak3==3 and(lis3[0]=="0" or lis3[1]=="0" or lis3[2]=="0"):
      return 0
    k3res=0
    k3res+=(int(lis3[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis3.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=(((ketak3-1)*(ketak3-2)*(ketak3-3))//6)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis1):
    ketak1=len(lis1)
    if ketak1==1 and lis1[0]=="0":
      return 0
    k1res=int(lis1[0])+9*(ketak1-1)
    return k1res

def k2(lis2):
    ketak2=len(lis2)
    if ketak2==0 and (lis2[0]=="0" or lis2[1]=="0"):
      return 0
    k2res=0
    k2res+=(int(lis2[0])-1)*(ketak2-1)*9
    k2_copy=lis2.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis3):
    ketak3=len(lis3)
    if ketak3==3 and(lis3[0]=="0" or lis3[1]=="0" or lis3[2]=="0"):
      return 0
    k3res=0
    k3res+=(int(lis3[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis3.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=(((ketak3-1)*(ketak3-2)*(ketak3-3))//6)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis1):
    ketak1=len(lis1)
    if ketak1==1 and lis1[0]==0:
      return 0
    k1res=int(lis1[0])+9*(ketak1-1)
    return k1res

def k2(lis2):
    ketak2=len(lis2)
    if ketak2==0 and (lis2[0]=="0" or lis2[1]=="0"):
      return 0
    k2res=0
    k2res+=(int(lis2[0])-1)*(ketak2-1)*9
    k2_copy=lis2.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis3):
    ketak3=len(lis3)
    if ketak3==3 and(lis3[0]=="0" or lis3[1]=="0" or lis3[2]=="0"):
      return 0
    k3res=0
    k3res+=(int(lis3[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis3.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=(((ketak3-1)*(ketak3-2)*(ketak3-3))//6)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis1):
    ketak1=len(lis1)
    k1res=int(lis1[0])+9*(ketak1-1)
    return k1res

def k2(lis2):
    ketak2=len(lis2)
    k2res=0
    k2res+=(int(lis2[0])-1)*(ketak2-1)*9
    k2_copy=lis2.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis3):
    ketak3=len(lis3)
    k3res=0
    k3res+=(int(lis3[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis3.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=(((ketak3-1)*(ketak3-2)*(ketak3-3))//6)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

keta=len(n)
n_list=[]
for i in range(0,keta):
    n_list.append(n[i])

def k1(lis):
    ketak1=len(lis)
    k1res=int(lis[0])+9*(ketak1-1)
    return k1res

def k2(lis):
    ketak2=len(lis)
    k2res=0
    k2res+=(int(lis[0])-1)*(ketak2-1)*9
    k2_copy=lis.copy()
    k2_copy.pop(0)
    k2res+=k1(k2_copy)
    k2res+=((ketak2-1)*(ketak2-2)//2)*(9**2)
    return k2res

def k3(lis):
    ketak3=len(lis)
    k3res=0
    k3res+=(int(lis[0])-1)*(((ketak3-1)*(ketak3-2))//2)*(9**2)
    k3_copy=lis.copy()
    k3_copy.pop(0)
    k3res+=k2(k3_copy)
    k3res+=((ketak3-1)*(ketak3-2)//2)*(ketak3-3)*(9**3)
    return k3res
  
if k==1:
  print(k1(n_list))
  
if k==2:
  print(k2(n_list))
  
if k==3:
  print(k3(n_list))

Submission status: Runtime Error

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

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

    minus = 0
    if k == 1:
        minus = 9 - int(n[0])
    elif k == 2:
        b = 9 - int(n[0])
        minus = b*(digits-1)*9+(9-int(n[1]))
    elif k == 3:
        b = 9 - int(n[0])
        minus += b*(digits-1)*(digits-2)*9*9//2
        minus += (9-int(n[1]))*(digits-2)*9
        minus += (9-int(n[2]))

    print(ans-minus)


main()

Submission status: Runtime Error

Solution code:
from math import log
def solve(N, K):
    if N == 1:
        if K == 1:
            return 1
        return 0
    num = int(log(N, 10))
    if K == 1:
        res = 9 * num + N//(10**num)
        return res
    if K == 2:
        res = 9 ** 2 * (num*(num-1))//2 
        res += (N//(10**num) - 1)*num*9
        res += solve(N - N//(10**num)*(10**num), 1)
        return res
    if K == 3:
        res = 9 ** 3 * (num*(num-1)*(num-2))//6
        res += (N//(10**num) - 1)*(num*(num-1))*81//2
        res += solve(N - N//(10**num)*(10**num), 2)
        return res
N = int(input())
K = int(input())
print(solve(N, K))

Submission status: Runtime Error

Solution code:
from math import log
def solve(N, K):
    num = int(log(N, 10))
    if K == 1:
        res = 9 * num + N//(10**num)
        return res
    if K == 2:
        res = 9 ** 2 * (num*(num-1))//2 
        res += (N//(10**num) - 1)*num*9
        res += solve(N - N//(10**num)*(10**num), 1)
        return res
    if K == 3:
        res = 9 ** 3 * (num*(num-1)*(num-2))//6
        res += (N//(10**num) - 1)*(num*(num-1))*81//2
        res += solve(N - N//(10**num)*(10**num), 2)
        return res
N = int(input())
K = int(input())
print(solve(N, K))

Submission status: Runtime Error

Solution code:
from scipy.misc import comb
N = int(input())
K = int(input())
# n : Nの桁数
n = len(str(N))
# m : 各位の値
m = list(map(int,str(N)))
###最高位が 0 の時
A = (9 ** (K)) * comb(n-1,n-K-1,exact=True)
###最高位が 1 以上 m[0] 未満 の時
B = (m[0]-1) * (9 ** (K-1)) * comb(n-1,n-K,exact = True)
###最高位が m[0] の時
C = 0
if not n == K:
    for i in range(K):
        c_0 = (9 ** (K-1-i)) * comb(n-2-i,K-1-i,exact=True)
        c_9 = 1
        for j in range(1,i+1):
            c_9 *= m[j]
        c = c_0 * c_9
        C += c
else:
    c = 1
    for i in range(n-1):
        c *= m[i+1]
        C += c
print(A+B+C)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

N = int(input())
K = int(input())
n = len(str(N))
m = list(map(int,str(N)))
A = (9 ** (K)) * comb(n-1,n-K-1,exact=True)
B = (m[0]-1) * (9 ** (K-1)) * comb(n-1,n-K,exact = True)
C = 0
if not n == K:
    for i in range(K):
        c_0 = (9 ** (K-1-i)) * comb(n-2-i,K-1-i,exact=True)
        c_9 = 1
        for j in range(1,i+1):
            c_9 *= m[j]
        c = c_0 * c_9
        C += c
else:
    c = 1
    for i in range(n-1):
        c *= m[i+1]
        C += c
print(A+B+C)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
N = int(input())
K = int(input())
# n : Nの桁数
n = len(str(N))
# m : 各位の値
m = list(map(int,str(N)))
###最高位が 0 の時
A = (9 ** (K)) * comb(n-1,n-K-1,exact=True)
###最高位が 1 以上 m[0] 未満 の時
B = (m[0]-1) * (9 ** (K-1)) * comb(n-1,n-K,exact = True)
###最高位が m[0] の時
C = 0
## 
if not n == K:
    for i in range(K):
        c_0 = (9 ** (K-1-i)) * comb(n-2-i,K-1-i,exact=True)
        c_9 = 1
        for j in range(1,i+1):
            c_9 *= m[j]
        c = c_0 * c_9
        C += c
else:
    c = 1
    for i in range(n-1):
        c *= m[i+1]
        C += c
print(A+B+C)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

N = int(input())
K = int(input())
# n : Nの桁数
n = len(str(N))
# m : 各位の値
m = list(map(int,str(N)))
###最高位が 0 の時
A = (9 ** (K)) * comb(n-1,n-K-1,exact=True)
###最高位が 1 以上 m[0] 未満 の時
B = (m[0]-1) * (9 ** (K-1)) * comb(n-1,n-K,exact = True)
###最高位が m[0] の時
C = 0
## 
if not n == K:
    for i in range(K):
        c_0 = (9 ** (K-1-i)) * comb(n-2-i,K-1-i,exact=True)
        c_9 = 1
        for j in range(1,i+1):
            c_9 *= m[j]
        c = c_0 * c_9
        C += c
else:
    c = 1
    for i in range(n-1):
        c *= m[i+1]
        C += c
print(A+B+C)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

N = int(input())
K = int(input())
# n : Nの桁数
n = len(str(N))
# m : 各位の値
m = list(map(int,str(N)))
###最高位が 0 の時
A = (9 ** (K)) * comb(n-1,n-K-1,exact=True)
###最高位が 1 以上 m[0] 未満 の時
B = (m[0]-1) * (9 ** (K-1)) * comb(n-1,n-K,exact = True)
###最高位が m[0] の時
C = 0
## 
if not n == K:
    for i in range(K):
        c_0 = (9 ** (K-1-i)) * comb(n-2-i,K-1-i,exact=True)
        c_9 = 1
        for j in range(1,i+1):
            c_9 *= m[j]
        c = c_0 * c_9
        C += c
        print(c_0,c_9)
else:
    c = 1
    for i in range(n-1):
        c *= m[i+1]
        C += c
print(A,B,C)
print(A+B+C)

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
    if k == 1:
 		print(int(n))  
    if k >= 2:
      print(0)
else:
  print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Runtime Error

Solution code:
n = str(input())
k = int(input())
dp = [[[0 for i in range(len(n))+1] for i in range(2)] for i in range(len(n))]
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if n[a] > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if n[a] > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if n[a] == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if n[a] == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
print(dp)

Submission status: Runtime Error

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

from functools import lru_cache

n, k = map(int, read().split())


@lru_cache(None)
def check(n, k):
    a, b = divmod(n, 10)
    cnt = 0
    if k >= 1:
        cnt += check(a, k - 1) * b
        cnt += check(a - 1, k - 1) * (9 - b)
    cnt += check(a, b)
    return cnt


if n < 10:
    if k == 1:
        print(n)
    else:
        print(0)
else:
    print(check(n, k))

Submission status: Runtime Error

Solution code:
n = int (input ())
k = int (input ())
if k == 1:
	ans = 0
	i = 0
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += (r - l) // pow (10, i) + 1
		i += 1
	print (ans)
elif k == 2:
	ans = 0
	i = 1
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * i 
		tmp = (r - l) // pow (10, i - 1)
		a = tmp % 10
		ans -= (9 - a) 
		i += 1
	print (ans)
else:
	ans = 0
	i = 2
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * 9 * i * (i - 1) // 2
		tmp = (r - l) // pow (10, i - 2)
		a = tmp % 100 // 10
		b = tmp % 10 
		ans -= (9 - a) * 9 + (9 - b)
		i += 1
		# print (l, r, ans)
	exit (1)
	print (max (0, ans))

Submission status: Runtime Error

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

def F(N, K):
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q, r = divmod(N, 10)
    ret = 0
    if K >= 1:
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    ret += F(q, K)
    return ret

print(F(N, K))

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

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

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

# N の桁数を M として、1~9 が (M-K) 個と 0 が K 個を並べ替えた時に(leading zeroを許容して)できる数字の総数

M = len(str(N))  # N の桁数
ans = 9**(M-K) * cmb(M, K)  # 可能な全パターン

# ここから N+1 ~ 999..90 (最後の 0 は K 個) の条件を満たさない分を引く
max_int = int("9"*(M-K) + "0"*K)
ans -= max_int - (N+1) + 1

print(ans)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
l2=[0]*20
inv=[0]*(10**6+10)
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    K = iip(False)
    ret = solve(N, K)
    print(ret)

def solve(N, K):

    strn = str(N)

    A = []
    B = []

    for i in range(len(strn), 0, -1):
        if strn[len(strn)-i] != "0":
            A.append(int(strn[len(strn)-i]))
            B.append(i)


    if K == 1:
        return 9*(B[0]-1) + A[0]


    if K == 2:
        if len(strn) < 2:
            return 0
        ret = 0
        ret += (B[0]-1) * (B[0]-2) // 2 * (9**2) #桁数がmaxじゃない場合
        ret += (A[0]-1) * 9 * (B[0]-1) #桁数がmaxで先頭桁がmax以外の場合
        if len(B) >= 2 and len(A) >= 2:
            ret += (B[1]-1) * 9 + A[1] #先頭桁がmaxの場合
        return ret

    ret = 0
    ret += (B[0] - 1) * (B[0] - 2) * (B[0] - 3) // 6 * 9**3 #桁数がmaxじゃない場合
    ret += (A[0] - 1) * (B[0] - 1) * (B[0] - 2) // 2 * 9**2 #桁数がmaxで先頭桁がmaxじゃない場合

    #以下、桁数はmaxで先頭桁はmaxとする
    if len(strn) < 3:
        return 0
    if len(B) >= 2:
        ret += (B[1]-1) * (B[1]-2) // 2 * 9**2 #有効2桁目の桁数がmaxじゃない場合
    if len(B) >= 2 and len(A) >= 2:
        ret += (A[1] - 1) * (B[1]-1) * 9 #有効2桁目の桁数がmaxで数字がmaxじゃない場合
    if len(B) >= 3 and len(A) >= 3:
    ret += (B[2] - 1) * 9 + A[2] #有効2桁目,3桁目がmaxの場合
    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
from collections import deque

def main():
    N = iip(False)
    K = iip(False)
    ret = solve(N, K)
    print(ret)

def solve(N, K):

    strn = str(N)

    A = []
    B = []

    for i in range(len(strn), 0, -1):
        if strn[len(strn)-i] != "0":
            A.append(int(strn[len(strn)-i]))
            B.append(i)


    if K == 1:
        return 9*(B[0]-1) + A[0]


    if K == 2:
        if len(strn) < 2:
            return 0
        ret = 0
        ret += (B[0]-1) * (B[0]-2) // 2 * (9**2) #桁数がmaxじゃない場合
        ret += (A[0]-1) * 9 * (B[0]-1) #桁数がmaxで先頭桁がmax以外の場合
        ret += (B[1]-1) * 9 + A[1] #先頭桁がmaxの場合
        return ret

    ret = 0
    ret += (B[0] - 1) * (B[0] - 2) * (B[0] - 3) // 6 * 9**3 #桁数がmaxじゃない場合
    ret += (A[0] - 1) * (B[0] - 1) * (B[0] - 2) // 2 * 9**2 #桁数がmaxで先頭桁がmaxじゃない場合

    #以下、桁数はmaxで先頭桁はmaxとする
    if len(strn) < 3:
        return 0
    ret += (B[1]-1) * (B[1]-2) // 2 * 9**2 #有効2桁目の桁数がmaxじゃない場合
    ret += (A[1] - 1) * (B[1]-1) * 9 #有効2桁目の桁数がmaxで数字がmaxじゃない場合
    ret += (B[2] - 1) * 9 + A[2] #有効2桁目,3桁目がmaxの場合
    return ret


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))

def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        #print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r-l > 1:
        x = (l+r)//2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        #print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod


if __name__ == "__main__":
    main()