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:
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:
        ans=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)
        elif k==1:
            ans += 1
    #print(n,k,ans)
    return ans
    

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

tot = calc(N,K)

print(tot)

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

def mitukeru_not_zero(num):
    for i in range(len(str(num))):
        if i != 0 and str(num)[i] != "0":
            return i
    else:
        return -1 

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

Submission status: Runtime Error

Solution code:
n=int(input())
k=int(input())
m=str(n)
l=len(m)
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:
  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]))

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())
def comb(a, b):
    if b == 1:
        return a
    if b == 2:
        return a*(a-1)//2
    if b == 3:
        return a*(a-1)*(a-2)//6
ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    ans += comb(L-1,s)*(9**s)
    if s-1 > 0:
        ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
ans += int(N[K-1])
print(ans)

Submission status: Runtime Error

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

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)):
            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):
                                P=str(int(str(n)[i]))+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[i])-1)
    print(counter)

Submission status: Runtime Error

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

count = 0
for i in range(0, n+1):
    s = str(i).replace('0', '')
    if sum(Counter(s).values()) == k:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
k = int(input())
keta = len(str(n))
from math import factorial
if k <= keta:
    al = (factorial(keta) / factorial(k) / factorial(keta - k)) * 81
    diff = 0
    if k == 2:
        diff += (9-int(str(n)[0]))*9*(keta-1)
        diff += 9-int(str(n)[1])
    elif k == 3:
        c = (factorial(keta-1) / factorial(k) / factorial(keta-1 - k))
        diff += (9-int(str(n)[0]))*81*c
        c = (factorial(keta-2) / factorial(k) / factorial(keta-2 - k))
        diff += (9-int(str(n)[1]))*9*c
        diff += 9-int(str(n)[2])
    elif k == 1:
        diff += 9-int(str(n)[0])
    al = (factorial(keta) / factorial(k) / factorial(keta - k)) * (9**k)
    print(int(al-diff))
else:
    print(0)

Submission status: Runtime Error

Solution code:
def comb(a, b):
    if b == 1:
        return a
    if b == 2:
        return a*(a-1)//2
    if b == 3:
        return a*(a-1)*(a-2)//6
N = input()

K = int(input())

ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    ans += comb(L-1,s)*(9**(s))
    if s-1 > 0:
        ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
ans += int(N[K-1])
print(int(ans))

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
m = len(list(str(n)))
n0 = list(str(n))
for i in range(m):
    n0[i] = int(n0[i])
ans = 0
comb = 1
if k < m:
    for j in range(k):
        comb *= (m-1-j)
        comb //= (j+1)
    ans += comb*(9**k)
#print(ans,k,m)
if k == 1:
    ans += n0[0]
elif k == 2:
    if m >= 2:
        ans += (n0[0]-1)*9*(m-1)
        c = 1
        while n0[c] == 0 and c < m-1:
            c += 1
        if n0[c] > 0:
            ans += n0[c]
            ans += 9*(m-c-1)
    else:
        ans = 0
else:
    if m >= 3:
        ans += (n0[0]-1)*9*9*(m-1)*(m-2)//2
        c = 1
        while n0[c] == 0 and c <= m-2:
            c += 1
        if c < m-1:
            ans += (n0[c]-1)*9*(m-c-1)
            ans += 9*9*(m-c-1)*(m-c-2)//2
            c1 = c+1
            while n0[c1] == 0 and c < m-1:
                c1 += 1
            if n0[c1] > 0:
                ans += n0[c1]
                ans += 9*(m-c1-1)
    else:
        ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
import sys,math

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

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

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


main()

Submission status: Runtime Error

Solution code:
import math

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

N = input()
K = int(input())
ans = 0
for i in range(1, len(N)):
  if i < K:
    pass
  else:
    ans += 9 ** K * Comb(i-1, K-1)
ans += (int(N[0])-1) * Comb(len(N)-1, K-1) * 9 ** (K-1)
if K == 1:
  ans += 1
elif K == 2:
  for i in range(1, len(N)):
    if N[i] != '0':
      ans += int(N[i]) + 9 * (len(N) - i - 1)
      break
else:
  for i in range(1, len(N)):
    if N[i] != '0':
      if len(N) - i - 1 >= 2:
        ans += Comb(len(N) - i - 1, 2) * 9 ** 2
      if len(N) - i - 1 >= 1:
        ans += (int(N[i]) - 1) * 9 * (len(N) - i - 1)
      for j in range(i+1, len(N)):
        if N[j] != '0':
          ans += int(N[j]) + 9 * (len(N) - j - 1)
          break
      break
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
k=int(input())
d=len(str(n))
from math import factorial as f
def c(n):
  if n<2:
    return 0
  else:
    return f(n)//(f(n-2)*f(2))
def kk(n):
  dd=len(str(n))
  s=9*(dd-1)
  s+=int(str(n)[0])
  return s
def kkk(n):
  d=len(str(n))
  s=81*(d-1)*(d-2)//2
  s+=9*(d-1)*(int(str(n)[0])-1)
  s+=kk(int(str(n)[1:]))
  return s

if k==1:
  ans=kk(n)
elif k==2:
  ans=kkk(n)
else:
  t=0
  for i in range(2,d-1):
    t+=c(i)
  ans=729*t
  ans+=81*c(d-1)*(int(str(n)[0])-1)
  ans+=kkk(int(str(n)[1:]))
print(ans)

Submission status: Runtime Error

Solution code:
def comb(a, b):
	if b == 1:
		return a
    if b == 2:
    	return a*(a-1)//2
	if b == 3:
     	return a*(a-1)*(a-2)//6
N = input()

K = int(input())

ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    ans += comb(L-1,s)*(9**(s))
	if s-1 > 0:
		ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
ans += int(N[K-1])
print(int(ans))

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)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    for a in range(int(str(n)[i]),int(str(n)[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
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[i])-1)
    print(counter)

Submission status: Runtime Error

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

count = 0

for i in range(1, N + 1):
  s = str(i)
  count_len = len(s)
  count_zero = s.count('0')
  count_not0 = count_len - count_zero
  if (count_not0 == K):
    count += 1

print(count)

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

c = factorial(length) // factorial(K) // factorial(lenght-K)
c_1 = factorial(length-1) // factorial(K-1) // factorial(lenght-K-1)
print(c)
answer = 0
top = int(str(N)[0])
answer = factorial(length-1) // factorial(K) // factorial(lenght-K-1) * 9 ** K # 一個前まで
answer += factorial(length) // factorial(K) // factorial(lenght-K) * (top-1) * 9 ** K # 一桁目がtopより小さい数
print(answer)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:


#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

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

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



def main():
    s = list(input())
    n = len(s)
    k = ii()
    ans = 0

    if n == k:
        for i in range(n):
            ans+= pow(9,k-i-1)*(int(s[i])-1)
        ans+=1
        print(ans)
        exit()




    for i in range(k):
        tmp = int(s[i])
        if i == 0:
            ans+=(9**k)*com(n-1,k)
 #           print(n-1,k-1)
            ans+=(9**(k-1))*com(n-1,k-1)*(tmp-1)
 #           print(i,ans)
        else:
            ans+=(9**(k-i))*com(n-1-i,k-i)
            if tmp > 0:
                ans+=(9**(k-i-1))*com(n-1-i,k-i-1)*(tmp-1)
#            print(i,ans)
    ans+=1
    print(ans)





main()

Submission status: Runtime Error

Solution code:
def comb(a, b):
	if b == 1:
        return a
    if b == 2:
        return a*(a-1)//2
    if b == 3:
        return a*(a-1)*(a-2)//6
N = input()

K = int(input())

ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    ans += comb(L-1,s)*(9**(s))
	if s-1 > 0:
		ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
ans += int(N[K-1])
print(int(ans))

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)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    for a in range(int(str(n)[i]),int(str(n)[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
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[i])-1)
    print(counter)

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)-1)*(X(N)-2)*81) + 9*(X(N)-1)*(int(str(N)[0])-1) + solve_k1(int(str(N)[1:])))
else:
    raise TypeError

Submission status: Runtime Error

Solution code:
from math import factorial
N = int(input())
K = int(input())


def n_C_k(n, k):
    factorial_n = factorial(n)
    factorial_k = factorial(k)
    factorial_nk = factorial(n-k)
    return factorial_n//(factorial_k*factorial_nk)

def solve(N, k):
    #ls = list(str(N))
    n = str(N)
    keta = len(n)

    if k == 0:
        return 0

    t = n[0]
    s = ""

    for i in range(keta-1):
        t += "0"
    for i in range(keta-1):
        s += n[i+1]
    return solve2(t, k) + solve(s, k-1)

def solve2(t, k):
    n = str(t)
    keta = len(n)
    #print(keta, )
    if k == 1:
        print(t, k)
        print((keta-1)*9+int(n[0]))
        return (keta-1)*9+int(n[0])
    if k == 2:
        out = 0
        out += (int(n[0])-1)*(keta-1)*9 #最上桁を使う場合
        #print(out, 5555)
        if keta-1 >= 2:
            out += n_C_k(keta-1, 2)*9*9  # 最上桁を使わない場合
        print(t, k)
        print(out)
        return out
    else:
        out = 0
        if keta-1 >= 2:
            out += (int(n[0])-1)*n_C_k(keta-1, 2)*9*9
        if keta-1 >= 3:
            out += n_C_k(keta-1, 3)*9*9*9
        return out

    
ans = solve(N, K)
print(ans)

Submission status: Runtime Error

Solution code:
a = int(input())
b = int(input())
def aez(n, k):
    s = str(n)
    ln = len(s)-1
    n1 = int(s[0])
    if k == 1:
        return 9 * ln + n1 
    elif k == 2:
        return (81 * ln * (ln-1) // 2) + aez(int('9'*ln), 1)*(n1-1) + aez(int(s[1:]), 1)
    else:
        return (729*ln*(ln-1)*(ln-2)//6) + aez(int('9'*ln), 2)*(n1-1) + aez(int(s[1:]), 2)
print(aez(a, b))

Submission status: Runtime Error

Solution code:
def comb(a, b):
    if b == 1:
        return a
    if b == 2:
        return a*(a-1)//2
    if b == 3:
        return a*(a-1)*(a-2)//6
N = input()

K = int(input())

ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    #0
    ans += comb(L-1,s)*(9**(s))
    #1~N[0]-1
    if s-1 > 0:
        ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
    #N[0]
ans += int(N[K-1])
print(int(ans))

Submission status: Runtime Error

Solution code:
N_str = str(input())
K = int(input())

digit_length = len(N_str)
topmost_digit = int(N_str[0])

C_table = [[0, 0, 0] for _ in range(digit_length)]


def C(all, pick):
    if C_table[all][pick] == 0:
        count_child = 1
        count_parent = 1
        for i in range(pick):
            count_child *= all - i
            count_parent *= i + 1
        C_table[all][pick] = count_child // count_parent
    return C_table[all][pick]


def get_count(top_digit, digit_count, needed_nonzero):
    if needed_nonzero <= 0 or needed_nonzero > digit_count:
        return 0

    if digit_count == 1:
        if needed_nonzero == 1:
            return top_digit
        else:
            return 0

    if top_digit == 0:
        return get_count(int(N_str[digit_length - digit_count + 1]) ,digit_count - 1, needed_nonzero)

    if top_digit >= 1:
        count = C(digit_count - 1, needed_nonzero) * (9 ** needed_nonzero)
        if needed_nonzero == 1:
            count += 1

    if top_digit > 1:
        count += C(digit_count - 1, needed_nonzero - 1) * (9 ** (needed_nonzero - 1)) * (top_digit - 1)

    return count + get_count(int(N_str[digit_length - digit_count + 1]) ,digit_count - 1, needed_nonzero - 1)


print(get_count(topmost_digit, digit_length, K))

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
k = int(input())
keta = len(str(n))
from math import factorial
al = (factorial(keta) / factorial(k) / factorial(keta - k)) * 81
diff = 0
if k == 2:
    diff += (9-int(str(n)[0]))*9*(keta-1)
    diff += 9-int(str(n)[1])
elif k == 3:
    c = (factorial(keta-1) / factorial(k) / factorial(keta-1 - k))
    diff += (9-int(str(n)[0]))*81*c
    c = (factorial(keta-2) / factorial(k) / factorial(keta-2 - k))
    diff += (9-int(str(n)[1]))*9*c
    diff += 9-int(str(n)[2])
elif k == 1:
    diff += 9-int(str(n)[0])
al = (factorial(keta) / factorial(k) / factorial(keta - k)) * (9**k)
print(int(al-diff))

Submission status: Runtime Error

Solution code:
import sys,math

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

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

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


main()

Submission status: Runtime Error

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

M = len(str(N)) # 桁数

def solve_1(n,m):
    ans = 0
    ans += 9*(m-1)
    x = n//(10**(m-1))
    ans += x
    return ans

def solve_2(n,m):
    ans=0
    if m<1:
        return ans
    elif m>2:
        ans+= (9**2)*int((m-2)*(m-1)/2) 

    x = n//(10**(m-1))
    ans+= (x-1)*(m-1)*9
    ans+= int(str(n)[1])+9*(m-2)
    return ans

def solve_3(n,m):
    ans=0
    if m<2:
        return ans
    elif m>3:
        ans+=int((9**3)*(1/6)*(m-1)*(m-2)*(m-3))
    
    x = n//(10**(m-1))
    ans+=int((x-1)*(m-1)*(m-2)/2*81)
    ans+=solve_2(int(str(n)[1:]),m-1)
    return ans

if K==1:
    ans = solve_1(N,M)
if K==2:
    ans = solve_2(N,M)
if K==3:
    ans = solve_3(N,M)

print(ans)

Submission status: Runtime Error

Solution code:
s = input()
ind = len(n)
n = int(s)

k = int(input())

memo = [[None]*(k+1) for _ in range(ind+1)]

memo[1][1] = 9
memo[1][2] = 0
memo[1][3] = 0

for i in range(2,ind+1):
  for j in range(k+1):
    if j == 0:
      ans == 1
    elif i<j:
      ans == 0
    elif i+j==n:
      ans = int(s[n-i])*memo[i-1][j-1] + memo[i-1][j]
    else:
      ans = 9*memo[i-1][j-1] + memo[i-1][j]
    memo[i][j] = ans
    
print(memo[ind][k])

Submission status: Runtime Error

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



N = int(input())
K = int(input())
SN = str(N)
LN = list(SN)
keta =len(LN)
Nzer = keta-K
Nsei = K
output = 0

output += comb(keta,K,10**9+7)*9**K
t = 0
while K-1-t>=0:
    output -= (9-int(LN[t]))*comb(keta-1-t,K-1-t,10**9+7)*9**(K-1-t)
    t += 1
print(output)

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
l = len(str(N))
t = 9 ** K

ans = 0
x = 1
if K == 1:
    ans += (l-1) * t
    ans += int(str(N)[0])
    print(ans)

if K == 2:
    for i in range(K, l - 1):
        x += i

    ans += t * x
    ns = str(N)
    atama = ns[0]

    y = (int(atama)) * 9 ** (K - 1)
    ans += y * (l - 2)

    ans += (int(atama) - 1) * 9 ** (K - 1)
    w = ns[1:K]
    ans += int(w)
    print(ans)

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  print(0)
print(cnt)

Submission status: Runtime Error

Solution code:

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

keta = len(n)
ans = 0
if k == 1:
    ans += 9 * (keta-1) + int(n[0])
    
if k == 2:
    ans +=int(n[0])*9*(keta-1) - (9-int(n[1])) + 81*(keta-2)*(keta-1)/2

if k == 3:
    ans += int(n[0])*81*(keta-1)*(keta-2)/2 - (10-int(n[1]))*9 + (int(n[2]))
    for i in range(keta-2):
        ans += 729*(keta-i-2)*(keta-i-3)/2



print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.special import comb
N = input()
K = int(input())

ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    #0
    ans += comb(L-1,s)*(9**(s))
    #1~N[0]-1
    if s-1 > 0:
        ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
    #N[0]
ans += int(N[K-1])
print(int(ans))

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
x=math.floor(math.log10(N))+1
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if x<K:
  print(0)
  exit(0)
if K==1:
  ans=(x-1)*9
  ans+=(N//10**(x-1))
  print(ans)
elif K==2:
  for i in range(2,x):
    ans+=(9**2)*(i-1)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  ans+=(f-1)*9*(x-1)
  ans+=9*(s_n-1)
  ans+=s
  print(ans)
else:
  for i in range(3,x):
    ans+=(9**3)*combinations_count(i-1,2)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  for i in range(x-s_n+1,x):
    if n[i]!='0':
      t_n=x-i
      t=int(n[i])
      break
  ans+=(f-1)*9**2*combinations_count(x-1,2)
  ans+=9**2*combinations_count(s_n-1,2)
  ans+=(s-1)*9*(s_n-1)
  ans+=9*(t_n-1)
  ans+=t
  print(ans)

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
        break

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:
def main():
    n_str = input()
    k = int(input())
    keta = len(n_str)

    def k1():
        ans = keta*9 - (9-int(n_str[0]))
        print(ans)

    def k2():
        ans = (
            (keta*(keta-1)//2) * 9**2
            - (9-int(n_str[0])) * (keta-1) * 9
            - (9-int(n_str[1]))
        )
        print(ans)

    def k3():
        ans = (
            (keta*(keta-1)*(keta-2)//6) * 9**3
            - (9-int(n_str[0])) * ((keta-1)*(keta-2)//2) * 9**2
            - (9-int(n_str[1])) * (keta-2) * 9
            - (9-int(n_str[2]))
        )
        print(ans)

    if k == 1:
        k1()
    elif k == 2:
        k2()
    else:
        k3()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
x=math.floor(math.log10(N))+1
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if K==1:
  ans=(x-1)*9
  ans+=(N//10**(x-1))
  print(ans)
elif K==2:
  for i in range(2,x):
    ans+=(9**2)*(i-1)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  ans+=(f-1)*9*(x-1)
  ans+=9*(s_n-1)
  ans+=s
  print(ans)
else:
  for i in range(3,x):
    ans+=(9**3)*combinations_count(i-1,2)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  for i in range(x-s_n+1,x):
    if n[i]!='0':
      t_n=x-i
      t=int(n[i])
      break
  ans+=(f-1)*9**2*combinations_count(x-1,2)
  ans+=9**2*combinations_count(s_n-1,2)
  ans+=(s-1)*9*(s_n-1)
  ans+=9*(t_n-1)
  ans+=t
  print(ans)