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 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'+'0'*(K-1)):
    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:
N = input()
K = int(input())

ans = 0
if K == 1:
    for i in range(1,len(N)+1):
        if i != len(N):
            ans += 9
        else:
            ans += int(N) // (10 ** (i-1))
elif K == 2:
    for i in range(2, len(N)+1):
        if i != len(N):
            ans += 9 * 9 * (i-1)
        else:
            s = 0
            n = int(N) // (10 ** (i-1))
            ans += (n-1) * 9 * (i-1)
            for j in range(1,len(N)):
                if s == 0 and int(N[j]) == 0:
                    continue
                elif s == 1:
                    ans += 9
                else:
                    ans += int(N[j])
                    s = 1
elif K == 3:
    for i in range(3, len(N)+1):
        if i != len(N):
            ans += 9 * 9 * 9 * (((i-1) * (i-2)) // 2)
        else:
            s = 0
            n = int(N) // (10 ** (i-1))
            ans += (n-1) * 9 * 9 * (((i-1) * (i-2)) // 2)
            for j in range(1,len(N)):
                if s == 0 and int(N[j]) == 0:
                    continue
                elif s == 1:
                    ans += 9 * 9 * (((len(N)-j) * (len(N)-j-1)) // 2)
                    break
                else:
                    ans += (int(N[j])-1) * 9 * (len(N)-j-1)
                    for k in range(j+1,len(N)):
                        if s == 0 and int(N[k]) == 0:
                            continue
                        elif s == 1:
                            ans += 9
                        else:
                            ans += int(N[k])
                            s = 1
print(ans)

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(int('1'+'0'*(K-1))):
        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:
n = input()
k = int(input())

dp1 = [ [ i+1 for i in range(9) ] for i in range(201)]
dp2 = [ [ 0 for i in range(9) ] for i in range(201)]
dp3 = [ [ 0 for i in range(9) ] for i in range(201)]

for i in range(200):
    for j in range(9):
        if j == 0:
            dp1[i+1][j] = dp1[i][-1] + 1
        else:
            dp1[i+1][j] = dp1[i+1][j-1] + 1

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp3[i+1][j] = dp3[i][-1] + 81 * i*(i-1)//2
        else:
            dp3[i+1][j] = dp3[i+1][j-1] + 81 * (i+1) * i //2


def solve(s, x):
    if s[0] == "0":
        return 0
    

    if x == 1:

        return  dp1[len(s)-1][int(s[0]) - 1]
    elif x == 2:
        if len(s) < 2:
            return 0
        return  dp2[len(s)-1][int(s[0]) - 1] + solve(s[1:], 1)
    elif x == 3:
        if len(s) < 3:
            return 0
        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

Submission status: Wrong Answer

Solution code:
# E
import numpy as np
import math
N = int(input())
K = int(input())

lenN = len(str(N))
ans = 0
N_tmp = N

if K == lenN:
    N_low = 10**(lenN-1)
    ans += N - N_low - (N//10-N_low//10)

i = lenN-1
if K <= i:
    cycle = N_tmp//10**i
    N_tmp -= cycle * 10**i
    ans += math.factorial(i+K-1) / \
        math.factorial(i-1)/math.factorial(K)*9
    K -= 1
    if K == 0:
        ans += 1


for i in range(K, lenN-1)[::-1]:
    if K == 0:
        break
    cycle = N_tmp//10**i
    N_tmp -= cycle * 10**i
    ans += math.factorial(i+K-1) / \
        math.factorial(i-1)/math.factorial(K)*9*cycle
    if cycle > 0:
        K -= 1
    if K == 0:
        ans += 1


print(int(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))

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)
    elif a > b:
        return 0
    if i == n and kt == 0:
        return 1
    elif i > n:
        return 0
    ret = 0
    for j in range(10):
        f = 0
        if j != 0:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

ans = dfs(0, m, k)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
A = 0
if N <= 100000:
    for i in range(1,N+1):
        c = str(i)
        d = len(c) - c.count('0')
#    print(i,c,d,len(c),c.count('0'))
        if d == K:
            A += 1
else:
    keta = len(str(N))
    if K ==1:
        A = 9*(keta-1)
    if K ==2:
        A = 9*9*(keta-1)*(keta-2)//2
    if K ==3:
        A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
    nc = 1
#    print(N,K,keta,A)
    while nc <= 3 and keta >=1:
        # abcd... -> 1000000 - a0000000
        T = N//(10**(keta-1))%10
#        print(T,nc)
        if T == 0:
            keta -=1
        else:
            if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
              A = A + (T)
            if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
                A = A + int((T-1)*9*(keta-1))
            if (nc==2 and K==2):
                A = A + 9*(keta-1)
            if (nc==1 and K ==3):
                A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
            if (nc==2 and K==3):
                A = A + int(9*9*(keta-1)*(keta-2)/2)
            nc +=1
            keta -=1
#        print(A)
        
print(A)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
A = 0
if N <= 100000:
    for i in range(1,N+1):
        c = str(i)
        d = len(c) - c.count('0')
#    print(i,c,d,len(c),c.count('0'))
        if d == K:
            A += 1
else:
    keta = len(str(N))
    if K ==1:
        A = 9*(keta-1)
    if K ==2:
        A = 9*9*(keta-1)*(keta-2)//2
    if K ==3:
        A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
    nc = 1
#    print(N,K,keta,A)
    while nc <= 3 and keta >=1:
        # abcd... -> 1000000 - a0000000
        T = N//(10**(keta-1))%10
#        print(T,nc)
        if T == 0:
            keta -=1
        else:
            if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
              A = A + (T)
            if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
                A = A + int((T-1)*9*(keta-1))
            if (nc==2 and K==2):
                A = A + 9*(keta-1)
            if (nc==1 and K ==3):
                A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
            if (nc==2 and K==3):
                A = A + 9*9*(keta-1)*(keta-2)/2
            nc +=1
            keta -=1
#        print(A)
        
print(A)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
A = 0
if N <= 100000:
    for i in range(1,N+1):
        c = str(i)
        d = len(c) - c.count('0')
#    print(i,c,d,len(c),c.count('0'))
        if d == K:
            A += 1
else:
    keta = len(str(N))
    if K ==1:
        A = 9*(keta-1)
    if K ==2:
        A = 9*9*(keta-1)*(keta-2)//2
        print(A)
    if K ==3:
        A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
    nc = 1
    print(N,K,keta,A)
    while nc <= 3 and keta >=1:
        # abcd... -> 1000000 - a0000000
        T = N//(10**(keta-1))%10
        print(T,nc)
        if T == 0:
            keta -=1
        else:
            if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
              A = A + (T)
            if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
                A = A + int((T-1)*9*(keta-1))
            if (nc==2 and K==2):
                A = A + 9*(keta-1)
            if (nc==1 and K ==3):
                A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
            if (nc==2 and K==3):
                A = A + 9*9*(keta-1)*(keta-2)/2
            nc +=1
            keta -=1
        print(A)
        
print(A)

Submission status: Wrong Answer

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

    # 最上位からその数をとる。
    if len(n) == 1:
        tmp3 = 1
    else:
        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: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

def g(m, k):
    if k == 0:
        return 1
    if k == 1:
        return m * 9
    if k == 2:
        return m * (m-1) // 2 * 81
    if k == 3:
        return m * (m-1) * (m-2) // 6 * 729

@lru_cache(maxsize=None)
def f(n, k):
    if n == 0: return 0
    if k == 0: return 1
    S = str(n)
    t = int(S[0])
    m = len(S)
    return f(int("0" + S[1:]), k-1) + ((t-1) * g(m-1, k-1) if t else 0) + g(m-1, k)

N = int(input())
K = int(input())
print(f(N, K))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0
    if point2 == 99:
        print(ans)
        exit()
    for i in range(point2+1,100):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0
    if point3 == 999:
        print(ans)
        exit()
    for i in range(point3+1,1000):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "00":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-2)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0
    if point2 == 99:
        print(ans)
        exit()
    for i in range(point2+1,100):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0
    if point3 == 999:
        print(ans)
        exit()
    for i in range(point3+1,1000):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "00":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-3)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

def g(m, k):
    if k == 0:
        return 1
    if k == 1:
        return m * 9
    if k == 2:
        return m * (m-1) // 2 * 81
    if k == 3:
        return m * (m-1) * (m-2) // 6 * 729

@lru_cache(maxsize=None)
def f(n, k):
    if k == 0:
        return 1
    S = str(n)
    t = int(S[0])
    m = len(S)
    return f(int("0" + S[1:]), k-1) + ((t-1) * g(m-1, k-1) if t else 0) + g(m-1, k)

N = int(input())
K = int(input())
print(f(N, K))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict

IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

def fact_fun(n):
  if n == 0:
    return 1
  fact_num=int(1) 
  for i in range(1,n+1):
      fact_num=i*fact_num
  return fact_num

def c_n_x(case_count,real_count):
  fact_n = fact_fun(case_count)
  fact_x = fact_fun(real_count)
  fact_n_x = fact_fun(case_count - real_count)
  c_n_x_num = fact_n // (fact_x*fact_n_x)
  return c_n_x_num
def f(k):
    res=int(9)
    for i in range(1,k):
        res*=9
    return res

s = input()
l=len(s)
ans=int(0)
k=int(input())
for i in range(1,l):
    if k>i:continue
    num=i-k
    #print(str(i-1)+" "+str(k-1)+" "+str(c_n_x(i-1,k-1)*f(k)))
    ans+=c_n_x(i-1,k-1)*f(k)
#print(ans)
res=1
if k==1:
    ans+=int(s[0])
if k==2:
    flag=int(0)
    for i in range(1,l):
        
        ans+=(int(s[0])-1)*9+max((int(s[i])),flag)
        if int(s[i])>0:flag=9
if k==3:
    num1=int(0)
    num2=int(0)
    for i in range(1,l):
        num2=0
        for j in range(i+1,l):
            ans+=(int(s[0])-1)*9*9
            if num1==9:ans+=9*9
            else:ans+=(int(s[i])-1)*9+max(num1,1)*max(int(s[j]),num2)
            if int(s[j])>0:num2=9
        if int(s[i])>0:num1=9
       
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

if len(N) < K:
    print(0)
    sys.exit()

ans = 0

for i in range(K, len(N)+1):
    bc = 1
    for j in range(K-1):
        bc *= i-(j+1)
    if K-1 != 0:
        bc //= K-1
    else:
        bc = 1
    nonzero = (9**K)*bc
    ans += nonzero

if K == 1:
    ans -= 9-int(N[0])
elif K == 2:
    ans -= (9-int(N[0]))*(len(N)-1)*9
    ans -= 9-int(N[1])
else: # K==3
    ans -= (9-int(N[0]))*((len(N)-1)*(len(N)-2)//2)*81
    ans -= (9-int(N[1]))*(len(N)-2)*9
    ans -= 9-int(N[2])

if ans < 0:
    ans = 0

zero = 0
for i in range(len(N)):
    if N[i] == 0:
        zero += 1

if zero > 3:
    ans = 0
    for i in range(K, len(N)):
        bc = 1
        for j in range(K-1):
            bc *= i-(j+1)
        if K-1 != 0:
            bc //= K-1
        else:
            bc = 1
        nonzero = (9**K)*bc
        ans += nonzero

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0

    for i in range(point2,99):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0

    for i in range(point3,999):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "00":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-2)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce


nCr = {}
def cmb(n, r):
  if r == 0 or r == n: return 1
  if r == 1: return n
  if (n,r) in nCr: return nCr[(n,r)]
  nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
  return nCr[(n,r)]


def main():
  N = int(input())
  K = int(input())
  
  sn = str(N)
  order = len(sn)
    
  result = 0
  for i, c in enumerate(sn):
    n = order - i - 1  # i+1以降の桁数
    k = K - i  # 手前にi個の0以外の数字がある。
    
    if n == 0 and k == 1:
      result += int(c)
      break
    
    # 左からi桁目を0とする場合
    if n > 0 and k >= 0 and k <= n:
      result += cmb(n, k) * 9 ** k
    
    # 左からi桁目を0以外とする場合
    k -= 1
    if int(c) > 1 and n > 0 and k >= 0 and k <= n:
      result += (int(c) - 1) * cmb(n, k) * 9 ** k

  print(result)

main()

Submission status: Wrong Answer

Solution code:
n, k = input(), int(input())
z = [len(str(i))-str(i).count('0')==k for i in range(1000)]
for i in range(999): z[i+1] += z[i]

t = [0] + [9*(n[i-1]!='0') for i in range(1, len(n))]

def reter(r, p, sm):
    if r==0: return z[sm]
    ret = 0
    for i in range(p+1, len(n)-r+1):
        ret += reter(r-1, i, sm*10+max(t[i]*(i!=k-r), int(n[i])))
    return ret

print(reter(k, -1, 0))

Submission status: Wrong Answer

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: 範囲内に含まれるゼロでない数字の数
    """
    if K < 1:
        return 0
    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
    if L < K:
        return 0
    # 最上位桁が[0-(intN[0]-1)]のものをカウント
    if K >= 1:
        count += count_nonzero(L, intN[0]-1, K-0)
    # 最上位桁が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:K]が非ゼロなら、自分自身をカウント
    for d in intN[0:K]:
        if d == 0:
            return count
    count += 1
    return count


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

Submission status: Wrong Answer

Solution code:
def keta(n,k):
    s=str(n)
    l=len(s)-1
    if k==1:
        a=9*l
    elif k==2:
        a=81*l*(l-1)
    elif k==3:
        a=729*l*(l-1)*(l-2)
    
    i=10**l
    b=n-i+1
    for j in range(b):
        n=str(i).count('0')
        g=l-n+1
        i+=1
        if k == g:
            a+=1
    return a
N=int(input())
K=int(input())
print(keta(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:

        index = 1
        while (index < lenN):
            if int(strN[index]) != 0:
                ans += 9 * (lenN - 1 - index)
                ans += int(strN[index])
                break
            index += 1
        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:
        index = 1
        index_2 = 0
        while (index < lenN and index_2 == 0):
            if int(strN[index]) != 0:
                ans += (int(strN[index]) - 1) * 9 * (lenN - 1-index)
                index_2 += index+1
                while (index_2 < lenN):
                    if int(strN[index_2]) != 0:
                        ans += int(strN[index_2])
                        ans += 9*(lenN-1-index_2)
                        break
                    index_2 += 1
            index += 1
        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 sys

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

if len(N) < K:
    print(0)
    sys.exit()

ans = 0

for i in range(K, len(N)+1):
    bc = 1
    for j in range(K-1):
        bc *= i-(j+1)
    if K-1 != 0:
        bc //= K-1
    else:
        bc = 1
    nonzero = (9**K)*bc
    ans += nonzero

if K == 1:
    ans -= 9-int(N[0])
elif K == 2:
    ans -= (9-int(N[0]))*(len(N)-1)*9
    ans -= 9-int(N[1])
else: # K==3
    ans -= (9-int(N[0]))*((len(N)-1)*(len(N)-2)//2)*81
    ans -= (9-int(N[1]))*(len(N)-2)*9
    ans -= 9-int(N[2])

if ans < 0:
    ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
import math
def comb(n,k):
  if n==k and n==0:
    return 1
  if n<=0 or k<0 or n<k:
    return 0
  return math.factorial(n)/(math.factorial(k) * math.factorial(n-k))


N=int(input())
K=int(input())
dig = []
n = math.floor(math.log10(N))+1
for i in range(n):
  dig.append(N // 10**(n-i-1))
  N -= dig[i] * 10**(n-i-1)
ans = 0
ans += (comb(n-1,K) * math.floor(9**K))
ans += (dig[0]-1)* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + 9* (comb(n-2,K-2) * math.floor(9**(K-2))) )

if n>1:
  ans += 1* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + (dig[1]-1)* (comb(n-2,K-2) * math.floor(9**(K-2))) )
  if n==2:
    ans += 1
  if n>2:
    ans += 1* ( (comb(n-3,K-2) * math.floor(9**(K-2))) + (dig[2])* (comb(n-3,K-3) * math.floor(9**(K-3))) )
    
print(int(ans))

Submission status: Wrong Answer

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

rows = len(str(N))

if K > rows:
    print(0)
    sys.exit(0)

m = [[0] * (K+1) for _ in range(rows+1)]
m[1][1] = 9

for i in range(2, rows+1):
    for j in range(1, K+1):
        if j == 1:
            m[i][j] = m[i-1][j] + 9
        else:
            m[i][j] = m[i-1][j] + m[i-1][j-1] * 9

ans = 0
M = int(str(N)[:K])

for i in range(0, M+1):
    j = str(i).zfill(K)
    c = j.count("0")
    if c == K:
        ans += m[rows-K][K]
    elif c == 0:
        ans += 1
    else:
        ans += m[rows-K][c]

print(ans)

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:
        n = str(int(n))
        return 9*(len(n)-1)+int(n[0])
    t = ''.join(['9']*(len(n)-1))
    t2 = t
    w = (int(n[0])-1)
    if n[0] == '0':
        t2 = n[1:]
        w = 0
    return rec(t2, k) + w*rec(t2, k-1) + rec(n[1:], k-1)
print(rec(N,K))

Submission status: Wrong Answer

Solution code:
''' Hey stalker :) '''
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    n = list(input())
    k = get_int()
    ln = len(n)
    ans = 0
    def solve(nz, ind, locked = False):
        if nz == 0: return 1
        if ind>=ln: return 0
        num = int(n[ind])
        ans = 0
        for index in range(ind,ln):
            if locked and ind==index:
                if num==0: return 0
                for i in range(index+1, ln):
                    if int(n[i])>0:
                        ans += solve(nz-1, i, True)
                        break
                ans += solve(nz-1, index+1)*(num-1)
            else: ans += solve(nz-1, index+1)*9
        #print(nz, ind, locked, ans)
        return ans

    ans = solve(k,0, True)
    print(ans)


''' Pythonista fLite 1.1 '''
import sys
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right
#from functools import reduce
import math
#input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()
#[main() for _ in range(int(input()))]
print(*out, sep='\n')

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))
    t2 = t
    w = (int(n[0])-1)
    if n[0] == '0':
        t2 = n[1:]
        w = 0
    return rec(t2, k) + w*rec(t2, k-1) + rec(n[1:], k-1)
print(rec(N,K))

Submission status: Wrong Answer

Solution code:
import math
def comb(n,k):
  if n==k and n==0:
    return 1
  if n<=0 or k<0 or n<k:
    return 0
  return math.factorial(n)/(math.factorial(k) * math.factorial(n-k))


N=int(input())
K=int(input())
dig = []
n = math.floor(math.log10(N))+1
for i in range(n):
  dig.append(N // 10**(n-i-1))
  N -= dig[i] * 10**(n-i-1)
ans = 0
ans += (comb(n-1,K) * math.floor(9**K))
ans += (dig[0]-1)* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + 9* (comb(n-2,K-2) * math.floor(9**(K-2))) )

if n>1:
  ans += 1* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + (dig[1]-1)* (comb(n-2,K-2) * math.floor(9**(K-2))) )
  
  if n>2:
    ans += 1* ( (comb(n-3,K-2) * math.floor(9**(K-2))) + (dig[2])* (comb(n-3,K-3) * math.floor(9**(K-3))) )
    
print(int(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:
    # top桁を0にする
    if keta -1 >= 2:
        ans += (keta-1)*(keta-2)//2 * 9*9
    # top桁に数字が入る
    if keta >= 2:
        # top桁はNより小さい
        ans += (int(str(N)[0])-1) * (keta-1) * 9
        # top桁がNに一致
        ans += suu[1] + 9 * (keta-2)
    print(ans)
else:
    # top桁を0にする
    if keta - 1 >= 3:
        ans += (keta-1)*(keta-2)*(keta-3)//6 * 9*9*9
    if keta >= 3:
        #top桁はNより小さい
        ans += (int(str(N)[0])-1) * (keta-1)*(keta-2)//2 * 9 * 9
        #top桁はNに一致し、かつ次の桁が0
        ans += (keta-2)*(keta-3)//2 * 9 * 9
        #top桁はNに一致し、かつ次の桁がNより小さい
        ans += (int(str(N)[1])-1) * (keta-2) * 9
        #top桁はNに一致し、かつ次の桁もNに一致
        ans += suu[2] + 9 * (keta-3)
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
def comb(n,k):
  if n==k and n==0:
    return 1
  if n<=0 or k<0 or n<k:
    return 0
  return math.factorial(n)/(math.factorial(k) * math.factorial(n-k))


N=int(input())
K=int(input())
dig = []
n = math.floor(math.log10(N))+1
for i in range(n):
  dig.append(N // 10**(n-i-1))
  N -= dig[i] * 10**(n-i-1)
ans = 0
ans += (comb(n-1,K) * math.floor(9**K))
print(ans)
ans += (dig[0]-1)* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + 9* (comb(n-2,K-2) * math.floor(9**(K-2))) )
print(ans)
if n>1:
  ans += 1* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + (dig[1]-1)* (comb(n-2,K-2) * math.floor(9**(K-2))) )
  print(ans)
  if n>2:
    ans += 1* ( (comb(n-3,K-2) * math.floor(9**(K-2))) + (dig[2])* (comb(n-3,K-3) * math.floor(9**(K-3))) )
    print(ans)
print(int(ans))