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 f2(n):
    c = len(n)-1
    nn = n[1:]
    s = c*(c-1)//2 * 9*9 
    s += c * (int(n[0])-1)*9
    s += (len(nn)-1)*9 + int(nn[0])
    return s

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

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

if k == 3:
    c = len(n)-1
    nn = n[1:]
    s = c*(c-1)*(c-2)//(3*2) * 9*9*9
    s += (int(n[0])-1) * c*(c-1)//2 * 9*9 
    s += f2(nn)
    print(s)

Submission status: Runtime Error

Solution code:
def nCk(n, k):
  return factorial(n)/factorial(n-k)/factorial(k)

from math import factorial
N = input()
K = int(input())
order = len(N)
diff = order - K 
if order < K:
  print(0)

s = int(N[0])
#lower  = factorial(order-1)/factorial(diff-1)/ factorial(K) * (9**K)
if order - 1 >= K:
  lower = nCk(order - 1, K) * (9**K)
else:
  lower = 0
total = lower
for i in range(1, s):
#  total += factorial(order-1)/factorial(diff)/ factorial(K-1) * (9**(K-1))
  total += nCk(order - 1, K - 1) * (9**(K-1))

if K == 1:
  total += 1
elif K == 2:
  under = int(N[1:])
  num = "0"*(order -1)
  for k in range(order - 1):
    for kk in range(1, 10):
      tmp = num[:k] + str(kk) + num[k+1:]
      if int(tmp) <= under:
        total += 1
elif K == 3:
  under = int(N[1:])
  num = "0"*(order -1)
  for k in range(1, order - 1):
    for j in range(k):
      for kk in range(1, 10):
        for jj in range(1, 10):
          tmp = num[:j] + str(jj) + num[j+1:k] +str(kk) +  num[k+1:]
          if int(tmp) <= under:
            total += 1
            

print(int(total))
#pattern = factorial(order)/factorial(diff)/ factorial(K) * (9**K)

Submission status: Runtime Error

Solution code:
def calc(n,k):
    while n[0] == '0' :n=n[1:]
    
    digit = len(n)
    if digit < k:
        return 0
    
    comb = [1]*(k+1)
    for i in range(1,k+1):
        comb[i] = comb[i-1] * (digit-i) //i
    if k==1:
        return 9*comb[1] + int(n[0])
    elif k==2:
        return (9**2)*comb[2] + (int(n[0])-1) * 9*comb[1] + calc(n[1:],1)
    elif k==3:
        return (9**3)*comb[3] + (int(n[0])-1) * (9**2) * comb[2] + calc(n[1:],2)

n=input()
k=int(input())
print(calc(n,k))

Submission status: Runtime Error

Solution code:
N = list(map(int,input()))
K = int(input())
L = len(N)

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

i = 0
D = [0] * K
M = K
for k in range(K):
    while N[i] == 0 and i < L:
        i += 1
    if i < L:
        D[k] = i
        i += 1
    else:
        M = k

ans = 0
for k in range(M):
    i = D[k]
    ans += comb(L-1-i,K-k)*(9**(K-k))
    ans += (N[i]-1) * comb(L-1-i,K-1-k)*(9**(K-1-k))
if K == M:
    ans += 1

print(ans)

Submission status: Runtime Error

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

if K == 1:
    c = int(N[0])
    c += (len(N) - 1) * 9
    print(c)

if K == 2:
    c = 0
    if N[0] == 1:
        d = 0
        d += int(N[1])
        d += (len(N) - 2) * 9
        d += int((len(N) - 1) * (len(N) - 2) / 2 * 81)
        print(d)
    else:
        d = 0
        d += int(N[1])
        d += (len(N) - 2) * 9
        d += (len(N) - 1) * 9 * (int(N[0]) - 1)
        d += int((len(N) - 1) * (len(N) - 2) / 2 * 81)
        print(d)

if K == 3:
    pass

Submission status: Runtime Error

Solution code:
# E
import numpy as np
import math
N=int(input())
K=int(input())

log_ind=int(np.log10(N))

ans1=math.factorial(log_ind+K-1)/math.factorial(log_ind-1)/math.factorial(K)*9

ans2=len([1 for i in range(10**log_ind, N+1) if str(i).count("0")==log_ind+1-K])

print(int(ans1+ans2))

Submission status: Runtime Error

Solution code:
from math import floor, log10
N = int(input())
K = int(input())
ans = 0
def X(num):
    return floor(log10(num)+1)

def solve_k1(num):
    return 9*(X(num)-1)+int(str(num)[0])

if K == 1:
    print(solve_k1(N))
elif K == 2:
    print(int(0.5*X(N)*(X(N)-1)*81 + solve_k1(int(str(N)[1:]))))
else:
    raise TypeError

Submission status: Runtime Error

Solution code:
import numpy as np 
import math
import itertools
N_str = input()
K = input()
base = len(N_str)
N = int(N_str)
K = int(K) 

cnt = 0
idx_candidates = [i for i in range(base)]
number_candidates = [i for i in range(1, 10)]
if N_str[:-1] == "9"*(base-1):
    cnt = math.factorial(base)/(math.factorial(base-K)*math.factorial(K)) * 9**K
    print(int(cnt))
else: 
    for idxs in itertools.combinations(idx_candidates, r=K):
        for nums in itertools.product(number_candidates, repeat=K): 
            number = ["0"] * base
            for i, idx in enumerate(idxs): 
                number[idx] =  str(nums[i])
            number = int("".join(number))
            if number <= N:
                cnt += 1    
    print(int(cnt))

Submission status: Runtime Error

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

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

dp[0][0][0] = 1
for i in range(n_num):
    for smaller in range(2):
        for j in range(n_num):
            lim = 9 if smaller else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = smaller | (x < n_list[i])
                dp[i + 1][nlt][ns] += dp[i][smaller][j]
ans = dp[n_num][0][k] + dp[n_num][1][k]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np 
import math
import itertools
N_str = input()
K = input()
base = len(N_str)
N = int(N_str)
K = int(K) 

cnt = 0
idx_candidates = [i for i in range(base)]
number_candidates = [i for i in range(1, 10)]
if N_str[:-1] == "9"*(base-1):
    cnt = math.factorial(base)/(math.factorial(base-K)*math.factorial(K)) * 9**K
    print(int(cnt))
    return 
for idxs in itertools.combinations(idx_candidates, r=K):
    for nums in itertools.product(number_candidates, repeat=K): 
        number = ["0"] * base
        for i, idx in enumerate(idxs): 
            number[idx] =  str(nums[i])
        number = int("".join(number))
        if number <= N:
            cnt += 1    
print(int(cnt))

Submission status: Runtime Error

Solution code:
import math

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

def calc(n, k):
    if n == 0:
        return 0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        return ans
    

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

tot = calc(N,K)+1

print(tot)

Submission status: Runtime Error

Solution code:
def comb(n,k):
  if k==0:
    return 1
  if k==1:
    return n
  if k==2:
    return n*(n-1)//2
  if k==3:
    return n*(n-1)*(n-2)//6
  return None
def cnt(n,k):
  if k==0:
    return 1
  return (comb(len(n)-1,k)*9**k
          +(int(n[0])-1)*comb(len(n)-1,k-1)*9**(k-1)
          +cnt(n[1:],k-1))
def main():
  n=input()
  k=int(input())
  print(cnt(n,k))
main()

Submission status: Runtime Error

Solution code:
# E
#import numpy as np
import math
N=int(input())
K=int(input())

log_ind=int(np.log10(N))

ans1=math.factorial(log_ind+K-1)/math.factorial(log_ind-1)/math.factorial(K)*9

ans2=len([1 for i in range(10**log_ind, N+1) if str(i).count("0")==log_ind+1-K])

print(int(ans1+ans2))

Submission status: Runtime Error

Solution code:
import math
import itertools

str_N = input()
K = int(input())
N = int(str_N)
zero_num = len(str_N)-K

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

def count():
    c = 0
    top = int(str_N[0])
    if K==3:
        for one in itertools.combinations(list(range(1,len(str_N))), K-1):
            a,b = one
            if a==1:
                c += (top-1)*int(str_N[a])*9+(int(str_N[a])-1)*9+int(str_N[b])
            else:
                c += top*9*9
    elif K==2:
        for one in range(1, len(str_N)):
            if one==1:
                c += (top-1)*9+int(str_N[one])
            else:
                c += top*9
    elif K==1:
        c+=top
    return c

ans = 0
if len(str_N)==K:
    ans += count()
else:
    ans += combinations_count(len(str_N)-1, K)*(9**K)
    ans += count()
print(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())
A = []
ans = 1


for i in range(K):
  n = int(str(N)[0])
  dig = len(str(N)) - 1
  A.append([n, dig])
  N -= n * 10**dig


for i in range(K):
  if A[i][1] >= K-i:
    ans += comb(A[i][1], K-i) * 9 ** (K-i) 
  ans += (A[i][0]-1) * comb(A[i][1], K-i-1) * 9 ** (K-i-1)
#  print(ans)

print(ans)

Submission status: Runtime Error

Solution code:
tmp=input()
n=int(tmp)
l=len(tmp)

k=int(input())
if k==1:
    ans=9*(l-1)
    last=int(tmp[0])
    ans+=last
    print(ans)
    exit()
if k==2:
    c=l-2
    ans=(9**2)*((c*(c+1))//2)
    num=0
    for i in range(1,l):
        for head_i in range(9,0,-1):
            for tail_i in range(9,0,-1):
                cal=str(head_i)
                cal+="0"*len(tmp[1:i])
                cal+=str(tail_i)
                cal+="0"*len(tmp[i+1:])
                if int(cal)<=n:
                    num+=1
    ans+=num
    print(ans)
    exit()
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

def calc(n, k):
    if n == 0:
        return 0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k < digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        return ans
    

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

tot = calc(N,K)+1

print(tot)

Submission status: Runtime Error

Solution code:
import math

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

str_n=input()
k=int(input())
cnt=0
dig = len(str_n)

#最上位桁が最大以外の場合　かつ　0でない場合
cnt += (int(str_n[0])-1)*combinations_count(dig-1,k-1)*9**(k-1)
#最上位桁が0の場合
if dig-1>=k:
  cnt += combinations_count(dig-1,k)*9**k

#最上位桁が最大の場合
if k==1:
  cnt+=1
else:
  ##第２非ゼロ桁の探索
  for i in range(dig-1):
    if str_n[i+1] != '0':
      dig2 = i+1
      break
  else:
    print(cnt)
    exit()
  ##第２非ゼロ桁が最大以外の場合　かつ　0でない場合
  cnt += (int(str_n[dig2])-1)*combinations_count(dig-1-dig2,k-2)*9**(k-2)
  ##第２非ゼロ桁が0の場合
  if dig-1-dig2>=k-1:
    cnt += combinations_count(dig-1-dig2,k-1)*9**(k-1)
  ##第２非ゼロ桁が最大の場合
  if k==2:
    cnt+=1
  else:
    ##第３非ゼロ桁の探索
    for i in range(dig-1-dig2):
      if str_n[i+1+dig2] != '0':
        dig3 = i+1+dig2
        break
    else:
      print(cnt)
      exit()
    ##第３非ゼロ桁が0でない場合
    cnt += int(str_n[dig3])
    ##第３非ゼロ桁が0の場合
    cnt += combinations_count(dig-1-dig3,k-2)*9**(k-2)
print(cnt)

Submission status: Runtime Error

Solution code:
import math 
def main():
  n = int(input())
  k = int(input())
  
  p = math.floor(math.log(n,10))
  
  res = 0;
  
  if k == 1:
    if p >= k:
      res += 9 * p
    res += int(str(n)[0])
  elif k == 2:
    if p >= k:
      res += 99 * (p-1)
    res += (int(str(n)[0])-1) * 9 + int(str(n)[1])
  else:
    if p >= k:
      res += 999 * (p-2)
    res += (int(str(n)[0])-1) * 99 + (int(str(n)[1])-1) * 9 + int(str(n)[2])
    
  
  print(res)
  
  return 
          
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            counter+=(int(str(n)[i])-1)*((99-i)*(98-i)//2)*9*9
            for j in range(i+1,100):
                for k  in range(j+1,100):
                    for b in range(1,10):
                        for c in range(1,10):
                            pp=str(n)[i]+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                            if 1<=int(pp)<=n:
                                counter+=1
    print(counter)

Submission status: Runtime Error

Solution code:
import math

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

def calc(n, k):
    ans = 0
    digits = int(math.log10(n))+1
    #Nより小さい桁数
    if k < digits-1:
        for n_dig in range(k, digits):
            ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
            #print(n_dig,tot)
    #Nと桁数が同じ
    top = n//10**(digits-1)
    ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
    if k>1:
        ans += calc(n-top*10**(digits-1), k-1)
    return ans
    

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

tot = calc(N,K)+1

print(tot)

Submission status: Runtime Error

Solution code:
def calc(n,k):
    digit = len(n)
    comb = [1]*(k+1)
    for i in range(1,k+1):
        comb[i] = comb[i-1] * (digit-i) //i
    if k==1:
        return 9*comb[1] + int(n[0])
    elif k==2:
        return (9**2)*comb[2] + (int(n[0])-1) * 9*(digit-1) + calc(n[1:],1)
    elif k==3:
        return (9**3)*comb[3] + (int(n[0])-1) * (9**2) * comb[2] + calc(n[1:],2)

n=input()
k=int(input())
print(calc(n,k))

Submission status: Runtime Error

Solution code:
import sys

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

n=input()
k = int(input())
l = len(n)

if l == 1:
    if k >= 2:
        print(0)
        sys.exit()
    print(top)
    sys.exit()

top = int(n[0])

if k == 1:
    z = 9
elif k == 2:
    z = 81
else:
    z = 729

ans = comb(l - 1, k) * z
ans += comb(l - 1, k - 1) * (top - 1) * (z // 9)

if k == 1:
    ans+=top    
elif k == 2:
    for i in range(1, l):
        if i==1 or int(n[1:i]) == 0:
            ans += int(n[i])
        else:
            ans += 9
elif k == 3:
    for i in range(1, l):
        for j in range(i + 1, l):
            flag1 = i == 1 or int(n[1:i]) == 0
            flag2 = j == i + 1 or int(n[i + 1 :j]) == 0
            if not(flag1) and not(flag2):
                ans += 81
            elif flag1 and not (flag2):
                ans += 9 * int(n[i])
            elif not (flag1) and flag2:
                ans += 81
            else:
                ans += 9 * (int(n[i]) - 1) + int(n[j])

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()
S = str(N)

def calc1(S):
    bl = len(S)
    return int(S[0])+9*(bl-1)

def calc2(S):
    bl = len(S)
    ans = 0
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    ans += calc1(S[1:])
    return ans

def calc3(S):
    bl = len(S)
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    ans += calc2(S[1:])
    return ans

if K==1:
    print(calc1(S))
if K==2:
    print(calc2(S))
if K==3:
    print(calc3(S))

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

def f(n_str, k):
  while n_str[0] == '0':
    n_str = n_str[1:]
  if n_str == "":
    return 0
  if k == 1:
    return int(n_str[0]) + 9 * (len(n_str) - 1)
  else:
    return (int(n_str[0]) - 1) * f('9' * (len(n_str) - 1), k - 1) + f(n_str[1:], k - 1) + 9 ** k * comb(len(n_str) - 1, k, exact=True)

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

print(f(n, k))

Submission status: Runtime Error

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

l = len(str(N))
a = N // 10**(l - 1)
b = N // 10**(l - 2)
c = N // 10**(l - 3)

d = b - 10 * a
e = c - 100 * a - 10 * d

if K == 1:
    ans = 9 * (l - 1) + a
    print(ans)
elif K == 2:
    if l == 1:
        print(0)
    else:
        ans = 81 * (l - 1) * (l - 2) // 2
        ans += (a - 1) * 9 * (l - 1) + 9 * (l - 2) + d
        print(ans)
else:
    if l == 1 or l == 2:
        print(0)
    else:
        ans = 729 * (l - 1) * (l - 2) * (l - 3) // 6
        ans += (a - 1) * 81 * (l - 1) * (l - 2) // 2
        ans += 81 * (l - 2) * (l - 3) // 2
        if d != 0:
            ans += (d - 1) * 9 * (l - 2)
        ans += (l - 3) * 9 + e

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if K == 1:
        y = Z[0]
        ans += (m-1) * 9 + y
        #print(ans)
    elif K == 2:
        #0 
        ans += ((m-1) * (m-2) // 2) * 9 * 9
        #print(ans)
        #mid
        ans += (Z[0]-1) * (m-1) * 9
        #print(ans)
        #max
        K -= 1
        m -= 1
        Z = Z[1:]
        ans += nn(Z,K,m)
        #print(ans)
    elif K == 3:
        #0 
        ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
        #print(ans)
        #mid
        ans += (Z[0]-1) * ((m-1) * (m-2) // 2) * 9 * 9
        #print(ans)
        #max
        K -= 1
        m -= 1
        Z = Z[1:]
        ans += nn(Z,K,m)
    return ans
ans = nn(Z,K,m)        
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial as fac

def comb(n,r):
    if ( r<0 or r>n ):
        return 0
    return fac(n)/(fac(r)*fac(n-r))


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

nn=str(n)
keta=len(nn)

ans=0


for i in range(k):
    ans+=comb(keta-i-1,k-i)*9**(k-i)
    if int(nn[i])-1>=0:
        ans+=(int(nn[i])-1)*comb(keta-i-1,k-i-1)*9**(k-i-1)



print(int(ans)+1)

Submission status: Runtime Error

Solution code:
n=int(input())
k=int(input())
if k==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif k==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif k==3:
    K=str(n)
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    for a in range(1,int(K[i])+1):
                        for b in range(1,10):
                            for c in range(1,10):
                                P=str(a)+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
    print(counter)

Submission status: Runtime Error

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

def K1(N):
    res = 0
    if N < 10:
        res = N
    else:
        l = len(str(N))
        res += 9*(l-1)
        res += N // (10**(l-1))
    return res

if K==1:
    print(K1(N))

else:
    print(usitapunichiakun)

Submission status: Runtime Error

Solution code:
import itertools

def comb(a,b):
    if a<=0:
        return 0
    if b==1:
        return a
    elif b==2:
        return a*(a-1)//2
    else:
        return a*(a-1)*(a-2)//6

def tmp(L, K):
    ret=[]
    if K==1:
        bases=itertools.combinations(range(L+1),K)    
        for b in bases:
            ret+=[ k*10**b[0] for k in range(1,10)]
    if K==2:
        bases=itertools.combinations(range(L+1),K)
        kk=list(itertools.product(range(1,10),range(1,10)))
        for b in bases:
            ret+=[ k[0]*10**b[0] + k[1]*10**b[1] for k in kk]
    return ret

Nst=input()
K=int(input())
L=len(Nst)
N1=int(Nst[0])
N2=int(Nst[1])

if K==1:
    ans=comb( L-1, K) * 9 + N1
elif K>=2:
    ans=comb( L-1, K) * 9**(K) + comb( L-1, K-1) * 9**(K-1) *(N1-1)
    lst=[ 10**(L-1)*N1 + a for a in tmp(L-1, K-1)]
    ans+=sum([x <= int(Nst) for x in lst])
print (ans)

Submission status: Runtime Error

Solution code:
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <stdio.h>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}

using namespace std;


int main(){
	string s;
	int k;
	cin >> s >> k;
	int n = s.size()-1;
	int N = n;
	ll ans = 0;
	/*rip(i,k,0){
		ans *= (n-i)*9;
		ans /= i+1;
	}
	cout << ans << endl;*/
	while(n > -1 && k > 0){
		if(s[N-n] == '0'){
			n--;
			continue;
		}
		ll add = s[N - n] -'0'-1;
		rip(i,k-1,0){
			add *= (n-i)*9;
			add /= i+1;
		}
		//cout << n MM k MM add << endl;
		ans += add;
		add = 1;
		rip(i,k,0){
			add *= (n-i)*9;
			add/=i+1;
		}
		ans += add;
		k--;
		n--;
	}
	if(k==0) ans++;
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()

S = str(N)
bl = len(S)

if K==1:
    #print(int(S[0])+9*(bl-1))
    ans = 0
    flag = False
    for s in S:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    print(ans)

if K==2:
    print(ans)
    ans = 0
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)

if K==3:
    print(ans)
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    S = S[1:]
    bl = len(S)
    ans += (int(S[0])-1)*9*(bl-1)
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()

S = str(N)
bl = len(S)

if K==1:
    #print(int(S[0])+9*(bl-1))
    ans = 0
    flag = False
    for s in S:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    print(ans)

if K==2:
    print(ans)
    ans = 0
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)

if K==3:
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    S = S[1:]
    bl = len(S)
    ans += (int(S[0])-1)*9*(bl-1)
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
n=list(input())
N=len(n)
k=int(input())
dp=[[0 for i in range(len(n))] for j in range(k)]
ans=0
x=int(n[0])

if k==1:
  ans+=(N-1)*9
  ans+=x
  print(ans)
  sys.exit()

elif k==2:
  ans+=(N-1)*(N-2)*81//2
  ans+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans+=(N2-1)*9
  ans+=x
  print(ans)
  sys.exit()

else:
  ans+=(N-1)*(N-2)*(N-3)*729//6
  ans+=(x-1)*(N-1)*(N-2)*81//2
  n=n[1:N+1]
  N=len(n)
  x=int(n[0])
  ans2=0
  ans2+=(N-1)*(N-2)*81//2
  ans2+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans2+=(N2-1)*9
  ans2+=x
  ans+=ans2
  print(ans)
  sys.exit()

Submission status: Runtime Error

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

dp = [[0] * 2 for _ in range(n_num + 1)]
dp[0][0] = 1
for i in range(n_num):
    nxt = [[0] * 2 for _ in range(n_num + 1)]
    for j in range(n_num):
        for l in range(2):
            lim = 9 if l else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = l | (x < n_list[i])
                nxt[ns][nlt] += dp[j][l]
    dp = copy.deepcopy(nxt)
ans = dp[k][0] + dp[k][1]
print(ans)

Submission status: Runtime Error

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

if K == 1:
    N = str(N)
    ans = (len(N)-1) * (len(N)-2) * 9
    ans += int(N[0])
    print(ans)
    # N = str(N)
    # ans = 9*(len(N)-1)+int(N[0])
    # print(ans)
elif K == 2:
    N = str(N)
    # 最上位を避けた
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位ともう一つ
    ans += (int(N[0])-1) * (len(N)-1) * 9
    # 最上位の桁のみを選ぶ場合
    ans += 1 * int(N[1])
    # 最上位+何か
    ans += 1 * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    # 最上位を避けた選び方
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他
    ans += int(N[0]) * int(N[1]) * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)

Submission status: Runtime Error

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

if K == 1:
    cnt = 9 * (l - 1) + N // (10 ** (l - 1))
elif K == 2:
    a = int(str(N)[0])
    b = int(str(N)[1])
    cnt = 81 * ((l - 1) * (l - 2) // 2) + 9 * a * (l - 2) + (a - 1) * 9 + b
else:
    a = int(str(N)[0])
    b = int(str(N)[1])
    c = int(str(N)[2])
    cnt = 9 ** 3 * ((l - 1) * (l - 2) * (l - 3) // 6) + a * 9 * 9 * ((l - 2) * (l - 3) // 2) + (a - 1) * 9 * 9 * (l - 2) + (b - 1) * 9 * (l - 2) + 9 * (l - 3) + c

print(cnt)

Submission status: Runtime Error

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

dp = [[0] * 2 for _ in range(n_num)]
dp[0][0] = 1
for i in range(n_num):
    nxt = [[0] * 2 for _ in range(n_num + 1)]
    for j in range(n_num):
        for l in range(2):
            lim = 9 if l else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = l | (x < n_list[i])
                nxt[ns][nlt] += dp[j][l]
    dp = copy.deepcopy(nxt)
ans = dp[k][0] + dp[k][1]
print(ans)