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:
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
    for i in range(1,10):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            else:
                break

    v=combinations_count(len(n),2)
    if len(n)>=3:
        w=combinations_count(len(n)-1,2)
        w1=(9-int(n[1]))*(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
    for i in range(1,10):
        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)) < z * 100 + 100:
                    b+=1
                else:
                    break
    v=combinations_count(len(n),3)
    if len(n)>=4:
        w=combinations_count(len(n)-1,3)
        w1=combinations_count(len(n)-1,2)*(9-int(n[2]))
        w2=combinations_count(len(n)-2,2)*b
        print(a*v+(729-a)*w+w1+w2)
    else:
        print(a*v)
        exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=input()
K=int(input())
km = len(N)
res = 0
if int(N)<=1000:
    for i in range(int(N)):
        c = Counter(str(i+1))
        if len(str(i+1)) - c['0']==K:
            res += 1
    print(res)
    exit()
d = [[0]*3 for _ in range(100001)]
for i in range(100000):
    d[i+1] = d[i][:]
    c = Counter(str(i+1))
    k=len(str(i+1)) - c['0']
    if k<=3:
        d[i+1][k-1] += 1
def rec(n,k):
    re = 0
    if int(n)<100000:
        re = 0
        return d[int(n)][k-1]
    if k==1:
        return 9*(len(n)-1)+int(n[0])
    t = ''.join(['9']*(len(n)-1))
    return rec(t, k) + (int(n[0])-1)*rec(t, k-1) + rec(n[1:], k-1)
print(rec(N,K))

Submission status: Wrong Answer

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

def num(x):
  s=len(str(x))
  t=int(str(x)[0])
  return 9*(s-1)+t

l=str(n)
m=len(l)

ans=0

if k==1:
  a=int(l[0])
  ans+=9*(m-1)+a
elif k==2:
  a=int(l[0])
  ans += 9*9*(m-1)*(m-2)//2
  ans += (a-1)*9*(m-1)
  ans += num(n-a*10**(m-1))
elif k==3:
  a=int(l[0])
  b=int(l[1])
  ans += 9*9*9*(m-1)*(m-2)*(m-3)//12
  ans += (a-1)*9*(m-1)
  
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        dp[("T",i,0)]=1
        dp[("T",i,1)]=max(x-1,0)
        dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            dp[("T",i,k)]+=dp[("T",i-1,k)]
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9
            dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1)
                dp[("T",i,k)]+=dp[("F",i-1,k)]
            else:
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
                             
print dp[("T",l,K)]+dp[("F",l,K)]

Submission status: Wrong Answer

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

def naive(N,K):
    count=0
    for i in range(1,N+1):
        if str(i).count("0")==len(str(i))-K:
            count+=1
    return count

import itertools 

N=one_int()
K=one_int()

sums = 0
N_len = len(str(N))
if N_len!=K:
    for i in range(K,0,-1):
        temp =list(itertools.combinations([j for j in range(N_len-i)],K-i+1))
    #     sums += 9**(i)
        add = 1
        if K>=i>1:
            add=naive(int(str(N)[:i-1]),i-1)
        sums += (9**(K-i+1)) * max((len(temp)),0) * add  
sums += naive(int(str(N)[:K]), K)

print(sums)

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)
    t = 0
    for i in range(keta3-3):
        t += (i+1)*i//2
    cnt = 729 * t
    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:
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
    for i in range(1,10):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            else:
                break

    v=combinations_count(len(n),2)
    if len(n)>=3:
        w=combinations_count(len(n)-1,2)
        w1=(9-int(n[1]))*(len(n)-2)
        print(a*v+(81-a)*w+w1)
    else:
        print(a*v)
        exit()

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        dp[("T",i,0)]=1
        dp[("T",i,1)]=max(x-1,0)
        dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            dp[("T",i,k)]+=dp[("T",i-1,k)]
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9
            dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1)
                dp[("T",i,k)]+=dp[("F",i-1,k)]
                
print dp[("T",l,K)]+dp[("F",l,K)]

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
import math

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

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

    ans = 0
    # 最上桁が0のとき
    if len(N)-1 >= K:
        ans += combinations_count(len(N)-1, K) * 9**K
    # 最上桁が非0のとき
    updigit = int(N[0:K])
    counter = [0]*(K+1)
    if updigit >= int('1'*K):
        for i in range(int('1'+'0'*(K-1)), updigit+1):
            counter[str(i).count('0')] += 1
    for i, c in enumerate(counter):
        if len(N)-K >= i:
            ans += c * combinations_count(len(N)-K, i) * 9**i

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=input()
K=int(input())
km = len(N)
res = 0
if int(N)<=1000:
    for i in range(int(N)):
        c = Counter(str(i+1))
        if len(str(i+1)) - c['0']==K:
            res += 1
    print(res)
    exit()
def rec(n,k):
    re = 0
    if int(n)<1000:
        re = 0
        for i in range(int(n)):
            c = Counter(str(i+1))
            if len(str(i+1)) - c['0']==k:
                re += 1
        return re
    if k==1:
        return 9*(len(n)-1)+int(n[0])
    t = ''.join(['9']*(len(n)-1))
    return rec(t, k) + (int(n[0])-1)*rec(t, k-1) + rec(n[1:], k-1)
print(rec(N,K))

Submission status: Wrong Answer

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

        ans += 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)

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

elif K == 3:
    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:
import numpy as np
n=input()
k=int(input())
dp=np.zeros((len(n)+1,k+1,2))
dp[0][0][0]=1
for i in range(1,len(n)+1):
    for j in range(int(n[i-1])):
        if j==0:
            dp[i][1]+=dp[i-1][0]
        else:
            dp[i][1][1:]+=dp[i-1][0][:-1]
    for j in range(10):
        if j==0:
            dp[i][1]+=dp[i-1][1]
        else:
            dp[i][1][1:]+=dp[i-1][1][:-1]
    if int(n[i-1])==0:
        dp[i][0]+=dp[i-1][0]
    else:
        dp[i][0][1:]+=dp[i-1][0][:-1]
print(dp[-1][0][-1]+dp[-1][1][-1])

Submission status: Wrong Answer

Solution code:
factorial_L = [1] * 101
for i in range(2, 101):
    factorial_L[i] = factorial_L[i-1] * i

def permutations_count(n, r):
    return factorial_L[n] // factorial_L[n - r]


N_str = input()
N_int = int(N_str)
K = int(input())  # 1, 2, 3
ans = 0
keta = len(N_str)

S_keta = [[0] * (keta+1) for _ in range(K+1)]
for k in range(1, K+1):
    for i in range(1, keta+1):
        S_keta[k][i] = (permutations_count(i, k) // factorial_L[k]) * (9 ** (k))



def solve(nketa, k):
    if k == 1 and nketa == 1:
        return int(N_str[-1])
    if k == 2 and nketa == 2:
        last_2 = int(N_str[-2])
        if last_2 == 0:
            return 0
        return int(last_2-1) * 9 + int(N_str[-1])
    if k == 3 and nketa == 3:
        last_3 = int(N_str[-3])
        if last_3 == 0:
            return 0
        return int(last_3-1) * 81 + solve(2,2)
    if nketa < k:
        return 0
    if nketa == 0:
        return 0
    ret = 0
    ret += S_keta[k][nketa-1]
    if k-1 == 0:
        ret += int(N_str[keta-nketa])
    else:
        ret += (int(N_str[keta-nketa]) -1) * S_keta[k-1][nketa-1]
        ret += solve(nketa-1, k-1)
    return ret
print(solve(keta, K))

Submission status: Wrong Answer

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

keta = len(str(N))
not_kumi = list(itertools.combinations(range(keta), K))
count = 0

kumikomi = list(itertools.product(range(1,10), repeat = K))

for i in range(len(not_kumi)):   
    for j in range(len(kumikomi)):
        num = "".join(str("0") for i in range(keta))
        num = list(num)
        for k in range(K):
            num[not_kumi[i][k]] = str(kumikomi[j][k])
        
        for k in range(keta):
            if num[0]== "0":
                del num[0]
            else:
                exit
        num = int("".join(num))
        
        
        if num < N:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
factorial_L = [1] * 101
for i in range(2, 101):
    factorial_L[i] = factorial_L[i-1] * i

def permutations_count(n, r):
    return factorial_L[n] // factorial_L[n - r]


N_str = input()
N_int = int(N_str)
K = int(input())  # 1, 2, 3
ans = 0
keta = len(N_str)

S_keta = [[0] * (keta+1) for _ in range(K+1)]
for k in range(1, K+1):
    for i in range(1, keta+1):
        S_keta[k][i] = (permutations_count(i, k) // factorial_L[k]) * (9 ** (k))
        # if S_keta[k][i] == 0:
        #     S_keta[k][i] = 1



def solve(nketa, k):
    if k == 1 and nketa == 1:
        return int(N_str[-1])
    if k == 2 and nketa == 2:
        last_2 = int(N_str[-2])
        if last_2 == 0:
            return 0
        return int(last_2-1) * 9 + int(N_str[-1])
    if nketa < k:
        return 0
    if nketa == 0:
        return 0
    ret = 0
    ret += S_keta[k][nketa-1]
    # ret += ( int(N_str[keta-nketa])) * solve(nketa-1, k-1)
    if k-1 == 0:
        ret += int(N_str[keta-nketa])
    else:
        ret += (int(N_str[keta-nketa]) -1) * S_keta[k-1][nketa-1]
        ret += solve(nketa-1, k-1)
    return ret
print(solve(keta, K))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
R = len(str(n))
r = R - 1
q = 0
num = [0] * 4
index = [0] * 4
s = str(n)
for i in range(R):
    if s[i] != "0":
        num[q] = int(s[i])
        index[q] = i
        q += 1
    if q == 4:
        break

if k == 1:
    ans = 9 * r + num[0]
elif k == 2:
    ans = 81 * r * (r-1) // 2
    if num[1] != 0:
        pass
    else:
        num[1] = 9
        index[1] = 1
    ans += 9 * (R - 1) * (num[0] - 1) + num[1] + 9 * (R - index[1] - 1)
elif k == 3:
    ans = 243 * r * (r-1) * (r-2) // 2
    if num[2] != 0:
        pass
    elif num[1] != 0:
        num[1] -= 1
        index[2] = index[1] + 1
        num[2] = 9
    else:
        num[0] -= 1
        index = [0, 1, 2]
        num[1], num[2] = 9, 9
    ans += 81 * (R-1)*(R-2)*(num[0]-1)//2 + 9 * (R - index[1] - 1) * (num[1] - 1)
    ans += 81 * (R-index[1]-1)*(R-index[1]-2) // 2
    ans += 9 * (R - index[2] - 1) + num[2]
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc154/abc154_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2s()
    K = i2n()
    res = AEZ(N, K, 0)
    print(res)
    return

def AEZ(N, K, res):
    if K == 0:
        return 1
    if len(N) == 0:
        return 0
    N_len = len(N)
    under_d_sum = C(N_len - 1, K) * 9**K
    head = int(N[0])
    #print(N, K, res, under_d_sum, head)
    res = res + under_d_sum + (head-1) * AEZ('9'*(len(N)-1), K-1, res) + AEZ(N[1:], K-1, res)
    return res


def C(n,m):
    if n < m:
        return 0
    if n <= 0:
        return 0
    num = 1
    for i in range(m):
        num *= (n-i)
    if m == 3:
        m = 6
    return num // m

main()

Submission status: Wrong Answer

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


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

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

    if k == 0 or keta < k:
        return 0
    t = n[0]
    s = ""

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
ans = 0
if k == 1:
    if n < 10:
        ans = n
    else:
        l = len(str(n))
        ans += 9 * (l - 1)
        ans += int(str(n)[0])
elif k == 2:
    if n < 11:
        ans = 0
    else:
        l = len(str(n))
        for i in range(2, l):
            ans += 9 * 9 * (i - 1)
        f = int(str(n)[0])
        ans += (f - 1) * 9 * (l - 1)
        num = l - 1
        f = 0
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += f
        ans += 9 * (l - num - 1)
else:
    if n < 111:
        ans = 0
    else:
        l = len(str(n))
        for i in range(3, l):
            ans += 9 * 9 * 9 * (i - 1) * (i - 2) // 2

        f = int(str(n)[0])
        ans += (f - 1) * 9 * 9 * (l - 1) * (l - 2) // 2

        num = l - 1
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += (f - 1) * (l - num - 1) * 9
        ans += 9 * 9 * (l - num - 1) * (l - num - 2) // 2

        num = l - 1
        f = 0
        for i in range(num + 1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += (l - num - 1) * 9
        ans += f
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce


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


s = input()
d = len(s)
m = int(s[0])
k = int(input())
a = 9**k * comb(d - 1, k)
if k == 1:
    a += m
elif k == 2:
    a += (m - 1) * 9 * max(d - 1, 0)
    for di, si in enumerate(s[1:]):
        if int(si) > 0:
            a += 9 * (d - di - 2)
            a += int(si)
            break
elif k == 3:
    a += (m - 1) * 9 * 9 * comb(d - 1, 2)
    for di, si in enumerate(s[1:]):
        if int(si) > 0:
            a += 9 * 9 * comb(d - di - 2, 2)
            a += int(si) * 9 * (d - di - 2)
            break
print(a)

Submission status: Wrong Answer

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

        ans += 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)

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

elif K == 3:
    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:
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))
    if n - r -1 > 0: ans += fc(n) // fc (r+1) // fc(n-r-1) *(9**(k-kazu +1))
    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(max(int(anss+1),1))

Submission status: Wrong Answer

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


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

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

    if k == 0 or keta < k:
        return 0
    t = n[0]
    s = ""

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

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

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

Submission status: Wrong Answer

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

def solve(n,k):

#    print("solve",n,k)

    if n<10**5:
        ans=0
        for num in range(1,n+1):
            cnt=0
            for char in str(num):
                if char!="0":
                    cnt+=1
            if cnt==k:
                ans+=1
        return ans

    keta = len(str(n))
    max_num=int(str(n)[0])

    if k==1:
        return max_num + 9*(keta-1)

    if n==max_num*(10**(keta-1)):
        if k==2:
            ans=max_num*(keta-1)*9
            return ans + solve(10**(keta-1) - 1,2)
        if k==3:
            ans=max_num*(keta-1)*(keta-2)/2 * 81
            return ans + solve(10**(keta-1) - 1,3)

    return solve(max_num*(10**(keta-1)),k)+solve(n-max_num*(10**(keta-1)),k-1)

print(solve(n,k))

Submission status: Wrong Answer

Solution code:
strN = input()
N = int(strN)
K = int(input())
ans = 0
N_copy = 0
N_copy += N
lenN = 0
for s in range(N):
    if N_copy > 0:
        lenN += 1
        N_copy //= 10
    else:
        break
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    if lenN >= 2:
        ans += int(strN[1])
        ans += 9 * (lenN - 2)
        ans += (int(strN[0]) - 1) * 9*(lenN-1)
        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])

elif K == 3:
    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 Pika(p,K):
    tmp = 1
    now = p
    for i in range(K):
        tmp *= now
        now -= 1
    now = 1
    for i in range(K):
        tmp //= now
        now += 1
    tmp *= 9**K
    return tmp

N = input()
K = int(input())
p = len(N)
def solve(N,K,p):
    if K==0:
        return 1
    elif N=='':
        return 0
    elif N[0]=='0':
        return solve(N[1:],K,p)
    else:
        ans = 0
        ans += Pika(p-1,K)
        atama = int(N[0])
        ans += (atama-1)*Pika(p-1,K-1)
        
        ans += solve(N[1:],K-1,p-1)
    
    return ans
A = solve (N,K,p)
print(A)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} #階乗
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) #組み合わせ

n = int(input())
k = int(input())
r = len(str(n))-1
st = str(n)
ans = 0
if k==1 and r>=0:
    ans += 9*r + int(st[0])
elif k==2 and r>=1:
    ans += 9**2 * comb(r, 2) + (int(st[0])-1) * 9**1 * comb(r, 1) + 9**1 * comb(r-1, 1) + int(st[1])
elif k==3 and r>=2:
    ans += comb(r, 3)*9**3\
           +comb(r, 2)*9**2*(int(st[0])-1)\
           +comb(r-1,2)*9**2\
           +comb(r-1, 1)*9**1*(int(st[1])-1)\
           +comb(r-2,1)*9\
           +int(st[2])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()
length = 0
for i in range(1, 100):
    if 10 ** i > N:
        length = i
        break

answer = 0
def F(length, K, N):
    ret = 0
    if length == 1:
        if K == 1:
            return N
        elif K == 0:
            return 1
        else:
            return 0
    if length < K:
        return 0
    top = int(str(N)[0])
    if length-K >= 1:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K # 一個前まで    
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) # 一桁目がtopより小さい数  
    if K > 1: # 一桁目がtopと同じ数
        N = int(str(N)[1:])
        length = 0
        for i in range(1, 100):
            if 10 ** i > N:
                length = i
                break
        ret += F(length, K-1, N)
    else:
        ret += 1 # 2000のような数
    return ret

answer = F(length, K, N)
print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#import itertools
#import numpy as np
import math

n = int(input())
k = int(input())
sn = str(n)
l = len(sn) # 10^(l-1) < n < 10^l
ans = 0
z = 0

def combinations_count(n, r):
    x = 1
    for y in range(n-r+1, n+1):
        x *= y
    for z in range(1, r+1):
        x //= z
    return x
    
if k <= l-1:
    ans += combinations_count(l-1, k) * (9 ** k)

if k <= l:
    # l桁の整数について
    if k == 1:
        z = int(sn[0])
        
    elif k == 2:
        z = (int(sn[0])-1) * (l-1)*9
        z += int(sn[1])
        z += (l-2) * 9
        
    else:
        z = (int(sn[0])-1) * combinations_count(l-1, 2)*81
        for i in range(l-2):
            z += int(sn[i+1]) * sum(list(map(int, list(sn[i+2:]))))

print(ans + z)

Submission status: Wrong Answer

Solution code:
import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r==1 or n==r==0:
    return 1
  else:
    return 1
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    #print(ans)
    if not_zero==K:
      ans+=1
      break
print(ans)

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,10):
        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

    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,10):
        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))<y*10+10:
                    b+=1
                elif int(str(i)+str(j)+str(k))<z*100+100:
                    c+=1
    v=combinations_count(len(n),3)
    if len(n)>=4:
        w=combinations_count(len(n)-1,3)
        w1=combinations_count(len(n)-1,2)*b
        w2=combinations_count(len(n)-2,2)*c
        print(a*v+(729-a)*w+w1+w2)
    else:
        print(a*v)
        exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r==1 or n==r==0:
    return 1
  else:
    return 1
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    print(ans)
    if not_zero==K:
      ans+=1
      break
print(ans)