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: Wrong Answer

Solution code:
strN = input()
N = int(strN)
K = int(input())
ans = 0
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    lenN = len(strN)
    if lenN >= 2:
        ans += int(strN[1])
        ans += (int(strN[0]) - 1) * 9
        ans += int(strN[0]) * 9 * (lenN - 2)
        for j in range(1, lenN - 1):
            ans += 9 * 9 * (lenN - j - 1)

        # if lenN >= 3:
        #    ans += (lenN - 2) * 9
        #now_pattern = int(strN[0])
        # for j in range(1, lenN):
        #    ans += now_pattern * (9 ** (lenN - j - 1))
        #    now_pattern *= int(strN[j])

else:
    lenN = len(strN)
    if lenN >= 3:
        ans += int(strN[2])+(lenN-3)*9
        if int(strN[1]) != 0:
            ans += (int(strN[1]) - 1) * 9 * (lenN - 2)
        ans += 9 * 9 * (((lenN - 2) * (lenN - 3)) // 2)
        ans += (int(strN[0]) - 1) * 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)
        ans += 9*9*9*(((lenN-1)*(lenN-2)*(lenN-3))//6)
        # for h in range(1, lenN - 2):
        #    ans += 9 * 9 * 9*(((lenN-1-h)*(lenN-2-h))//2)
print(ans)

Submission status: Wrong Answer

Solution code:

def countPermutations(N, B):  
    count = 0
    for i in  range(N):
        res = list(map(int, str(i))) 
        if B in set(res):
            count = count + 1
    return count
            
    
  
# Driver code  
if __name__ == "__main__": 
    N = int(input())
    B = int(input())
    print(countPermutations(N, B) )

Submission status: Wrong Answer

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

n = ii()
k = ii()
n2 = n

n_keta = 1
while n2:
    n2 = n2 //10
    if n2 == 0:
        break
    n_keta += 1

from math import factorial as fc
def func(keta,kazu,ima):
    ans = 0
    n = n_keta - keta -1
    r =  k - kazu
    if n-r <0:
        return 0
    ans += (ima-1) *fc(n) //fc (r)//fc(n-r)  * (9 **(k-kazu))
    print(ans)
    if n - r -1 >= 0: ans += fc(n) // fc (r+1) // fc(n-r-1) *(9**(k-kazu +1))
    print(ans)
    return ans
n_in = str(n)
kk = 0
lis = []

for i in range(n_keta):
    if n_in[i] != 0:
        lis.append([i,kk+1,int(n_in[i])]) 
        kk += 1
    if kk ==k:
        break
anss = 0
for lil in lis:
    anss += func(lil[0],lil[1],lil[2])
print(int(anss+1))

Submission status: Wrong Answer

Solution code:
def cmb(a,b):
    if b == 0:
        ans=1
    elif a<b:
        ans = 0
    else:
        Nu = 1
        Di = 1
        for i in range(b):
            Nu = Nu*(a-i)
            Di = Di*(b-i)
        ans = Nu/Di
    return ans


def f(a,keta,K):
    ans = cmb(keta,K)*9**K
    if K == 1:
        ans += a
    else:
        ans += cmb(keta, K-1)*9**(K-1)*(a-1)
    return ans



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

    ans = 0
    while K>0 and N>0:
        keta = len(str(N))-1
        a = int(N/(10**(keta)))
        if keta + 1 < K: break
        if keta == 0:
            if K==1 :ans += N
        ans += f(a,keta,K)
        N -= a*10**keta
        K -= 1
        print(a,keta,ans)
    print(int(ans))
    return

if __name__=="__main__":
    main()

Submission status: Wrong Answer

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

l = len(str(N))
a = N // 10**(l - 1)

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

            rem = N - c * 10**(l - 3)
            l_rem = len(str(rem))
            if l_rem != 0:
                aa = rem // 10**(l_rem - 1)
                ans += 9 * (l_rem - 1) + aa
        else:
            rem = N - c * 10**(l - 3)
            l_rem = len(str(rem))
            if l_rem >= 2:
                aa = rem // 10**(l_rem - 1)
                bb = rem // 10**(l_rem - 2)
                dd = bb - 10 * aa
                ans += 81 * (l_rem - 1) * (l_rem - 2) // 2
                ans += (aa - 1) * 9 * (l_rem - 1) + 9 * (l_rem - 2) + dd
        print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k = get_all_int()

# m桁の数値でf(n)=kとなる数の個数
# dp[k][m]
dp = [ [None]*101 for _ in range(4)]

for i in range(101):
    dp[0][i] = 1
dp[0][0] = 0
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0
dp[1][1] = 9
dp[2][1] = 0
dp[3][1] = 0

dp[1][2] = 1 * dp[1][1] + 9 * dp[0][1]
for i in range(2,101):
    dp[1][i] = 1 * dp[1][i-1] + 9 * dp[0][i-1]
    dp[2][i] = 1 * dp[2][i-1] + 9 * dp[1][i-1]
    dp[3][i] = 1 * dp[3][i-1] + 9 * dp[2][i-1]

# log(dp[1])
# log(dp[2])

ans = 0

keta = 0
x = n
while x > 0:
    keta += 1
    x //= 10

def sol(n, keta, k):
    if k == 0:
        return 1
    if k < 0:
        return 0
    if keta < k:
        return 0
    if keta == 0:
        return 1
    
    top = n//10**(keta-1)%10
    if keta==1:
        return top
    ans = 0
    # 0のとき
    if top == 0:
        ans += sol(n, keta-1, k)
    else:
        ans += 1 * (0 if keta==1 else dp[k][keta-1])
    # ans += sol(n, keta-1, k)
    log(keta,top,k,ans)

    # 1～top-1のとき
    if top != 0:
        if top == 1:
            ans += sol(n, keta-1, k-1)
        else:
            ans += (top-1) * (1 if keta==1 else dp[k-1][keta-1])
        # ans += (top-1) * sol(n, keta-1, k-1)
        log(keta,top,k,ans)

    # topのとき
    if top != 0:
        ans += sol(n, keta-1, k-1)
        log(keta,top,k,ans)
    return ans

if keta < k:
    print(0)
    exit()
ans += sol(n, keta, k)

print(ans)

Submission status: Wrong Answer

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

l = [[0,0,0]]
p1 = 0
p2 = 0
p3 = 0

for i in range(1, 1000):
    m = len(str(i)) - str(i).count("0")
    if m == 3:
        p3 += 1
    elif m == 2:
        p2 += 1
    else:
        p1 += 1
    l.append([p1,p2,p3])
if n <= 999:
    ans = l[n][k-1]

else:
    l2 = [l[9], l[99], l[999]]
    sn = str(n)
    keta = len(sn)
    a = int(sn[0])
    a2 = int(sn[1])
    a3 = int(sn[2])
    for i in range(keta - 4):
        p1 = l2[-1][0] + 9
        p2 = l2[-1][1] + 9 * l2[-1][0]
        p3 = l2[-1][2] + 9 * l2[-1][1]
        l2.append([p1,p2,p3])
    if k == 1:
        ans = l2[-1][0] + a
    elif k == 2:
        ans = l2[-1][1] + (a - 1)* l2[-1][0] + l2[-2][0] + a2
    else:
        ans = l2[-1][2] + (a - 1)* l2[-1][1] + l2[-2][1] + (a2 - 1)* l2[-2][0] + l2[-3][0] + a3

print(ans)

Submission status: Wrong Answer

Solution code:
strN = input()
N = int(strN)
K = int(input())
ans = 0
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    lenN = len(strN)
    if N > 10:
        ans += int(strN[1])
        ans += (int(strN[0]) - 1) * 9
        ans += int(strN[0]) * 9 * (lenN - 2)
        for j in range(1, lenN - 1):
            ans += 9 * 9 * (lenN - j - 1)

        # if lenN >= 3:
        #    ans += (lenN - 2) * 9
        #now_pattern = int(strN[0])
        # for j in range(1, lenN):
        #    ans += now_pattern * (9 ** (lenN - j - 1))
        #    now_pattern *= int(strN[j])

else:
    lenN = len(strN)
    if N > 110:
        ans += int(strN[2])+(lenN-3)*9
        if int(strN[1]) != 0:
            ans += (int(strN[1]) - 1) * 9 * (lenN - 2)
        ans += 9 * 9 * (((lenN - 2) * (lenN - 3)) // 2)
        ans += (int(strN[0]) - 1) * 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)
        ans += 9*9*9*(((lenN-1)*(lenN-2)*(lenN-3))//6)
        # for h in range(1, lenN - 2):
        #    ans += 9 * 9 * 9*(((lenN-1-h)*(lenN-2-h))//2)
print(ans)

Submission status: Wrong Answer

Solution code:
def factorial(n):
    a = 1
    for i in range(1, n + 1):
        a *= i
    return a

def nCr(n,r):
    if r > n:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def normal(d, k):
    #print("normal d,k ", d, k)
    return nCr(d, k) * (9**k)

def main():
    tmp = input()
    N = [int(c) for c in tmp]
    D = len(N)
    K = int(input())
    #print(D, K)

    x = 0
    ans1, ans2, ans3, ans4, ans5, ans6 = 0, 0, 0, 0, 0, 0
    if K == 1:
        ans1 = normal(D-1, K)
        ans2 = N[0]
    elif K == 2:
        ans1 = normal(D-1, K)
        ans2 = (N[0] - 1) * normal(D-1, K-1)
        x = 1
        found = False
        for i in range(x, D):
            if N[i] != 0:
                x = i
                found = True
                break
        if found:
            if x == D - 1:
                ans4 = N[x]
            else:
                ans3 = normal(D-(x+1), K-1)
                ans4 = N[x]
    elif K == 3:
        ans1 = normal(D-1, K)
        ans2 = (N[0] - 1) * normal(D-1, K-1)
        x = 1
        found = False
        for i in range(x, D):
            if N[i] != 0:
                x = i
                found = True
                break
        if found:
            if x == D - 1:
                pass
            else:
                ans3 = normal(D-(x+1), K-1)
                ans4 = (N[x] - 1) * normal(D-(x+1), K-2)
                found = False
                for i in range(x, D):
                    if N[i] != 0:
                        x = i
                        found = True
                        break
                if found:
                    if x == D - 1:
                        ans6 = N[x]
                    else:
                        ans5 = normal(D-(x+1), K-2)
                        ans6 = N[x]

    #print("ans1", ans1)
    #print("ans2", ans2)
    #print("ans3", ans3)
    #print("ans4", ans4)
    #print("ans5", ans5)
    #print("ans6", ans6)

    ans = ans1+ans2+ans3+ans4+ans5+ans6
    #print("ans", ans)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8

from math import factorial as fact
# import copy

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

digit = len(str(N))

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

ans = 0
while K > 0:
    for i in range(K, digit):  # i: 桁数
        ans += (fact(i-1) * (9**K)) // (fact(i-K) * fact(K-1))

    # print(ans)

    # 桁数がdigitのときのみ限界が存在
    str_n = str(N)

    # 最大の桁の数がhead-1までは同様
    ans += ((int(str_n[0])-1) * fact(digit-1) * (9**(K-1))) // (fact(digit-K) * fact(K-1))

    # print(ans)

    # def rec(i, extract, num, head, digit):
    #     global ans

    #     if len(extract) == num:
    #         tmp = 1
    #         for ext in extract:
    #             tmp *= ext
    #         ans += tmp
    #     elif i >= digit:
    #         pass
    #     else:
    #         new_extract = copy.copy(extract)
    #         new_extract.append(int(str_n[i]))
    #         rec(i+1, new_extract, num, head, digit)  # use
    #         rec(i+1, extract, num, head, digit)  # not use

    # rec(1, [], K-1, int(str_n[0]), digit)
    # print(str_n)
    if len(str_n) == 1:
        break
    N = int(str_n[1:])
    K -= 1
    digit -= 1

print(ans+1)

Submission status: Wrong Answer

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

ans=0

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

def k2(n):
    str2_n = str(n)
    keta2 = len(str2_n)
    cnt = 81 * (keta2 - 1) * (keta2 - 2) // 2
    cnt += (int(str2_n[0]) - 1) * k1(10 ** (keta2 - 1) - 1)
    cnt += k1(n-(int(str2_n[0])*10**(keta2-1)))
    return cnt


def k3(n):
    str3_n = str(n)
    keta3 = len(str3_n)
    cnt = 729 * (keta3 - 2) * (keta3 - 3) // 2
    cnt += (int(str3_n[0]) - 1) * k2(10 ** (keta3 - 1) - 1)
    cnt += k2(n-(int(str3_n[0])*10**(keta3-1)))
    return cnt

if k == 1:
    ans = k1(n)

if k == 2:
    ans = k2(n)

if k == 3:
    ans = k3(n)

print(ans)

Submission status: Wrong Answer

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

suu = []
for i in range(keta):
    suu += [int(str(N)[i])]

ans = 0
if K == 1:
    for i in range(len(str(N))):
        if i > 0:
            ans += 9
        else :
            ans += int(str(N)[i])
    print(ans)
elif K == 2:
    if keta -1 >= 2:
        ans += (keta-1)*(keta-2)//2 * 9*9
    if keta >= 2:
        ans += (int(str(N)[0])-1) * (keta-1) * 9
        ans += sum(suu[1:])
    print(ans)

Submission status: Wrong Answer

Solution code:
N  = int(input())
K = int(input())
K = str(K)
count = 0
for i in range(N):
    j = str(i)
    if K in j:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def binomial_coefficient(n, r, mod=10**9+7):
    """
    二項係数nCr, (n,r)をmodで除したあまりを返す
    """
    res = 1
    div = 1
    r = min(r, n - r)
    for i in range(r):
        res *= (n - i) % mod
        div *= (i + 1) % mod
    res *= pow(div, mod - 2, mod)
    return res % mod


def calc(N, K):
    if K == 0:
        return 1
    if K > len(N):
        return 0

    res = 0
    # 一番上が0の時

    if len(N)-1 > K:
        res += binomial_coefficient(len(N) - 1, K) * (9 ** K)

    # 一番上が1~N[0]-1の時
    res += (int(N[0]) - 1) * (9**(K-1)) * binomial_coefficient(len(N)-1, K-1)

    # 一番上がN[0]のとき
    res += calc(N[1:], K-1)

    return res


if __name__ == "__main__":
    N = int(input())
    K = int(input())
    d = len(str(N))
    N = str(N)
    ans = calc(N, K)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

input = sys.stdin.readline
n = int(input())
k = int(input())
t = n
m = 0
while t:
    m += 1
    t //= 10

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

ans = 9 ** k * comb(m-1, k)
tk = k

def dfs(i, mt, kt):
    a = i // 10 ** mt
    b = n // 10 ** mt
    if kt < 0:
        return 0
    if mt < kt:
        return 0
    if a < b:
        if mt > 0:
            return 9 ** kt * comb(mt, kt)
        else:
            return 1
    elif a > b:
        return 0
    if i == n:
        return 1
    elif i > n:
        return 0
    ret = 0
    for j in range(10):
        f = 0
        if j:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

t_ans = 0
for i in range(1, n // (10 ** (m-1) )+1):
    ti = i * 10 ** (m-1)
    t_ans += dfs(ti, m-1, k-1)

print(ans+t_ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lenn=len(str(n))

k=int(input())
#k:1~3

result=0

if n <=9:
    if k==1:
        print(n)
    else:
        print(0)
    exit()
elif n <=99:
    if k==1:
        print(n//10+9)
    elif k==2:
        print((n//10-1)*9+n%10)
    else:
        print(0)
    exit()
    """
elif n <=999:
    if k==1:
        print(n//100+9+9)
    elif k==2:
        print((n//100-1)*9+9*9)
    else:
        print(0)
    exit()
    """
else:
    if k==1:
        print(9*(lenn-1)+n//(10**(lenn-1)))
    elif k==2:
        result=0
        #先頭の文字を抜いた状態で
        result+=9*9*(lenn-1)*(lenn-2)//1//2
        #print(result)
        #先頭の文字を1ひいて
        result+=(n//(10**(lenn-1))-1)*9*(lenn-1)
        #print(result)

        for i in str(n)[1:]:
            result+=int(i)
        print(result)
    else:
        if lenn==3:
            result=(n//(10**(lenn-1))-1)*9*9
            temp=1
            for i in str(n)[1:]:
                temp=temp*int(i)
            result+=temp
            print(result)
            exit()
        else:
            result=0
            #先頭の文字を抜いた状態で
            result+=9*9*9*(lenn-1)*(lenn-2)*(lenn-3)//1//2//3
        #先頭の文字を1ひいて
            result+=(n//(10**(lenn-1))-1)*9*9*(lenn-1)*(lenn-2)//1//2
            temp=1
            i=1
            while i<lenn:
                j=i+1
                while j<lenn:
                    result+=int(str(n)[i])*int(str(n)[j])
                    j+=1
                i+=1

            print(result)

Submission status: Wrong Answer

Solution code:
import math
n=input()
k=int(input())
if len(n)>=3:
    x=int(n[0]+n[1]+n[2])
if len(n)>=2:
    y=int(n[0]+n[1])
z=int(n[0])

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

# k==1のもの数える
if k==1:
    print(z*len(n)+(9-z)*(len(n)-1))

elif k==2 and len(n)>=2:
    a=0
    b=0
    for i in range(1,11):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            elif int(str(i)+str(j))<(y-int(n[1]))+10:
                b+=1
            else:
                v=combinations_count(len(n),2)
                if len(n)>=3:
                    w=combinations_count(len(n)-1,2)
                    w1=b*(len(n)-2)
                    print(a*v+(81-a)*w+w1)
                else:
                    print(a*v)
                exit()

elif k==3 and len(n)>=3:
    a=0
    b=0
    c=0
    for i in range(1,11):
        for j in range(1,10):
            for k in range(1,10):
                if int(str(i)+str(j)+str(k))<=x:
                    a+=1
                elif int(str(i)+str(j)+str(k))<x-int(n[2])+10:
                    b+=1
                elif int(str(i)+str(j)+str(k))<x-int(n[1])-int(n[2])+100:
                    c+=1

                else:
                    v=combinations_count(len(n),3)
                    if len(n)>=4:
                        w=combinations_count(len(n)-1,3)
                        w1=combinations_count(len(n)-1,2)
                        w2=combinations_count(len(n)-2,2)
                        print(b*v+(729-b)*w+w1+w2)
                    else:
                        print(b*v)
                    exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
n=list(map(int,input()))
l=len(n)
k=int(input())
#print(n)
ans=0
if k==1:
	#最上位に0でない数字
	ans=n[0]+9*(l-1)
elif k==2:
	if k<=l: #lは2以上
		#最上位にn[0]次に0以外
		ans+=n[1]
		#最上位にn[0]次に0
		ans+=9*(l-2)
		#最上位にn[0]以外
		ans+=(n[0]-1)*9*(l-1)
		#最上位は0
		ans+=81*(l-1)*(l-2)//2
elif k==3:
	if k<=l: #lは3以上
		if n[1]!=0:
			#最上位にn[0]次にn[1]
			ans+=n[2]+9*(l-3)
			#最上位にn[0]次にn[1]以外
			ans+=(n[1]-1)*9*(l-2)
		#最上位にn[0]次に0
		ans+=81*(l-2)*(l-3)//2
		#最上位にn[0]以外
		ans+=(n[0]-1)*81*(l-1)*(l-2)//2
		#最上位はなし
		ans+=729*(l-1)*(l-2)*(l-3)//6
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
tmpn=int(str(n)[:k]+("0"*(len(str(n))-k)))
# print(tmpn)
if k==2 and n<11:
    print(0)
    quit()
if k==3 and n<111:
    print(0)
    quit()
nonzero=[]
cnt=0
for i in range(keta):
    if str(n)[i]!="0":
        nonzero.append([int(str(n)[i]),keta-i])
        cnt+=1
    if cnt==k:
        break
# print(nonzero)
    

ans=0
def combinations_count(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if k==1:
    ans+=int(str(n)[0])
    ans+=(keta-1)*9
if k==2:
    if len(nonzero)==2:
        ans+=nonzero[1][0]+(int(str(n)[0])-1)*9
        ans+=int(str(n)[0])*(nonzero[1][1]-1)*9
        ans+=combinations_count(keta-1,k)*81
    else:
        ans+=combinations_count(keta-1,k)*81
if k==3:
    if len(nonzero)==3:
        ans+=nonzero[2][0]+(nonzero[1][0]-1)*9+(int(str(n)[0])-1)*81
        ans+=int(str(n)[0])*nonzero[1][0]*(nonzero[2][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[2][1],2)*81
        ans+=combinations_count(keta-1,k)*81*9
    elif len(nonzero)==2:
        ans+=int(str(n)[0])*(nonzero[1][0]-1)*(nonzero[1][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[1][1]-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
    else:
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
w=[int(i) for i in str(n)]
x=len(w)
ans=chk=0
if n<10000:
    for i in range(1,n+1):
        chk=0
        p=i
        while p>0:
            if p%10>0:
                chk+=1
            p//=10
        ans += chk==k
    print(ans)
    exit()
if k==3:
    for a in range(x-2):
        e=1
        for b in range(a+1,x-1):
            f=1
            for c in range(b+1,x):
                if a==0 and e and f:
                    ans+=(w[a]-1)*w[b]*9
                    ans+=1*(w[b]-1)*9
                    ans+=1*1*w[c]
                    if w[b]!=0 and w[c]!=0:
                        e=f=0
                    elif w[c]!=0:
                        f=0
                elif a==0 and e:
                    ans+=(w[a]-1)*w[b]*9
                    ans+=1*(w[b]-1)*9
                    ans+=1*1*w[c]
                    if w[b]!=0:
                        e=0
                else:
                    ans+=9**3
elif k==2:
    for a in range(x-1):
        for b in range(a+1,x):
            if a==0 and b==1:
                ans+=(w[a]-1)*9
                ans+=1*w[b]
            elif a==0:
                ans+=w[a]*9
            else:
                ans+=9**2
else:
    ans=w[0]*(9**(x-1))
print(ans)

Submission status: Wrong Answer

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

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


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

print(syou(n, k))

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = [int(x) for x in input()]
    K = int(input())
    dp = np.zeros((len(n)+1, 2, K+1), dtype=int)

    dp[0, 0, 0] = 1

    for i in range(len(n)):
        for k in range(0, K+1):
            for smaller in [0, 1]:
                # use 0
                dp[i+1, 1, k] += dp[i, smaller, k]
                # use 1~9
                r = 9 if smaller == 1 else n[i]
                for x in range(1, r+1):
                    # print(i+1, int(smaller==1 or x <n[i]), k+1, x)
                    if k+1 <= K:
                        dp[i+1, int(smaller == 1 or x < n[i]), k+1] += dp[i, smaller, k]
    print(dp[len(n), 0, K] + dp[len(n), 1, K])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N_str = input().strip()
L = len(N_str)
N_list = list(map(int, N_str))
N = int(N_str)
K = int(input())

def count1(s):
	if N_list[s] == 0:
		if s < L - 1:
			return count2(s + 1)
		else:
			return 0
	total = 0
	for i in range(s, L):
		if i == s:
			total += N_list[i]
		else:
			total += 9
	return total

def count2(s):
	if N_list[s] == 0:
		if s < L - 1:
			return count2(s + 1)
		else:
			return 0
	total = 0
	for i in range(s, L - 1):
		if i == s:
			if N_list[i] > 0:
				total += (N_list[i] - 1) * (L - i - 1) * 9
			total += count1(i + 1)
		else:
			total += 81 * (L - i - 1)
	return total

if K == 1:
	total = count1(0)
elif K == 2:
	total = count2(0)
else:
	total = 0
	for i in range(0, L - 2):
		if i == 0:
			if N_list[i] > 0:
				total += (N_list[i] - 1) * (L - i - 1) * 9 * (L - i - 2) * 9 // 2
			total += count2(i + 1)
		else:
			total += 729 * (L - i - 1) * (L - i - 2) // 2

print(total)

Submission status: Wrong Answer

Solution code:
import math
n=input()#as string
k=int(input())

e=9**k
f=len(n)
ans=0

zeroexist=True#途中桁に0が存在するかどうか

#kの範囲が極めて狭いので愚直に行く
if k==1:
    for i in range(f):
        if i==0:
            ans+=int(n[i])
        else:
            ans+=e
elif k==2:
    for i in range(f):
        for j in range(i+1,f):
            if i==0:
                ans+=(int(n[i])-1)*9
                if j==1:
                    ans+=int(n[j])
                    if int(n[j])!=0:
                        zeroexist=False
                else:
                    if zeroexist and int(n[j])!=0:
                        zeroexist=False
                    
                    if zeroexist:
                        ans+=int(n[j])
                    else:
                        ans+=9
            else:
                ans+=e
            
else:
    for i in range(f):
        for j in range(i+1,f):
            for k in range(j+1,f):
                if i==0:
                    ans+=(int(n[i])-1)*9*9
                    if j==1:
                        ans+=int(n[j])*9
                        if int(n[j])!=0:
                            zeroexist=False
                    else:
                        if zeroexist and int(n[j])!=0:
                            zeroexist=False
                        
                        if zeroexist:
                            if int(n[j])==0:
                                ans+=int(n[k])
                            else:
                                ans+=(int(n[j])-1)*9+int(n[k])
                        else:
                            ans+=9*9
                else:
                    ans+=e
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def Comb(n, r):
  if n < r:
    return 1
  else:
    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: Wrong Answer

Solution code:
n=int(input())
k=int(input())
counter = 0
for i in range(10**(k-1),n+1):
    if list(str(i)).count(str(range(1,9))) == k:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
n=input()
k=int(input())
p=len(n)
q=int(n[0])

if k==1:
    ans=9*(p-1)+q
if k==2:
    if int(n)>9:
        q2=int(n[1])
        ans=int(81*0.5*(p-1)*(p-2))
        ans+=9*(p-1)*(q-1)
        ans+=q2+9*(p-2)
    else:
        ans=0
    
if k==3:
    if int(n)>110:
        q2=int(n[1])
        q3=int(n[2])
        ans=int(729*((p-1)*(2*p-3)*(p-2)-3*(p-1)*(p-2))/12)
        ans+=81*(q-1)*(p-1)*(p-2)/2
        ans+=81*(p-2)*(p-3)/2
        ans+=9*(p-3)*q2
        ans+=(q2-1)*9
        ans+=q3
    else:
        ans=0

print(int(ans))

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
N=input()
K=int(input())
if len(N)<K:
    print(0)
    exit()
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += (int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*(len(N)-2)+int(N[1])
else:
    ans += int(N[2])+(len(N)-3)*9+(int(N[1])-1)*(len(N)-2)*9+comb(len(N)-2,2)*81
print(int(ans))

Submission status: Wrong Answer

Solution code:
import itertools
#nCr
import math
def com(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n=input()
k=int(input())
m=len(n)
if k==1:
    x=int(n[0])
    print(9*(m-1)+x)
    exit()
ans=0
x=int(n[0])
ans+=9**k*com(m-1,k)+(x-1)*com(m-1,k-1)*9**(k-1)
# print(9**k*com(m-1,k),(x-1)*com(m-1,k-1)*9**(k-1))
i=1
while i<m and n[i]=="0":
    i+=1
if k==3:
    if m<3:
        print(0)
        exit()
    if i==1:
        x=int(n[1])
        ans+=9**2*com(m-2,2)+(x-1)*com(m-2,1)*9
        ans+=int(n[2])+9*(m-3)
    if i==2:
        if m>=4:
            x=int(n[2])
            ans+=9**2*com(m-3,2)+(x-1)*com(m-3,1)*9
            ans+=int(n[2])+9*(m-4)+1
elif k==2:
    if m==1:
        print(0)
        exit()
    if i==1:
        ans+=int(n[1])+9*(m-2)
print(ans)

Submission status: Wrong Answer

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

N = str(N)
N_keta = len(N)
p = N[0]

if K == 1:
    print(int(p))

else:
    M = int(N) - int(p)*(10**(int(N_keta)-1))
    M = str(M)
    M_keta = len(M)
    q = M[0]
    if K == 2:
        if int(N) <= 9:
            print(0)
        else:
            kotae = 9 * (int(N_keta)-1) * (int(p)-1) + int(q) + 9 * (int(M_keta)-1) 
            print(int(kotae))
    else:
        if int(N) <= 99:
            print(0)
        else:
             L = int(M) - int(q)*(10**(int(M_keta)-1))
             L = str(L)
             L_keta = len(L)
             r = L[0]
             kotae = 9 * (int(M_keta)-1) * (int(q)-1) + int(r) + 9 * (int(L_keta)-1) + (int(p)-1)*(int(N_keta)-1)*(int(N_keta)-2)*0.5*81
             print(int(kotae))