Problem:


Score : 500 points

Problem Statement

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

1 \leq N < 10^{100}

1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

19

The following 19 integers satisfy the condition:

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Sample Input 2

25
2

Sample Output 2

14

The following 14 integers satisfy the condition:

11,12,13,14,15,16,17,18,19,21,22,23,24,25

Sample Input 3

314159
2

Sample Output 3

937

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300



Sample input:
100
1


Sample output:
19

Submission status: Runtime Error

Solution code:
N=input()
K=int(input())
#Nは最大で100桁あるので、整数では扱いにくい
#そこでstringで入力する

#桁DPの典型的な問題
#まず、Nの具体的な値は無視して、以下のDPをする
#dp[i][j][k]=[j*10^i,(j+1)*10^i)までに0でない桁がk桁あるような数の個数
#このDPは、以下の遷移で求まる
#dp[i][j][k]=(i=0 j=0 k=0)1
#            (i=0 j=0 k!=0)0
#            (i=0 j!=0 k=1)1
#            (i=0 j!=0 k!=1)0
#            (i!=0 j=0)Σ[j,0~9] dp[i-1][j][k]
#            (i!=0 j!=0)Σ[j,0~9] dp[i-1][j][k-1]

dp = [[[0 for i in range(104)] for j in range(11)] for k in range(5)]
for j in range(10):
    if j==0:
        dp[0][j][0]=1
    else:
        dp[0][j][1]=1

for k in range(K+1):
    for i in range(len(N)):
        if i==0:
            continue
        for j in range(10):
            if j==0:
                for l in range(10):
                    dp[i][j][k]+=dp[i-1][l][k]
            elif (k != 0):
                for l in range(10):
                    dp[i][j][k]+=dp[i-1][l][k-1]


#そうしてDPのボードが完成したら答えを求める
#Nの上からi桁目をDとおき、[0,D)だけdp[i][j][k]を足す
#なお、最後の桁だけは[0,D]
#Dが0のときは以降の桁に0が残り続けるので、kをデクリメントする
#全ての桁を調べるかkが負になったら終了

Ans=0
k=K
for i in range(len(N)):
    D=int(N[i])
    if i==len(N)-1:
        D+=1
    for j in range(D):
        Ans+=dp[len(N)-i-1][j][k]
    if D!=0:
        k-=1
    if k<0:
        break

print(Ans)

Submission status: Runtime Error

Solution code:
import sys
import itertools as it

n = int(input())
k = int(input())
if k == 2 and n < 11:
    print(0)
    sys.exit()
elif k == 3 and n < 111:
    print(0)
    sys.eixt()

nl = list(map(int, list(str(n))))
keta = len(nl)

from operator import mul
from functools import reduce


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


if keta == 1:
    print(n)
    sys.exit()
if keta > k:
    a0 = cmb(keta - 1, k) * 9 ** k
else:
    a0 = 0

nl0 = nl.pop(0)
a1 = 0
if k == 1:
    a1 = nl0
else:
    if k == 2:
        a1 = nl[0] + 9 * (keta - 2)
        a1 += (nl0 - 1) * 9 * (keta - 1)
    elif k == 3:
        for i in it.combinations(nl, 2):
            a1 += i[0] * i[1]
        a1 += (nl0 - 1) * cmb(keta - 1, 2) * 9 ** 2
print(a0 + a1)

Submission status: Runtime Error

Solution code:
import sys
import itertools as it

n = int(input())
k = int(input())
if k == 2 and n < 11:
    print(0)
    sys.exit()
elif k == 3 and n < 111:
    print(0)
    sys.eixt()

nl = list(map(int, list(str(n))))
keta = len(nl)

from operator import mul
from functools import reduce


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


if keta == 1:
    print(n)
    sys.exit()
if keta > k:
    a0 = cmb(keta - 1, k) * 9 ** k
else:
    a0 = 0
#print(a0)

nl0 = nl.pop(0)
a1 = 0
if k == 1:
    a1 = nl0
else:
    if k == 2:
        a1 = sum(nl)
        a1 += (nl0 - 1) * 9 * (keta - 1)
    elif k == 3:
        for i in it.combinations(nl, 2):
            a1 += i[0] * i[1]
        a1 += (nl0 - 1) * cmb(keta - 1, 2) * 9 ** 2
print(a0 + a1)

Submission status: Runtime Error

Solution code:
import sys
import itertools as it

n = int(input())
k = int(input())
if k == 2 and n < 11:
    print(0)
    sys.exit()
elif k == 3 and n < 111:
    print(0)
    sys.eixt()

nl = list(map(int, list(str(n))))
keta = len(nl)

from operator import mul
from functools import reduce


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


if keta == 1:
    print(n)
    sys.exit()
if keta > k:
    a0 = cmb(keta - 1, k) * 9 ** k
else:
    a0 = 0
#print(a0)

nl0 = nl.pop(0)
a1 = 0
if k == 1:
    a1 = nl0
else:
    if k == 2:
        a1 = sum(nl)
        a1 += (nl0 - 1) * 9 * (keta - 1)
    elif k == 3:
        for i in it.combinations(nl, 2):
            a1 += i[0] * i[1]a
        a1 += (nl0 - 1) * cmb(keta - 1, 2) * 9 ** 2
print(a0 + a1)

Submission status: Runtime Error

Solution code:
import sys
import itertools as it

n = int(input())
k = int(input())
if k == 2 and n < 11:
    print(0)
    sys.exit()
elif k == 3 and n < 111:
    print(0)
    sys.eixt()

nl = list(map(int, list(str(n))))
keta = len(nl)

from operator import mul
from functools import reduce


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


if keta == 1:
    print(n)
    sys.exit()
if keta > k:
    a0 = cmb(keta - 1, k) * 9 ** k
else:
    a0 = 0
print(a0)

nl0 = nl.pop(0)
a1 = 0
if k == 1:
    a1 = nl0
else:
    if k == 2:
        a1 = sum(nl)
        a1 += (nl0 - 1) * 9 * (keta - 1)
    elif k == 3:
        for i in it.combinations(nl, 2):
            a1 += i[0] * i[1]a
        a1 += (nl0 - 1) * cmb(keta - 1, 2) * 9 ** 2
print(a0 + a1)

Submission status: Runtime Error

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
def permutations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // factorial(n - r)
def combinations_count(n, r):
    if not n>=r>=0 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())
if length<K:
    print(0)
    exit()
length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3 >=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1 >=0:count+=combinations_count(length-1-count3,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
            count3+=1
    if K-count3==0:
        count+=1
        #count+=int(N[i])
        break
    if i==length-1:
        count+=int(N[i])
print(count)

Submission status: Runtime Error

Solution code:
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
 z=0
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

Submission status: Runtime Error

Solution code:
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
z=0
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

Submission status: Runtime Error

Solution code:
def f(s,t,k):
 n=len(s)
 a=max(t,int(s[0]))
 if k>n:z=0
 elif a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  z=0
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

Submission status: Runtime Error

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

digit = len(N)
dp = [[[0]*(digit+1) for _ in range(2)] for _ in range(digit)]

cd = int(N[0])
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = cd-1

for i in range(1, digit):
    for k in range(i+2):
        cd = int(N[i])
        if k == 0:
            dp[i][1][0] = 1
        else:
            dp[i][0][k] = dp[i-1][0][k-1]
            dp[i][1][k] = dp[i-1][0][k-1]*(cd-1)+dp[i-1][0][k]\
                          +dp[i-1][1][k]+dp[i-1][1][k-1]*9


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

Submission status: Runtime Error

Solution code:
import math

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

def count1(nrow, k):
  keta = len(nrow)
  topmax = int(nrow[0])

  if keta == 1:
    return topmax
  ans = topmax
  ans += (keta-1)*9
  return ans

def count2(nrow, k):
  keta = len(nrow)
  topmax = int(nrow[0])

  ans = count1(nrow[1:], k)  # top==topmax
  ans += (topmax-1)*(keta-1)*9  # top!=topmax
  if keta > 2:
    ans += comb(keta-1, 2)*81
  return ans

def count3(nrow, k):
  keta = len(nrow)
  topmax = int(nrow[0])

  ans = count2(nrow[1:],k) #top==topmax
  ans += (topmax-1)*comb(keta-1,2) * 81#top!=topmax
  if keta > 3:
    ans += comb(keta-1 , 3) * 729
  return ans

nrow=input()
k = int(input())

if k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))

Submission status: Runtime Error

Solution code:
def K1(n):
    ans = 0
    d = len(str(n))
    ans += int(str(n)[0])
    ans += 9 * (d-1)
    return ans


def K2(n):
    d = len(str(n))
    ans = 9**2*(d-2)*(d-1)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K1(int(str(n)[1:]))
    return ans


def K3(n):
    d = len(str(n))
    ans = 0
    for i in range(2,d-1):
        ans += i*(i-1)//2
    ans *= 9**3
    ans += (int(str(n)[0]) - 1) * 9**2 * (d-1)*(d-2) // 2
    ans += K2(int(str(n)[1:]))
    return ans


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

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

    if K == 2:
        print(K2(N))

    if K == 3:
        print(K3(N))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

L = list(map(int, list(str(N))))

M = len(L)
if M < K:
  x = 1 / 0
DP = [[[0] * 2 for _ in range(K + 1)] for _ in range(M)]

DP[0][1] = [L[0] - 1, 1]
DP[0][0][0] = 1

for i in range(1, M):
  DP[i][0][0] = DP[i - 1][0][0]
  for j in range(1, K + 1):
    DP[i][j][0] = DP[i - 1][j][0]
    DP[i][j][0] += DP[i - 1][j - 1][0] * 9
    DP[i][j][0] += DP[i - 1][j - 1][1] * (L[i] - 1)
    DP[i][j][0] += DP[i - 1][j][1] 
    DP[i][j][1] = DP[i - 1][j - 1][1]

ans = DP[-1][-1][0] + DP[-1][-1][1]
ans = max(0, ans)
print(ans)

Submission status: Runtime Error

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

L = list(map(int, list(str(N))))

M = len(L)
if L < M:
  x = 1 / 0
DP = [[[0] * 2 for _ in range(K + 1)] for _ in range(M)]

DP[0][1] = [L[0] - 1, 1]
DP[0][0][0] = 1

for i in range(1, M):
  DP[i][0][0] = DP[i - 1][0][0]
  for j in range(1, K + 1):
    DP[i][j][0] = DP[i - 1][j][0]
    DP[i][j][0] += DP[i - 1][j - 1][0] * 9
    DP[i][j][0] += DP[i - 1][j - 1][1] * (L[i] - 1)
    DP[i][j][0] += DP[i - 1][j][1] 
    DP[i][j][1] = DP[i - 1][j - 1][1]

ans = DP[-1][-1][0] + DP[-1][-1][1]
ans = max(0, ans)
print(ans)

Submission status: Runtime Error

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

L = list(map(int, list(str(N))))
if L < K:
  x = 1 / 0
M = len(L)
DP = [[[0] * 2 for _ in range(K + 1)] for _ in range(M)]

DP[0][1] = [L[0] - 1, 1]
DP[0][0][0] = 1

for i in range(1, M):
  DP[i][0][0] = DP[i - 1][0][0]
  for j in range(1, K + 1):
    DP[i][j][0] = DP[i - 1][j][0]
    DP[i][j][0] += DP[i - 1][j - 1][0] * 9
    DP[i][j][0] += DP[i - 1][j - 1][1] * (L[i] - 1)
    DP[i][j][0] += DP[i - 1][j][1] 
    DP[i][j][1] = DP[i - 1][j - 1][1]

ans = DP[-1][-1][0] + DP[-1][-1][1]
ans = max(0, ans)
print(ans)

Submission status: Runtime Error

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

L = list(map(int, list(str(N))))
if L < N:
  x = 1 / 0
M = len(L)
DP = [[[0] * 2 for _ in range(K + 1)] for _ in range(M)]

DP[0][1] = [L[0] - 1, 1]
DP[0][0][0] = 1

for i in range(1, M):
  DP[i][0][0] = DP[i - 1][0][0]
  for j in range(1, K + 1):
    DP[i][j][0] = DP[i - 1][j][0]
    DP[i][j][0] += DP[i - 1][j - 1][0] * 9
    DP[i][j][0] += DP[i - 1][j - 1][1] * (L[i] - 1)
    DP[i][j][0] += DP[i - 1][j][1] 
    DP[i][j][1] = DP[i - 1][j - 1][1]

ans = DP[-1][-1][0] + DP[-1][-1][1]
ans = max(0, ans)
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 saiki2(N, K, vlen, p):
    a = 0
    if (K == 0):
        ans =  1
    
    elif(N[p] == '0'):
        ans=  saiki2(N, K, vlen, p+1)

    else:
        if(vlen == 1):
            ans = int(N[p])
        else:
            a = saiki2(N, K-1, vlen, p+1)

            b = (int(N[p])-1) * 9**(K-1) * combinations_count(vlen-p-1, K-1)
            if(vlen-p-1 <  K):
                c = 0
            else:
                c =  9**(K) * combinations_count(vlen-p-1, K)
            ans = a+b+c

    return ans

N = input()
Nn = int(N)
K = int(input())
vlen = len(N)

ans = saiki2(N,K,vlen,0)

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

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

vlen = len(N)


#再帰関数
#Nnの頭からp桁目を見る
#
# print('K',K)
# print('N',N[0])
# print('vlen',vlen)



def saiki2(N, K, vlen, p):
    # print('**', p, K, '**')
    a = 0
    if (K == 0):
        #一つ上の桁で最後のKを使い果たした場合、
        ans =  1
    
    # 再帰が下にもぐるときは、桁の上位がNと同じで、下位の桁を見ないと大きいか分らない状態のときだけ

    elif(N[p] == '0'):
        ans=  saiki2(N, K, vlen, p+1)

    else:
        if(vlen == 1):
            ans = int(N[p])
        else:
            a = saiki2(N, K-1, vlen, p+1)
            # print('a',a)

            # print('K',vlen-p-1,K)
            b = (int(N[p])-1) * 9**(K-1) * combinations_count(vlen-p-1, K-1)
            if(vlen-p-1 <  K):
                c = 0
            else:
                c =  9**(K) * combinations_count(vlen-p-1, K)
            # print('b',b)
            # print('c',c)
            ans = a+b+c
            # print('toku', ans)

    # print('ret**', p, K, '**')
    return ans
ans = saiki2(N,K,vlen,0)


print(ans)
# 最大の項以外で成立する場合の数
# c =   combinations_count(vlen-1,K)

# anasi = c * 9 * (vlen-1)

# c2 =   combinations_count(vlen-1,K-1)

# aari = c2 * 9 * (int(N[0])-1)



# print(c)
# print(c * )

Submission status: Runtime Error

Solution code:
from math import factorial

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


def ncr(n, r):
    if n <= 0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)


def k1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])


def k2(n):
    if n < 10:
        return 0
    s = str(n)
    res = ncr(len(s)-1, 2) * 9 * 9
    res += (int(s[0]) - 1) * k1(10 ** (len(s) - 1) - 1) + k1(int(s[1:]))
    return res


def k3(n):
    s = str(n)
    res = ncr(len(s)-1, 3)*9*9*9
    res += (int(s[0]) - 1) * k2(10 ** (len(s) - 1) - 1) + k2(int(s[1:]))
    return res


kf = [k1, k2, k3]
print(kf[K-1](N))

Submission status: Runtime Error

Solution code:
from math import factorial

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


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


def k1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])


def k2(n):
    if n < 10:
        return 0
    s = str(n)
    res = ncr(len(s)-1, 2) * 9 * 9
    res += (int(s[0]) - 1) * k1(10 ** (len(s) - 1) - 1) + k1(int(s[1:]))
    return res


def k3(n):
    s = str(n)
    res = ncr(len(s)-1, 3)*9*9*9
    res += (int(s[0]) - 1) * k2(10 ** (len(s) - 1) - 1) + k2(int(s[1:]))
    return res


kf = [k1, k2, k3]
print(kf[K-1](N))

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
L = len(str(N))

def solve(num_str, k, smaller):
    if k == 0 or num_str == None:
        return 1

    elif smaller:
        keta = len(num_str)
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
L = len(str(N))

def solve(num_str, k, smaller):

    keta = len(num_str)
    if k == 0:
        return 1
    elif smaller:
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
L = len(str(N))

suu = []
for i in range(L):
    suu.append(int(str(N)[i]))

DP_1 =[[0 for k in range(L+1)] for i in range(L+2)]
DP_2 =[[0 for k in range(L+1)] for i in range(L+2)]
DP_2[0][0] = 1
for i in range(L):
    for k in range(L+1):
        DP_1[i+1][k] = DP_1[i][k] + DP_1[i][k-1] * 9 
        if suu[i]:
            DP_1[i+1][k] += DP_2[i][k] + DP_2[i][k-1] * max(suu[i] - 1, 0)
            DP_2[i+1][k] = DP_2[i][k-1]
        else:
            DP_2[i+1][k] = DP_2[i][k]
print(DP_1[L][K]+ DP_2[L][K])

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
L = len(str(N))

suu = []
for i in range(L):
    suu.append(int(str(N)[i]))

DP_1 =[[0 for k in range(L+1)] for i in range(L+1)]
DP_2 =[[0 for k in range(L+1)] for i in range(L+1)]
DP_2[0][0] = 1
for i in range(L):
    for k in range(L+1):
        DP_1[i+1][k] = DP_1[i][k] + DP_1[i][k-1] * 9 
        if suu[i]:
            DP_1[i+1][k] += DP_2[i][k] + DP_2[i][k-1] * max(suu[i] - 1, 0)
            DP_2[i+1][k] = DP_2[i][k-1]
        else:
            DP_2[i+1][k] = DP_2[i][k]
print(DP_1[L][K]+ DP_2[L][K])

Submission status: Runtime Error

Solution code:
def nCk(n, k):
    if n < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n * (n - 1) // 2
    else:
        return n * (n - 1) * (n - 2) // 6


def solve(N, K):
    if K == 0:
        return 1

    M = len(N)
    res = solve(N[1:], K - 1)
    res += (int(N[0]) - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))
    res += nCk(M - 1, K) * (9 ** K)

    return res


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

print(solve(N, K))

Submission status: Runtime Error

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

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])

def keta2(n):
    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:

def solve(n,k):
    if k == 0:
        return 1
    for i in range(len(n)):
        if n[i] != 0:
            break
    n = n[i:]
    if n == []:
        return 0
    l = len(n)
    ans = 0

    # n-1桁からKこ取る
    tmp1 = 1
    for i in range(1, k+1):
        tmp1 = tmp1*9*(l-i)
    for i in range(1, k+1):
        tmp1 = tmp1 // i

    # 最上位から1つ（最上位の数以外）とる。
    tmp2 = n[0]-1
    for i in range(1, k):
        tmp2 = tmp2*9*(l-i)
    for i in range(1, k):
        tmp2 = tmp2 // i

    # 最上位からその数をとる。
    tmp3 = solve(n[1:],k-1)

    ans = tmp1 + tmp2 + tmp3
    return ans

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

print(solve(n,k))

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

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

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


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

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

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

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

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

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

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

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

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

  print(ans1+ans2+ans3)
  exit()

Submission status: Runtime Error

Solution code:
import itertools

def read():
    N = str(input().strip())
    K = int(input().strip())
    return N, K

def nCk(n, k):
    return len(list(itertools.combinations(range(n), k)))

def count_nonzero(L, H, K):
    """
    [0-H][0-9]{L-1}にマッチするL桁の数字から、非ゼロがK個のものを数え上げ
    L: 桁数
    H: 上位1桁目の数字
    K: 範囲内に含まれるゼロでない数字の数
    """
    count = 0
    factor = [1, 9, 81, 729]
    count += nCk(L-1, K) * factor[K]
    for h in range(1, H+1):
        count += nCk(L-1, K-1) * factor[K-1]
    return count



def solve(N, K):
    L = len(N)
    intN = [int(N[i]) for i in range(L)]
    count = 0
    # 最上位桁が[0-(intN[0]-1)]のものをカウント
    if K >= 1:
        count += count_nonzero(L, intN[0]-1, K)
    # 最上位桁がintN[0]、2桁目が[0-(intN[1]-1)]のものをカウント
    if K >= 2:
        count += count_nonzero(L-1, intN[1]-1, K-1)
    # 上位桁がintN[0]intN[1]、3桁目が[0-(intN[2]-1)]のものをカウント
    if K >= 3:
        count += count_nonzero(L-2, intN[2]-1, K-2)
    # 上位桁がintN[0]intN[1]intN[2]のものをカウント (自分自身)
    count += 1
    return count


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Runtime Error

Solution code:
import math
from scipy.misc import comb

N = input()
l = len(N)

number = int(input())
mam = comb(l, number, exact=True)*9**number
if number == 1:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += int(N[0])
  print(mam1)
if number == 2:
  mam1 = comb(l-1, number, exact=True)*9**number#先頭が0
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)#先頭が1--8
  mam1 += int(N[1])+ (l-2)*9   #先頭が9で次が0
  print(mam1)
if number == 3:
  mam1 = comb(l-1, number, exact=True)*9**number#先頭が0
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*(9**(number-1))#先頭が1--8
  mam1 += comb(l-2, number-1, exact=True)*9**(number-1) #先頭が9で次が0
  mam1 += (int(N[1])-1)*comb(l-2, number-2, exact=True)*9**(number-2) #先頭が9で次が1~8
  mam1 += int(N[2])+ (l-3)*9
  print(mam1)

Submission status: Runtime Error

Solution code:
import math
from scipy.misc import comb

N = input()
l = len(N)

number = int(input())
mam = comb(l, number, exact=True)*9**number
if number == 1:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += int(N[0])
  print(mam1)
if number == 2:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)
  mam1 += int(N[1])+ (l-2)*9   
  print(mam1)
if number == 3:
  mam1 = comb(l-1, number, exact=True)*9**number#先頭が0
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*(9**(number-1))#先頭が1--8
  mam1 += comb(l-2, number-1, exact=True)*9**(number-1) #先頭が9で次が0
  mam1 += (int(N[1])-1)*comb(l-2, number-2, exact=True)*9**(number-2) #先頭が9で次が1~8
  mam1 += comb(l-3, number-2, exact=True)*9**(number-2)#先頭が9で次が9で次が0
  mam1 += int(N[2]) #先頭が9で次が9で次が1~9
  print(mam1)

Submission status: Runtime Error

Solution code:
def nC2(n):
    return n*(n-1)/2

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

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

    N=0

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

    #return N
    return 0


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

    N=0

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

    #return N
    return 0

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

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

N=input()
K=input()

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


print(int(ans))

Submission status: Runtime Error

Solution code:
def nC2(n):
    return n*(n-1)/2

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

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

    N=0

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

    return N


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

    N=0

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

    return N


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

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

N=input()
K=input()

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


print(int(ans))

Submission status: Runtime Error

Solution code:
def nC2(n):
    return n*(n-1)/2

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

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

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

    return N


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

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

    return N


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

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

N=input()
K=input()

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


print(int(ans))

Submission status: Runtime Error

Solution code:
import math
from scipy.misc import comb

N = input()
l = len(N)

number = int(input())
mam = comb(l, number, exact=True)*9**number
if number == 1:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += int(N[0])
  print(mam1)
if number == 2:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)
  mam1 += int(N[1])+ (l-2)*9   
  print(mam1)
if number == 3:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*(9**(number-1))
  mam1 += (int(N[1])-1)*comb(l-2, number-2, exact=True)*9**(number-2) + comb(l-2, number-1, exact=True)*9**(number-1)
  mam1 += int(N[2])+ (l-3)*9
  print(mam1)

Submission status: Runtime Error

Solution code:
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
else:

    def main(d, k):
        if N[d] == "0":
            return main(d + 1, k)
        if (L - d) < k:
            return 0
        if k == 1:
            return ((L - d) - 1) * 9 + int(N[d])
        elif k == 2:
            return (
                ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81
                + ((L - d) - 1) * 9 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )
        elif k == 3:
            return (
                ((((L - d) - 1) * ((L - d) - 2) * ((L - d) - 3)) // 6) * (9 ** 3)
                + ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )

    print(main(0, K))

Submission status: Runtime Error

Solution code:

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

keta1=len(str(N))
maxN=int(str(N)[0])
keta2=len(str(int(str(N)[1:])))
secN=int(str(int(str(N)[1:]))[0])
if keta2>1:
    keta3=len(str(int(str(int(str(N)[1:]))[1:])))
    thiN=int(str(int(str(int(str(N)[1:]))[1:]))[0])
only1=0
only2=0
if secN==0:
    only1=1
if str(int(str(int(str(N)[1:]))[0]))[0]==0:
    only2=1
import math

if keta1<K:
    print(0)
else:
    if K==1:
        print(maxN+9*(keta1-1))
    if K==2:
        if keta1-2!=0:
            if only1:
                print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2)
            else:
                if keta2-1!=0:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN+(keta2-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN)
        else:
            print((maxN-1)*(keta1-1)*9+secN)
    if K==3:
        if keta1-3!=0:
            if only1:
                print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6)
            else:
                if keta2-2!=0:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN+(keta3-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN)
        else:
            if only1:
                print((maxN-1)*(keta1-1)*9)
            else:
                print((maxN-1)*(keta1-1)*9+(secN-1)*9+thiN)

Submission status: Runtime Error

Solution code:
def nC2(n):
    return n*(n-1)/2

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

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

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


    return N


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

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

    return N


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

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

N=input()
K=input()

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


print(int(ans))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
n2 = str(n)
def permutations_count(n, r):
  return math.factorial(n) // math.factorial(n - r)//math.factorial(r)
k = int(input())
x = 0
for i in range(k,len(n2)+1):
  if i != len(n2):
    x += 9 * 9**(k-1) * permutations_count(i-1,k-1)
  else:
    if k == 1:
      x += int(n2[0])
    elif k == 2:
      x += 1 * (int(n2[1])+9*(i-2)) + (int(n2[0])-1) * 9 * (i-1)
    elif k == 3:
      x += 1*1*(int(n2[2])+9*(i-3))+1*((int(n2[1])-1)*9*(i-2)+1*9*9*permutations_count(i-2,2))+(int(n2[0])-1)*9*9*permutations_count(i-1,2)
print(x)