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:
def nC2(n):
    return n*(n-1)/2

def nC3(n):
    return n*(n-1)*(n-2)/2/3

def K1(s):
    while s[0]=="0" and len(s)>0:
        s=s[1:]

    ll=len(s)

    if ll==1 or ll ==0:
        N=int(s[0])
    
    elif ll>1:
        N=int(s[0])+9*(ll-1)

    return N


def K2(s):
    while s[0]=="0" and len(s)>0:
        s=s[1:]
    
    ll=len(s)

    if ll==1 or ll ==0:
        N=0
    elif ll==2:
        N=(int(s[0])-1)*9+int(s[1])
    else:
        N=K1(s[1:])+(int(s[0])-1)*(ll-1)*9+9*9*nC2(ll-1)

    return N


def K3(s):
    ll=len(s)

    if ll ==1 or ll==2:
        N=0
    elif ll==3:
        N=(int(s[0])-1)*9*9+int(s[1])*int(s[2])
    else:
        N=K2(s[1:])+(int(s[0])-1)*nC2(ll-1)*9*9+nC3(ll-1)*9*9*9
    
    return N

N=input()
K=input()

if K=="1":
    ans=K1(N)
elif K=="2":
    ans=K2(N)
elif K=="3":
    ans=K3(N)

print(int(ans))

Submission status: Runtime Error

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

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  if n[0] == '0':
    return syou(n[1:l], k-1)
  
  l = len(n)
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  print('tmp:', n,k,ans)
  return ans


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

print(syou(n, k))

Submission status: Runtime Error

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

import math

def func(n,k):
  if k==0:
    return 0
  digit = len(n)
  res = 0
  if digit == 1:
    if k ==1:
      res = int(n)
    return res
  if digit == 2:
    if k ==2:
      res = (int(n) - 9 - int(n) //10)
    elif k == 3:
      res = (0)
    else:
      res = (9+int(n)//10)
    return res

  base = 9**k * (math.factorial(digit-1)/ (math.factorial(k) * math.factorial(digit-1-k)) )

  for i in range(9):
    i+= 1
    if i < int(n[0]):
      base += func(n[1:],k-1)
  return base

print(int(func(n,k)))

Submission status: Runtime Error

Solution code:
from collections import Counter
N=input()
K=int(input())
res = 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)<=1000:
        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: Runtime Error

Solution code:
N = int(input())
K = int(input())
from math import log10
from operator import mul
from functools import reduce

def comb(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


lg = int(log10(N))

def dp(n:int,k:int,K:int):
    lg = int(log10(N))
    if n > N:
        return 0
    if k > K:
        return 0
    if k == K:
        tmp = lg - int(log10(n))
        return tmp if n*10**tmp > N else tmp + 1
    sm = 0
    for i in range(1,10):
        sm += dp(n*10 + i,k + 1,K)
    return sm + dp(n*10,k,K)

memo = {}
def dp2(string:str,k:int):
    if (string,k) in memo:
        return memo[(string,k)]
    if k == 1:
        ans = 0
        for i in range(int( log10( N ) ) + 2):
            digit = 10**i
            for j in range(1,10):
                if j*digit <= N:
                    ans += 1
        memo[(string,k)] = ans
        return memo[(string,k)]

    if string[0] == "0":
        memo[(string,k)] =  dp2(string[1:],k)
        return memo[(string,k)]

    if len(string) > 3:
        ln = len(string)
        tmp = (comb(ln - 1,k)*9**k)*(string[0]) + dp2(string[1:],k)
        memo[(string,k)] = tmp
        return tmp
    memo[(string,k)] = dp(int(string),0,K)
    return memo[(string,k)]

def main():
    if K == 1:
        ans = 0
        for i in range(int( log10( N ) ) + 2):
            digit = 10**i
            for j in range(1,10):
                if j*digit <= N:
                    ans += 1
        print(ans)
        return
    if N < 10**10:
        ans = 0
        for i in range(1,10):
            ans += dp(i,1)
        print(ans)
    print(dp2(str(N),K))
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

mainDigit = len(n)

def digitOne(digit, p):
  return 9 * (digit - 1) + p

def digitTwo(digit, p, q, qZure):
  return 81 * (digit-1) * (digit-2) // 2 + 9 * (digit-1) * (p-1) + digitOne(digit-1-qZure, q)

if k == 1:
  print(digitOne(mainDigit, int(n[0])))
elif k == 2:
  qZure = 0
  for i in range(1, mainDigit):
    if int(n[i]) == 0:
      qZure += 1
    else:
      break
  print(digitTwo(mainDigit, int(n[0]), int(n[qZure+1]), qZure))

Submission status: Runtime Error

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

def one(string):
    L = len(string)
    ans = (L-1)*9
    ans += int(string[0])
    return ans

def two(string):
    ans = sum(range(L - 1)) * 81
    head = int(string[0])
    ans += (head - 1) * 9 * (L - 1)
    ans += one(string[1:])
    return ans

ans = 0
L = len(str(N))
if K == 1:
    ans = one(NStr)
elif K == 2:
    ans = two(NStr)
else:
    seed = [0]*(L-1)
    for i in range(1, L-1):
        seed[i] = seed[i-1] + i
    ans = sum(seed[:L-2]) * 81 *9
    head = int(NStr[0])
    ans += (head-1)*81*(seed[L-2])
    ans += two(NStr[1:])

print(ans)

Submission status: Runtime Error

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

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


def sasa(N, K):
  # 桁数を取得
  dig = len(str(N))
  top = int(str(N)[0])
  ans = 0
  # X00000までの場合
  # 先頭を0以外にする場合
  if dig-1>=K-1:
    ans += (top-1) * comb(dig-1, K-1) * 9**(K-1)

  # 先頭を0にする場合
  if dig-1 >= K:
    ans += comb(dig-1, K) * 9**K

  if K == 1:
    ans += 1
  return ans

if K == 1:
  N1 = round(N, -len(str(N)) + 1)
  print(sasa(N1, K))
  exit()

if K == 2:
  N1 = round(N, -len(str(N)) + 1)
  ans1 = sasa(N1,K)

  _N2 = N - N1
  N2 = round(_N2, -len(str(_N2)) + 1)
  ans2 = sasa(N2, K-1)
  print(ans1+ans2)
  exit()

if K == 3:
  N1 = round(N, -len(str(N)) + 1)
  ans1 = sasa(N1,K)

  _N2 = N - N1
  N2 = round(_N2, -len(str(_N2)) + 1)
  ans2 = sasa(N2, K-1)

  _N3 = N - N1 - N2
  N3 = round(_N3, -len(str(_N3)) + 1)
  ans3 = sasa(N3, K-2)

  print(ans1+ans2+ans3)
  exit()

Submission status: Runtime Error

Solution code:
n = input()
n_0 = int(n[0])
n_1 = int(n[1])
n_2 = int(n[2])
n = len(n)
k = int(input())

if n < k:
    print(0)
else:
    if k == 1:
        print(9*(n-1)+n_0)
    elif k == 2:
        print(81*(-2)*(n-1)//2 + (n_0-1)*9*(n-1) + 9*(n-2) + n_1)
    else:
        print(9*9*9*((n-3)*(n-2)*(2*n-5)//6 + (n-3)*(n-2)//2)//2 + (n_0-1)*81*(n-1)*(n-2)//2 + 81*(n-3)*(n-2)//2 + (n_1-1)*9*(n-2) + 9*(n-3) + n_2)

Submission status: Runtime Error

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
  if _i > K:
    break
print(count)

Submission status: Runtime Error

Solution code:

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

dp1 = [ [ i+1 for i in range(9) ] for i in range(201)]
dp2 = [ [ 0 for i in range(9) ] for i in range(201)]
dp3 = [ [ 0 for i in range(9) ] for i in range(201)]

for i in range(200):
    for j in range(9):
        if j == 0:
            dp1[i+1][j] = dp1[i][-1] + 1
        else:
            dp1[i+1][j] = dp1[i+1][j-1] + 1

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp3[i+1][j] = dp3[i][-1] + 81 * i*(i-1)//2
        else:
            dp3[i+1][j] = dp3[i+1][j-1] + 81 * (i+1) * i //2


def solve(s, x):
    if s[0] == "0":
        return 0
    if x == 1:

        return  dp1[len(s)-1][int(s[0]) - 1]
    elif x == 2:

        return  dp2[len(s)-1][int(s[0]) - 1] + solve(s[1:], 1)
    elif x == 3:

        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

Submission status: Runtime Error

Solution code:
from math import factorial

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

n=int(input())
k=int(input())
ans=0
nstr=str(n)
nl=len(nstr)
for i in range(k,nl):
    ans+=combinations_count(i-1,k-1)
ans*=9**k
zerocnt=0
for i in range(nl):
    if zerocnt<=nl-k:
        if i==0:
            ans+=(int(nstr[0])-1)*combinations_count(nl-1,k-1)*(9**(k-1))
        else:
            if nstr[i]=='0':
                zerocnt+=1
            else:
                ans+=(int(nstr[i])-1)*combinations_count(nl-i-1,k-i+zerocnt-1)*9**(k-i+zerocnt-1)
    else:
        break
print(ans)

Submission status: Runtime Error

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

s = str(n)
a = len(str(n))
b = n//10**(a-1)
c = int(s[1])
d = int(s[2])
e = int(s[3])
def F1(i):
  A = len(str(i))
  B = i//10**(A-1)
  return(9*(A-1)+B)
def F2(i):
  A = len(str(i))
  B = i//10**(A-1)
  S = str(i)
  C = int(S[1])
  return((A-1)*(A-2)*81/2 + (B-1)*(A-1)*9+(A-2)*9*C +1)

if k ==1:
  print(9*(a-1)+b)

if k == 2:
   ans = (a-1)*(a-2)*81/2 + (b-1)*(a-1)*9+(a-2)*9*c +1
   print(ans)
if k ==3:
   ans = (a-1)*(a-2)*(a-3)//2*243 + F2(10**(a))*(b-1)+ F1(10**(a-1))*(c-1)+(a-3)*9*d +1
   print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def com(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 run():
  N = int(input())
  K = int(input())
  Nnum = len(str(N))
  #1
  all1 = com(Nnum, K)*9**K
  #2
  all2 = (9-int(str(N)[0]))*com(Nnum-1, K-1)*9**(K-1)
  if K == 1:
    print(all1-all2)
  #3
  elif K == 2:
    all3 = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        all3 += 9-N2
        break
      all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
  #4
  else:
    all3 = 0
    count = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        if count == 0:
          all3 += (9-N2)*com(Nnum-n-1, 1)*9
        elif count == 1:
          all3 += 9-N2
        count += 1
        if count == 2:
          break
      elif count == 0:
        all3 += 9*(Nnum-n-1)*9
      else:
        all3 += 9
    else:
      if count == 0:
        all3 = com(Nnum-1, 2)*9*9
      else
        all3 = (Nnum-1)*9
    print(all1-all2-all3)
    
  

if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
def out_order1(N):
    return(9 * (len((str(N))) - 1) + int(str(N)[0]))
def out_order2(N):
    if(len(str(N)) >= 3):
        out = 9 * 9 * (len(N) - 1) * (len(N) - 2) / 2
        out += (int(str(N)[0]) - 1) * (len(N) - 1) * 9
        N = str(N)
        N = N[1:]
        out += out_order1(int(N))
    elif(len(N) == 2):
        out = (int(str(N)[0]) - 1) * 9 + (int(str(N)[1]))
    else:
        out = 0
    return(out)

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

if K == 1:
    out = out_order1(N)
elif K ==2:
    out = out_order2(N)
elif K == 3:
    if(len(str(N)) >= 4):
        out = 9 * 9 * 9 * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) / 6
        out += (int(str(N)[0]) - 1) * (len(N) - 1) * (len(N) - 2) * 9 * 9 / 2
        N = str(N)
        N = N[1:]
        out += out_order2(int(N))
    elif(len(str(N)) == 3):
        out = (int(str(N)[0]))
        N = str(N)
        N = N[1:]
        out += out_order2(int(N))
    else:
        out = 0
    
print(out)

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
from math import factorial
def nCr(n,r):
    return (factorial(n) // factorial(r) // factorial(n - r))
ans += 9**K*nCr(len(str(N))-1,K)
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

def k_1(n):
    h = int(n[0])
    res = 0
    res += max((h-1), 1) * (len(n)-1) * 9
    res += h
    return res

def k_2(n):
    h = int(n[0])
    res = 0
    res += comb(len(n)-1, 2) * 9 * 9
    res += (h-1) * (len(n)-1) * 9
    res += k_1(n[1:])
    return res

def k_3(n):
    h = int(n[0])
    res = 0
    res += comb(len(n)-1, 3) * 9 * 9 * 9
    res += (h-1) * comb(len(n)-1, 2) * 9 * 9
    res += k_2(n[1:])
    return res

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

res = 0

if K == 1:
    res = k_1(N)
elif K == 2:
    res = k_2(N)
else:
    res = k_3(N)

print(int(res))

Submission status: Runtime Error

Solution code:
N=input()
K=int(input()) #0以外の個数
x=len(N) #Nの桁数
cnt=0 #0以外の数カウント
ans=0

for i in range(x-1):
    a=i+1
    k=K
    if a-k<0:
        continue
    s=cmb(a-1,a-k)*9**k
    ans+=s

i=-1
while (cnt<3 and i<=x-2):
    i+=1 #現在の桁位置
    init=int(N[i]) #桁取り出し
    
    if i>0:
        a=x-i-1
        k=K-cnt
        if a-k>=0 and k>=0 and a>0:
            s=cmb(a,a-k)*9**k
            ans+=s
    
    if init!=0:
        cnt+=1
        a=x-i-1
        k=K-cnt
        if a-k>=0 and k>=0:
            if i!=x-1:
                s=(init-1)*cmb(a,a-k)*9**k
                ans+=s
            else:
                s=init*cmb(a,a-k)*9**k
                ans+=s
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
k=int(input())
m=str(n)
l=len(m)
if k>l:
  print(0)
  sys.exit()
if k==1:
  print(9*(l-1)+int(m[0]))
if k==2:
  print((((9**2)*(l-1)*(l-2)//2)+(int(m[0])-1)*(l-1)*9)+9*(l-2)+int(m[1]))
if k==3:
  if int(m[1])>0:
    print(((9**3)*(l-1)*(l-2)*(l-3)//6)+(int(m[0])-1)*(9**2)*((l-2)*(l-1)//2)+(((9**2)*(l-2)*(l-3)//2)+(int(m[1])-1)*(l-2)*9)+9*(l-3)+int(m[2]))
  else:
    print(((9**3)*(l-1)*(l-2)*(l-3)//6)+(int(m[0])-1)*(9**2)*((l-2)*(l-1)//2)+(((9**2)*(l-2)*(l-3)//2))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    nstr = str(N)

    nl = len(str(N))

    dp = [[[0 for _ in range(nl + 1)] for _ in range(2)] for _ in range(nl + 1)]
    dp[0][0][0] = 1

    for i in range(nl):
        max_digit = int(nstr[i])
        for smaller in range(2):
            for j in range(nl):
                range_digit = 9
                # range_digit = 9 if smaller else max_digit
                if not smaller:
                    range_digit = max_digit
                for x in range(range_digit + 1):
                    if x != 0:
                        if smaller == 1:
                            dp[i + 1][smaller][j + 1] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j + 1] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j + 1] += dp[i][smaller][j]
                    else:
                        if smaller == 1:
                            dp[i + 1][smaller][j] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j] += dp[i][smaller][j]

    ans = 0
    print(dp[nl][1][K])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

from scipy.misc import comb
from math import factorial

n_d = len(str(n))
digits = str(n)

def get_num(top, k_val, d_num):
  #print(top, k_val, d_num)
  if d_num>n_d:
    return 1
  elif k_val==0:
    return 1
  elif top:
    below1 = get_num(True, k_val-1, d_num+1)
    below2 = (int(digits[d_num])-1) * get_num(False, k_val-1, d_num+1)
    below3 = get_num(False, k_val, d_num+1)
    return below1 + below2 + below3
  else:
    return factorial(n_d-d_num) / factorial(k_val) / factorial(n_d - d_num - k_val) * 9**(k_val)
    #return comb(n_d-d_num, k_val) * 9**(k_val)



if k<n_d :
  #a = comb(n_d-1, k)
  a = factorial(n_d-1) / factorial(k) / factorial(n_d-1 - k)
else:
  a = 0
a *= 9**k
#b = (int(digits[0]) - 1) * comb(n_d-1, k-1) * 9**(k-1)
c1 = get_num(True, k-1, 1)
c2 = (int(digits[0]) - 1) * get_num(False, k-1, 1)

#print(a, c1, c2)
print(int(a+c1+c2))

Submission status: Runtime Error

Solution code:
def comb(a,b,m):
    if b == 0 or b == a:
        ret = 1
    else:
        ret = 1
        for i in range(a-b+1,a+1):
            ret = (ret * i) % m
        for i in range(1,b+1):
            ret = (ret * pow(i,m-2,m) ) % m
    return ret

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

dp1 = [ [ i+1 for i in range(9) ] for i in range(201)]
dp2 = [ [ 0 for i in range(9) ] for i in range(201)]
dp3 = [ [ 0 for i in range(9) ] for i in range(201)]

for i in range(100):
    for j in range(9):
        if j == 0:
            dp1[i+1][j] = dp1[i][-1] + 1
        else:
            dp1[i+1][j] = dp1[i+1][j-1] + 1

for i in range(100):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp3[i+1][j] = dp3[i][-1] + 81 * i*(i-1)//2
        else:
            dp3[i+1][j] = dp3[i+1][j-1] + 81 * (i+1) * i //2


def solve(s, x):
    if s[0] == "0":
        return 0
    if x == 1:

        return  dp1[len(s)-1][int(s[0]) - 1]
    elif x == 2:

        return  dp2[len(s)-1][int(s[0]) - 1] + solve(s[1:], 1)
    elif x == 3:

        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

Submission status: Runtime Error

Solution code:
import math

x = int(input())
K = int(input())

N = str(x)
n = len(N)

keta = [0] * n


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


for i in range(n):
    if int(N[i]) == 0:
        keta[i] = 0
    else:
        keta[i] = int(N[i])

Sum = 0

if n < K:
    print("0")
else:
    if K == 1:
        Sum += keta[0]
        Sum += 9 * (n - 1)
    
    elif K == 2:
        for j in range(1, n):
            if j == 1:
                Sum += ((keta[0] - 1) * 9) + keta[j]
            else:
                Sum += ((keta[0] - 1) * 9) + 9
    
        Sum += 81 * com(n - 1, 2)
    
    elif K == 3:
        for j in range(1, n - 1):
            for k in range(j + 1, n):
                if j == 1:
                    #a = Sum
                    if k == 2:
                        Sum += ((keta[0] - 1) * 81) + ((keta[j] - 1) * 9) + keta[2]
                    else:
                        Sum += ((keta[0] - 1) * 81) + ((keta[j] - 1) * 9) + 9
                    #print(Sum - a)
                else:
                    Sum += ((keta[0] - 1) * 81) +((keta[j] - 1) * 9) + keta[k]
    
        Sum += (9**3) * com(n - 1, 3)
    
    print(Sum)

Submission status: Runtime Error

Solution code:
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()
length = 0
for i in range(1, 100):
    if 10 ** i > N:
        length = i
        break

answer = 0
def F(length, K, N):
    ret = 0
    if length == 1:
        if K == 1:
            return N
        else:
            return 0
    top = int(str(N)[0])
    if length-K-1>=0:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K # 一個前まで
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) # 一桁目がtopより小さい数  
    if K > 1: # 一桁目がtopと同じ数
        ret += F(length-1, K-1, int(str(N)[1:]))
    else:
        ret += 1 # 2000のような数
    return ret

answer = F(length, K, N)
print(answer)

Submission status: Runtime Error

Solution code:
def out_order1(N):
    return(9 * (len((str(N))) - 1) + int(str(N)[0]))
def out_order2(N):
    if(len(N) >= 3):
        out = 9 * 9 * (len(N) - 1) * (len(N) - 2) / 2
        out += (int(str(N)[0]) - 1) * (len(N) - 1) * 9
        N = str(N)
        N = N[1:]
        out += out_order1(int(N))
    elif(len(N) == 2):
        out = (int(str(N)[0]) - 1) * 9 + (int(str(N)[1]))
    else:
        out = 0
    return(out)

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

if K == 1:
    out = out_order1(N)
elif K ==2:
    out = out_order2(N)
elif K == 3:
    if(len(N) >= 4):
        out = 9 * 9 * 9 * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) / 6
        out += (int(str(N)[0]) - 1) * (len(N) - 1) * (len(N) - 2) * 9 * 9 / 2
        N = str(N)
        N = N[1:]
        out += out_order2(int(N))
    elif(len(N) == 3):
        out = (int(str(N)[0]))
        N = str(N)
        N = N[1:]
        out += out_order2(int(N))
    else:
        out = 0
    
print(out)

Submission status: Runtime Error

Solution code:
import math
import numpy as np

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

def aez(N, K):
    digits = math.floor(math.log10(N)) + 1
    LD = N // 10**(digits-1)
    
    if K == 1:
        return (digits - 1) * 9 + LD
    
    if digits < K:
        return 0
    A = aez(10 ** (digits  - 1) - 1 , K)
    B = aez(10 ** (digits  - 1) - 1, K - 1) * (LD - 1)
    C = aez(N % (10 ** (digits  - 1)), K - 1)
    count = A + B + C
    
    return count
  
print(aez(N, K))

Submission status: Runtime Error

Solution code:
# from scipy.misc import comb
#import numpy as np
#import math
N = int(input()
K = int(input()

def count_0(range_value, zero_count):
    k = 0

    for i in range(range_value):
        if str(i).count("0") == zero_count:
            k+=1

    return k


print(count_0(N, K))

Submission status: Runtime Error

Solution code:
n=str(input())
k=int(input())
top=int(n[0])
l=len(n)
if k==1:
  print(9*(l-1)+top)
if k==2:
  if l==1:
    print(0)
  else:
    for i in range(1,l):
      result=0
      if l>2:
        result+=
      second=0
      second_i=0
      if n[i]!=0:
        second=n[i]
        second_i=i
        break

Submission status: Runtime Error

Solution code:
import math
fac = math.factorial
n = int(input())
K = int(input())
lst = []
cnt = 0
for i in range(10**(K-1), 10**K):
  if str(i).count("0") != 0:
    continue
  lst.append(list(map(int, list(str(i)))))
if K == 1:
  for i in range(100-K):
    for lsti in lst:
      if lsti * 10 ** i <= n:
        cnt += 1
elif K == 2:
  for i in range(1, 100-K):
    for j in range(100-K-i):
      for lsti in lst:
        if lsti[0] * 10 ** (i+j) \
             + lsti[1] * 10 ** j <= n:
          cnt += 1
elif K == 3:
  for i in range(2, 100-K):
    for j in range(1, 100-K-i):
      for k in range(100-K-i-j):
        for lsti in lst:
          if lsti[0] * 10 ** (i+j+k) \
             + lsti[1] * 10 ** (j+k) \
             + lsti[2] * 10 ** k <= n:
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
N=input()
K=int(input()) #0以外の個数
x=len(N) #Nの桁数
cnt=0 #0以外の数カウント
ans=0

for i in range(x-1):
    a=i+1
    k=K
    if a-k<0:
        continue
    s=cmb(a-1,a-k)*9**k
    ans+=s
    print(a,k,s)

i=-1
while (cnt<3 and i<=x-2):
    i+=1 #現在の桁位置
    init=int(N[i]) #桁取り出し
    
    if i>0:
        a=x-i-1
        k=K-cnt
        print(a,k)
        if a-k>=0 and k>=0 and a>0:
            s=cmb(a,a-k)*9**k
            ans+=s
            print(s)
    
    if init!=0:
        cnt+=1
        a=x-i-1
        k=K-cnt
        print(a,k)
        if a-k>=0 and k>=0:
            if i!=x-1:
                s=(init-1)*cmb(a,a-k)*9**k
                ans+=s
                print(s)
            else:
                s=init*cmb(a,a-k)*9**k
                ans+=s
                print(s)
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

digit_num = math.floor(math.log10(n)) + 1
count = [0 for _ in range(n)]
# 1桁少ないとこまで
for i in range(digit_num-1):
    j = i + 1
    if j > k:
        temp = ((j*j + 3*j + 2) * 9^(j-2))  /2
        count[i] = temp

b = 0

for i in range(digit_num,k,-1):
    s = int(str(n)[i])
    if s > 1:
        temp = (s-1) * count[i+1]
        b = b + temp

ans = sum(count)+b

print(b)

Submission status: Runtime Error

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

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

l=n
l=str(l)
keta=len(l)
num=[0 for i in range(keta)]
ans=0
m=n
for i in range(keta):
  num[i]=m%10
  m//=10
#print(num)
if k==1:
  ans+=num[-1]+(keta-1)*9
if k==2:
  ans+=(num[-1]-1)*(keta-1)*9
  for i in range(keta-1):
    if i!=keta-2:
      ans+=9
    else:
      ans+=num[i]
  if keta>=3:
    ans+=comb(keta-1,2)*81
if k==3:
  ans+=comb(keta-1,3)*729
  ans+=(num[-1]-1)*comb(keta-1,2)*81
  ans+=(num[-2]-1)*(keta-2)*9
  for i in range(keta-2):
    ans+=num[i]
print(ans)

Submission status: Runtime Error

Solution code:
#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

#選び方（コンビネーション nCr）
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


def calc2(n,k):
    n_given = n
    k_given = k

    ans = 0
    ndigits = len(str(n_given))
    if k_given == 1:
        msd = n_given
        while msd >= 10:
            msd //=10
        
        ans = (ndigits-1)*9+msd

    elif k_given == 2:
        if ndigits < 2:
            ans = 0
        else:
            msd1 = n_given
            while msd1 >= 100:
                msd1 //=10
            msd2 = msd1%10
            msd1 = msd1//10
            
            if(ndigits > 2):
                ans += cmb(ndigits-1,2)*pow(9,2)
            ans += (msd1-1)*(ndigits-1)*9
            ans += (ndigits-2)*9+msd2

    return ans

n_given = input_one_number()
k_given = input_one_number()

ans = 0
ndigits = len(str(n_given))
if k_given == 1:
    msd = n_given
    while msd >= 10:
        msd //=10

    ans = (ndigits-1)*9+msd

elif k_given == 2:
    if ndigits < 2:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 100:
            msd1 //=10
        msd2 = msd1%10
        msd1 = msd1//10

        if(ndigits > 2):
            ans += cmb(ndigits-1,2)*pow(9,2)
        ans += (msd1-1)*(ndigits-1)*9
        ans += (ndigits-2)*9+msd2

else:
    if ndigits < 3:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 1000:
            msd1 //=10
        msd3 = msd1%10
        msd1 = msd1//10
        msd2 = msd1%10
        msd1 = msd1//10
        
        if(ndigits > 3):#XX XO
            ans += cmb(ndigits-1,3)*pow(9,3)
        if(ndigits > 3 and msd2 > 0):#OX
            ans += cmb(ndigits-2,2)*pow(9,2)*(msd1)
        if(ndigits > 3 and msd2 ==0):
            ans += msd1 * calc2(n_given - msd1*(10**(ndigits-1),2)
        if(ndigits > 3 and msd2 > 0):#OO
            ans += (ndigits-3)*msd1*msd2*9
        ans += (msd1-1) * 81 + msd2*msd3

print(ans)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb
import math
N=input()
K=int(input())
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: Runtime Error

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

n = int(input())
k = int(input())
l = len(str(n))
a = n//(10**(l-1))
b1 = 0
b2 = 0
c1 = 0
c2 = 0
c = 0
x =0
y =0
if k == 1:
    c = 9*(l-1) + a
    print(c)

elif k == 2:
    for i in range(1,l):
        if n%(10**(l-i)) >= 10**(l-i-1):
            b1 = l - i - 1
            b2 = (n%(10**(l-i)))//(10**(l-i-1))
            break
    c = 81*(l-1)*(l-2)//2 + (a-1)*9*(l-1) + b2 + b1*9
    print(c)

else:
    for i in range(1,l):
        if n%(10**(l-i)) >= 10**(l-i-1):
            b1 = l - i - 1
            b2 = (n%(10**(l-i)))//(10**(l-i-1))
            x = i
            break
    for i in range(x+1,l):
        if n%(10**(l-i)) >= 10**(l-i-1):
            c1 = l - i - 2
            c2 = (n%(10**(l-i)))//(10**(l-i-1))
            
            break        
    for i in range(2,l-1):
        y += comb(i,2)
    c = 729*y + (a-1)*729*comb(l-1,2) + 81*comb(b1,2) + (b2-1)*b1*9 +c1*9 +c2
    print(c)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def com(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 run():
  N = int(input())
  K = int(input())
  Nnum = len(str(N))
  #1
  all1 = com(Nnum, K)*9**K
  #2
  all2 = (9-int(str(N)[0]))*com(Nnum-1, K-1)*9**(K-1)
  if K == 1:
    print(all1-all2)
  #3
  elif K == 2:
    all3 = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        all3 += 9-N2
        break
      all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
  #4
  else:
    all3 = 0
    count = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        if count == 0:
          all3 += (9-N2)*com(Nnum-n-1, 1)*9
        elif count == 1:
          all3 += 9-N2
        count += 1
        if count == 2:
          break
      elif count == 0:
        all3 += 9*(Nnum-n-1)*9
      else:
        all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
    
  

if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
def Pika(p,K):
    tmp = 1
    now = p
    for i in range(K):
        tmp *= now
        now -= 1
    now = 1
    for i in range(K):
        tmp //= now
        now += 1
    tmp *= 9**K
    return tmp

N = input()
K = int(input())
p = len(N)
def solve(N,K,p):
    if K==0:
        return 1
    ans = 0

    ans += Pika(p-1,K)

    atama = int(N[0])
    ans += (atama-1)*Pika(p-1,K-1)
    ans += solve(N[1:],K-1,p-1)
    
    return ans
A = solve (N,K,p)
print(A)