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 combi(n,r):
    if r > n:return 0
    return math.factorial(n) // (math.factorial(n - r)*(math.factorial(r)))


def solve(i,k,smaller):
    #一番最後の桁まで調べたら終了
    if i == N:
        if k == 0:return 1
        else: 0
    #途中であっても0以外の数字を使い切ったら終了
    if k == 0:return 1

    #Nより小さいことが確定すれば残りの桁数（N-i）のうち
    #k個所に0以外の数字（9**k通り）を使い，それ以外の桁の数字は0なので
    #C(n-i,n-i-k)=C(n-i,k)個所に0をはめる
    if smaller: return combi(N-i, k)*(9**k)
    else:
        #i桁目が0なら，smallerであるといえない
        if S[i] == '0':return solve(i+1,k,False)
        else:
            zero = solve(i+1, k, True)
            aida = solve(i+1, k-1, True) * (int(S[i])-1)
            icchi = solve(i+1, k-1, False)
            return zero + aida + icchi

#0出ない数字がちょうどＫ個であるようなN以下の整数を探索
S = input()
N = len(S)
K = int(input())
print((solve(0,K,False)))

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):
    L = len(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

s = input()
k = int(input())
r = 0
d = k

def p(n, k):
  if n == k:
  	return 1
  else:
    return math.factorial(n) // math.factorial(n - k)

def c(n, k):
  if n == 0 or k == 0:
    return 0
  else:
    return p(n, k) // math.factorial(k)

while d <= len(s):
  if d == len(s):
    if k == 1:
      r += int(s[0])
    elif k == 2:
      r += int(s[1]) + (int(s[0]) - 1) * 9 + int(s[0]) * 9 * c(d - 2, 1)
    elif k == 3:
      r += int(s[2]) + (int(s[1]) - 1) * 9 + int(s[1]) * 9 * c(d - 3, 1) + (int(s[0]) - 1) * 81 * c(d - 2, 1) + int(s[0]) * 81 * c(d - 2, 2)
  else:
    if k == 1:
      r += 9
    elif k == 2:
      r += 9 * 9 * c(d - 1, 1)
    elif k == 3:
      r += 9 * 81 * c(d - 1, 2)
  d += 1
    
print(r)

Submission status: Runtime Error

Solution code:
import math

s = input()
k = int(input())
r = 0
d = k

def p(n, k):
  return math.factorial(n) // math.factorial(n - k)

def c(n, k):
  if n == 0:
    return 0
  else:
    return p(n, k) // math.factorial(k)

while d <= len(s):
  if d == len(s):
    if k == 1:
      r += int(s[0])
    elif k == 2:
      r += int(s[1]) + (int(s[0]) - 1) * 9 + int(s[0]) * 9 * c(d - 2, 1)
    elif k == 3:
      r += int(s[2]) + (int(s[1]) - 1) * 9 + int(s[1]) * 9 * c(d - 3, 1) + (int(s[0]) - 1) * 81 * c(d - 2, 1) + int(s[0]) * 81 * c(d - 2, 2)
  else:
    if k == 1:
      r += 9
    elif k == 2:
      r += 9 * 9 * c(d - 1, 1)
    elif k == 3:
      r += 9 * 81 * c(d - 1, 2)
  d += 1
    
print(r)

Submission status: Runtime Error

Solution code:


ar = input()

k = int(input())

l = len(ar)


DP = [[[-1] * 2 for j in range(5)] for i in range(102)]


def dp(i, j, fl):
    if i == l:
        if j == k:
            return 1
        else:
            return 0

    if DP[i][j][fl] != -1:
        return DP[i][j][fl]

    res = 0

   # print(i,j,fl)
    if fl:
        for p in range(10):

            res += dp(i+1, j + (p != 0) , fl == 1)
    else:
        ko = ord(ar[i]) - ord('0')
        for p in range(ko + 1):

            res += dp(i + 1, j + (p != 0), p < ko)
    DP[i][j][fl] = res
    return res

print(dp(0, 0, 0))

Submission status: Runtime Error

Solution code:
N = [int(i) for i in str(input())]
m = len(N)
K = int(input())
dp = [[[0 for i in range(m + 1)],[0 for i in range(m + 1)]]   for i in range(m)]
#初期条件
dp[0][1][0] = 1
dp[0][0][1] = 1
dp[0][1][1] = N[0] - 1
for i in range(1,m):
    for t in range(0,min(i+2,K+1)):
        if N[i] != 0:
            if t == 0:
                dp[i][1][t] = dp[i-1][1][t]
            else:
                dp[i][0][t] = dp[i-1][0][t-1]
                dp[i][1][t] = dp[i-1][0][t] + dp[i-1][0][t-1] * (N[i]-1) + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
        else :
            if t == 0:
                dp[i][0][t] = dp[i-1][0][t]
                dp[i][1][t] = dp[i-1][1][t] * 1
            else :
                dp[i][0][t] = dp[i-1][0][t] + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
print(dp[-1][0][K]+dp[-1][1][K])

Submission status: Runtime Error

Solution code:
N = [int(i) for i in str(input())]
m = len(N)
K = int(input())
dp = [[[0 for i in range(m + 1)],[0 for i in range(m + 1)]]   for i in range(m)]
#初期条件
dp[0][1][0] = 1
dp[0][0][1] = 1
dp[0][1][1] = N[0] - 1
for i in range(1,m):
    for t in range(0,i+2):
        if N[i] != 0:
            if t == 0:
                dp[i][1][t] = dp[i-1][1][t]
            else:
                dp[i][0][t] = dp[i-1][0][t-1]
                dp[i][1][t] = dp[i-1][0][t] + dp[i-1][0][t-1] * (N[i]-1) + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
        else :
            if t == 0:
                dp[i][0][t] = dp[i-1][0][t]
                dp[i][1][t] = dp[i-1][1][t] * 1
            else :
                dp[i][0][t] = dp[i-1][0][t] + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
print(dp[-1][0][K]+dp[-1][1][K])

Submission status: Runtime Error

Solution code:
#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    dp = [[[0]*(size+1) for j in range(2)] for i in range(size+1)]

    dp[0][0][0] = 1
    for i in range(size):
        for less in range(2):
            for k in range(size):
                for x in range(10 if less else N[i] + 1):
                    #print((i, less, k), x, (i+1, int(less or x < N[i]), k + (1 if x else 0)))
                    dp[i+1][less or x < N[i]][k + (1 if x else 0)] += dp[i][less][k]
        #print(dp[i+1])

    print(dp[-1][0][K] + dp[-1][1][K])

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])
 
def keta2(n):
    if n < 10:
      return 0
    s = str(n)
    cnt = [0] * 101
    for i in range(2, 101):
        cnt[i] = 9 * 9 * (i - 1)
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta1(10 ** (len(s) - 1) - 1) + keta1(int(s[1:]))
    return res
 
def keta3(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(3, 101):
        cnt[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta2(10 ** (len(s) - 1) - 1) + keta2(int(s[1:]))
    return res
 
if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

L = len(N)

if N.count("0") > L - K:
    integer = int(N)
    N = str(integer - integer % 10 - 1)

L = len(N)

if L < K:
    print(0)
    quit()

M = ["0"] * L
count = 0
for i in range(L):
    count += bool(int(N[i]))
    M[i] = N[i]
    if count == K:
        M = "".join(M)
        break

index = 0
ans = 0
while index < L:
    if int(M[index]):
        n = L - index - 1
        k = K - index
        digit = (int(M[index]) - 1)
        ans += comb(n, k, exact=True) * 9 ** k + \
               digit * comb(n, k - 1, exact=True) * 9 ** (k - 1)
    index += 1

print(ans + 1)

Submission status: Runtime Error

Solution code:
from scipy.misc import comb

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

L = len(N)

if N.count("0") > L - K:
    integer = int(N)
    N = str(integer - integer % 10 - 1)

M = ["0"] * L
count = 0

for i in range(L):
    count += bool(int(N[i]))
    M[i] = N[i]
    if count == K:
        M = "".join(M)
        break

index = 0
ans = 0
while index < L:
    if int(M[index]):
        n = L - index - 1
        k = K - index
        digit = (int(M[index]) - 1)
        ans += comb(n, k, exact=True) * 9 ** k + \
               digit * comb(n, k - 1, exact=True) * 9 ** (k - 1)
    index += 1

print(ans + 1)

Submission status: Runtime Error

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

dp0=[[0]*(m+1) for _ in range(m+1)]
dp1=[[0]*(m+1) for _ in range(m+1)]
dp1[0][0]=1
for i in range(1,m+1):
    dp0[i][0]=1
    
for i in range(m):
    for j in range(m):
        if N[i]=='0':
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]
            dp1[i+1][j+1]=dp1[i][j+1]
        else:
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]+dp1[i][j]*(int(N[i])-1)+dp1[i][j+1]
            dp1[i+1][j+1]=dp1[i][j]
print(dp0[-1][K]+dp1[-1][K])

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
sN = str(N)
iN = list(map(int, sN[0:K]))
lN = len(sN)
sum = 0

if K == 1:
  	sum = iN[0] + (lN - 1) * 9
elif K == 2:
  	sum = iN[1] + (iN[0] - 1) * 9 + iN[0] * 9 * (lN - 2) + ((lN - 1) * (lN - 2) / 2) * 9 * 9
elif K == 3:
  	sum = iN[0] * iN[1] * (iN[2] + (lN - 3) * 9) + iN[0] * ((lN - 2) * (lN - 3) / 2) * 9 * 9 + ((lN - 1) * (lN - 2) * (lN - 3) / (3 * 2)) * 9 * 9 * 9

print(int(sum))

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
sN = str(N)
iN = list(map(int, sN[0:K]))
lN = len(sN)
sum = 0

if K == 1:
  	sum = iN[0] + (sN - 1) * 9
elif K == 2:
  	sum = iN[1] + (iN[0] - 1) * 9 + iN[0] * 9 * (lN - 2) + ((lN - 1) * (lN - 2) / 2) * 9 * 9
elif K == 3:
  	sum = iN[0] * iN[1] * (iN[2] + (lN - 3) * 9) + iN[0] * ((lN - 2) * (lN - 3) / 2) * 9 * 9 + ((lN - 1) * (lN - 2) * (lN - 3) / (3 * 2)) * 9 * 9 * 9

print(int(sum))

Submission status: Runtime Error

Solution code:
rom math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

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

    ans = func(N, K)

    print(ans)

def func(N, K):
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    ret += func('9'* l, K)

    # ret += (n - 1) * nCr(l-1, K - 2) * 9 ** (K - 1)
    # ret += nCr(l-1, K - 1) * 9 ** K 

    return ret
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, Flase)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Submission status: Runtime Error

Solution code:
from math import factorial
def comb(n, r):
  if r < 0 or r > n:
    return 0
  else:
    return factorial(n) // (factorial(n - r) * factorial(r))

# 左から i 桁目以降について、0 以外の値を残り K 個使用可能
# smaller: i 桁目までが 一致している時=False, 小さい時=True  
def solve(i, k, smaller):
  if i == n:
    if k == 0:
      return 1
    else:
      return 0
  if k == 0:
    return 1
  if smaller:
    return comb(n - i, k) * 9 ** k
  else:
    if S[i] == "0":
      return solve(i + 1, k, Flase)
    else:
      zero = solve(i + 1, k, True)
      aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
      icchi = solve(i + 1, k - 1, False)
      return zero + aida + icchi

S = input()  
n = len(S)
k = int(input())
print(solve(0, k, False))

Submission status: Runtime Error

Solution code:
from math import factorial
import math

def comb(n, r):
    return factorial(n) / factorial(r) /factorial(n - r)

def solve(i, k, smaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    if smaller:
        return comb(N - i, k) * math.pow(9, k)
    else:
        if S[i] == "0":
            return solve(i + 1, k, False)
        else:
            zero = solve(i + 1, k, True)
            aida = solve(i + 1, k - 1, True) * (int(S[i]) - 1)
            icchi = solve(i + 1, k - 1, False)
            return int(zero + aida + icchi)

S = input()
K = int(input())
N = len(S)

print(solve(0, K, False))

Submission status: Runtime Error

Solution code:
s=input()*2;n=len(s)//2;X=[(0,0)]*4
for j in range(n+1):
 for k in range(3,-1,-1):
  a=int(s[n-j])
  X[k]=(X[k][0]+9*X[k-1][0],X[k][0]+(a-1)*X[k-1][0]+X[k-1][1]if a else X[k][1])if k else 1
print(X[int(input())][1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N, K = map(int,input().split())
 
@lru_cache(None)
def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
#     assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret

 
print(F(N, K))

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
fac = [1, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * pow(fac[r], mod-2, mod) * pow(fac[n-r], mod-2, mod) % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def g(x, y):
    return ((y+2) * modcmb(x+y+2, x, MOD) - (x+1)) * pow(x+1, MOD-2, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = g(r2, c2) - g(r1-1, c2) - g(r2, c1-1) + g(r1-1, c1-1)
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

# 必要なだけforを回す
for i in range(2, 6):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

# nCr n個から重複を許さずr個の組み合わせを選ぶ
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD

def rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

Submission status: Runtime Error

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

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 rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

Submission status: Runtime Error

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

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 rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (S[i] - '1')
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

Submission status: Runtime Error

Solution code:
import math

N=int(input())
K=int(input())
digits = len(str(N))
max_digits_val= int(str(N)[-digits])
max_digits_val_2= int(str(N)[-(digits-1)])
max_digits_val_3 = int(str(N)[-(digits-2)])


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





if K>digits:
    print(0)
elif digits==1:
    print(N)
else:
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        print(answer)
    if K==3:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)- combinations_count(digits-3,K-3)*(9**(K-3))*(9-max_digits_val_3)
        print(answer)

Submission status: Runtime Error

Solution code:
import math

N=int(input())
K=int(input())
digits = len(str(N))
max_digits_val= int(str(N)[-digits])
max_digits_val_2= int(str(N)[-(digits-1)])
max_digits_val_3 = int(str(N)[-(digits-2)])


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




if K>digits:
    print(0)
elif digits=1:
    print(N)    
else:
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        print(answer)
    if K==3:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)- combinations_count(digits-3,K-3)*(9**(K-3))*(9-max_digits_val_3)
        print(answer)

Submission status: Runtime Error

Solution code:
import math

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

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

if K ==1:
    ans = 0
    l = len(str(N))
    ans += 9*(l-1)
    head = int(str(N)[0])
    ans += head
    print(ans)
elif K == 2:
    ans = 0
    l = len(str(N))
    for i in range(1,l-1):
        ans += 9*(9*i)
    
    head = int(str(N)[0])
    ans += (head-1)*(9*(l-1))
    ans += int(str(N)[1]) + (9*(l-2))
    print(ans)
elif K == 3:
    ans = 0
    l = len(str(N))
    for i in range(0,l-3):
        ans += 9*(81*combinations_count(i+2,2))
    
    head = int(str(N)[0])
    ans += (head-1)*(81*combinations_count(l-1,2))
    ans += ( (int(str(N)[1])-1) * 9  * (l-2) )  + int(str(N)[2]) + (9 * (l-3) ) 
    if l > 3 : 
        ans += (81*combinations_count(l-2,2))
    print(ans)

Submission status: Runtime Error

Solution code:
import math

N=int(input())
K=int(input())
digits = len(str(N))
max_digits_val= int(str(N)[-digits])
max_digits_val_2= int(str(N)[-(digits-1)])
max_digits_val_3 = int(str(N)[-(digits-2)])


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


if K>digits:
    print(0)
else:
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        print(answer)
    if K==3:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)- combinations_count(digits-3,K-3)*(9**(K-3))*(9-max_digits_val_3)
        print(answer)

Submission status: Runtime Error

Solution code:
N = input()
n = [ int(x) for x in list(N)]

K = int(input())
nl = len(N)
cnt = 0

if K == 1:
    cnt += n[0]   + (nl-1) * 9
elif K == 2 and nl >= 2:
    if nl == 2:
        cnt += (n[0]-1) * 9 + n[1]
    if nl > 2:
        cnt += (nl-1) * (nl-2) * 9 * 9 // 2
        cnt += (n[0]-1) * 9 * (nl-1)
        for i in range(1,nl+1):
            if n[i] > 0:
                cnt += n[i] + (nl - i -1) * 9
                break
elif K == 3 and  nl >= 3:
    if nl == 3:
        cnt += (n[0]-1) * 9 * 9
        cnt += (n[1]-1) * 9 + n[2]
    elif nl > 3:
        cnt += (nl-1) * (nl-2) * (nl-3) // 6 * 9 * 9 * 9
        cnt += (n[0]-1) * (nl-1) * (nl-2) //2 * 9 * 9
        for i in range(1,nl):
            if n[i] > 0:
                cnt += (nl-i-1) * (nl-i-2) // 2 * 9 * 9
                cnt += (n[i]-1) * (nl-i-1) * 9
                for j in range(i+1,nl):
                    if n[j] > 0:
                        cnt += (nl-j-1) * 9
                        cnt += n[j]
                        break
                break
print (cnt)

Submission status: Runtime Error

Solution code:
N = input()
n = [ int(x) for x in list(N)]

K = int(input())
nl = len(N)
cnt = 0

if K == 1:
    cnt += n[0]   + (nl-1) * 9
elif K == 2 and nl >= 2:
    if nl == 2:
        cnt += (n[0]-1) * 9 + n[1]
    if nl > 2:
        cnt += (nl-1) * (nl-2) * 9 * 9 // 2
        cnt += (n[0]-1) * 9 * (nl-1)
        for i in range(1,nl+1):
            if n[i] > 0:
                cnt += n[i] + (nl - i -1) * 9
                break
elif K == 3 and  nl >= 3:
    if nl == 3:
        cnt += (n[0]-1) * 9 * 9
        cnt += (n[1]-1) * 9 + n[2]
    elif nl > 3:
        cnt += (nl-1) * (nl-2) * (nl-3) // 6 * 9 * 9 * 9
        cnt += (n[0]-1) * (nl-1) * (nl-2) //2 * 9 * 9
        for i in range(1,nl):
            if n[i] > 0:
                cnt += (nl-i-1) * (nl-i-2) // 2 * 9 * 9
                cnt += (n[i]-1) * (nl-i-1) * 9
                for j in range(i+1,nl+1):
                    if n[j] > 0:
                        cnt += (nl-j-1) * 9
                        cnt += n[j]
                        break
                break
print (cnt)

Submission status: Runtime Error

Solution code:
import math
from scipy.special import perm
A=int(input())
B=int(input())
C=len(A)
print(scipy.special.perm(C,C)*(9**B)/(math.factrial(C-B)*math.factrial(B)))

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 1
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:ans+=mi(0)*(a-1)*9+zero(1)*(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(0)*81*(combi(a-1,2))+9*mi(1)+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=a
        c=0
        cs=a
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)):
                break
            i+=1

        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)

Submission status: Runtime Error

Solution code:
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    z = N.count('0')
    o = N.count('1')
    f = 0
    if z + o == L:
      f = 1
    if f == 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(int(N[1:])),K - 1)
    else:
      if len(str(int(N[1:]))) != 1:
        return ans + top(str(int(N[1:])),K - 1)
      else:
        if o >= K:
          return ans + 1
        else:
          return ans

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

print(int(top(N,K)))

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:ans+=(int(n[0])-1)*(a-1)*9+(a-2)*9+int(n[1])
    else:ans+=(int(n[0])-1)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*(int(n[1])-1)+int(n[2])+(a-3)*9

print(ans)

Submission status: Runtime Error

Solution code:
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    if int(N) % u * 10 ** (L-1) != 0 or u != 1:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(N[1:]),K - 1)
    else:
      return ans

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

print(int(top(N,K)))

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:
        ans+=int(n[0])
    elif K==2:ans+=int(n[0])*(a-2)*9+(int(n[0])-1)*9+int(n[1])
    else:ans+=(int(n[0])-1)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*(int(n[1])-1)+int(n[2])+(a-3)*9

print(ans)

Submission status: Runtime Error

Solution code:
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    if int(N) % u * 10 ** (L-1) != 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(N[1:]),K - 1)
    else:
      return ans

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

print(int(top(N,K)))

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
print(a)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
        print(ans)
    if K==1:
        ans+=int(n[0])
    elif K==2:ans+=int(n[0])*(a-2)*9+(int(n[0])-1)*9+int(n[1])
    else:ans+=(int(n[0])-1)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*(int(n[1])-1)+int(n[2])+(a-3)*9

print(ans)

Submission status: Runtime Error

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

L=len(str(N))

import math

def combi(a, b):
    ans1=1
    ans2=1
    for i in range(b):
        ans1=ans1*(a-i)
        ans2=ans2*(b-i)
    ans = ans1/ans2
    ans=int(ans)
    return ans

if K==1:
    ans = (L-1)*9
    N1=int(NS[0])
    ans+=N1
elif K == 2:
    if N<=9:
        print(0)
        exit()
    elif N>=100:
        ans=combi(L-1,2)*(9**2)
    else:
        ans=0
    N1 = int(NS[0])
    ans+=(N1-1)*(L-1)*9
    ans+=(L-2)*9
    N2 = int(NS[1])
    ans+=N2
elif K==3:
    if N<=99:
        print(0)
        exit()
    elif N>=1000:
        ans=combi(L-1,3)*(9**3)
        N1 = int(NS[0])
        ans+=(N1-1)*combi(L-1,2)*(9**2)
        N2=int(NS[1])
        ans+=(N2-1)*(L-2)*9
        ans+=combi(L-2,2)*(9**2)
        N3=int(NS[2])
        ans+=N3
        ans+=(L-3)*9

print(ans)

Submission status: Runtime Error

Solution code:
N = list(map(int,list(input())))
K = int(input())
#print(N)

def main(k,p):
    l = len(k)
    x = 9 ** p###先頭桁が0
    for i in range(p):
        x *= max(l - 1 - i,0)
    for i in range(p):
        x //= (i+1)
    y = (k[0] - 1)*(9**(p-1))###先頭桁が1以上k[0]-1以下
    for i in range(p-1):
        y *= max(l - 1 - i,0)
    for i in range(p-1):
        y //= (i+1)
    ##以下, 先頭がk[0]
    i = 1
    while i < l-1 and k[i] == 0 :
        i += 1
    #print("i=",i)
    if p == 1:
        z = 1
    elif i == l-1 and k[i]==0:
        z = 0
    else:
        z = main(k[i:],p-1)
    #print(k,x,y,z)
    return (x+y)+z

print(main(N,K))

Submission status: Runtime Error

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

L=len(str(N))

import math

def combi(a, b):
    ans = math.factorial(a) / (math.factorial(a - b) * math.factorial(b))
    ans=int(ans)
    return ans

if K==1:
    ans = (L-1)*9
    N1=int(NS[0])
    ans+=N1
elif K == 2:
    if N<=9:
        print(0)
        exit()
    elif N>=100:
        ans=combi(L-1,2)*(9**2)
    else:
        ans=0
    N1 = int(NS[0])
    ans+=(N1-1)*(L-1)*9
    ans+=(L-2)*9
    N2 = int(NS[1])
    ans+=N2
elif K==3:
    if N<=99:
        print(0)
        exit()
    elif N>=1000:
        ans=combi(L-1,3)*(9**3)
        N1 = int(NS[0])
        ans+=(N1-1)*combi(L-1,2)*(9**2)
        N2=int(NS[1])
        ans+=(N2-1)*(L-2)*9
        ans+=combi(L-2,2)*(9**2)
        N3=int(NS[2])
        ans+=N3
        ans+=(L-3)*9

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 再帰

N = input()
K = int(input())
lenN = len(N)


# 組み合わせの数
def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n-k))


# i桁目から
# 残りk個 Non-Zero
# Nよりもsmallerか？
# というときの組み合わせの数
def CntAlmostZero(i, k, smaller):
    # N桁まで取り出した時
    if i == lenN:
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    # Nよりも小さい時
    if smaller:
        return comb(lenN - i, k) * (9 ** k)
    # 前がNと同じ桁の時(初期は0なので必ずこっち)
    else:
        # 見てる桁が0の時
        if N[i] == '0':
            return CntAlmostZero(i + 1, k, False)
        # 見てる桁が0以外の時
        else:
            # 0だったら
            zero = CntAlmostZero(i+1, k, True)
            # 同じだったら
            same = CntAlmostZero(i+1, k-1, False)
            # その間だったら
            aida = CntAlmostZero(i + 1, k - 1, True) * (int(N[i]) - 1)

            return zero + same + aida

    return 1


ans = CntAlmostZero(0, K, False)
print(ans)