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:
S = input()
N = len(S)
K = int(input())
def nCk(n, k):
    if n < k:
        return 0

    ans = 1
    for i in range(1, k+1):
        ans *= (n-i+1)
        ans //= i
    return ans

ans = 0
if K > N:
    print(ans) 
    exit()

for i in range(K):
    if i == K-1:
        ans += int(S[i])*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)
    else:
        if int(S[i]) != 0:
            ans += (int(S[i])-1)*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)
        else:
            ans += 9**(K-i)*nCk(N-1-i, K-i)

print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
K = int(input())
def nCk(n, k):
    if n < k:
        return 0

    ans = 1
    for i in range(1, k+1):
        ans *= (n-i+1)
        ans //= i
    return ans

ans = 0
if K > N:
    print(ans) 
    exit()

for i in range(K):
    if int(S[i]) == 0:
        continue

    if i == K-1:
        ans += int(S[i])*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)
    else:
        ans += (int(S[i])-1)*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)

print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
K = int(input())
def nCk(n, k):
    if n < k:
        return 0

    ans = 1
    for i in range(1, k+1):
        ans *= (n-i+1)
        ans //= i
    return ans

ans = 0
if K > N:
    print(ans) 
    exit()

for i in range(K):
    if int(S[i:]) == 0:
        break

    if i == K-1:
        ans += int(S[i])*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)
    else:
        ans += (int(S[i])-1)*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)

print(ans)

Submission status: Wrong Answer

Solution code:
def nCkpow(n,k):
    if n<k:
        return 0
    y=1
    for i in range(k):
        y*=n-i
        y//=i+1
        y*=9
    return y
def f(s,m,k):
    if len(s)-m<k:
        return 0
    if  k==0:
        return 1
    if s[m]==0:
        return f(s,m+1,k)
    l=len(s)-m
    y=nCkpow(l-1,k)
    y+=(int(s[m])-1)*nCkpow(l-1,k-1)
    return y+f(s,m+1,k-1)
N=input()
K=int(input())
print(f(N,0,K))

Submission status: Wrong Answer

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from  collections import defaultdict
from collections import Counter
import bisect


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

def main():
    N = S()
    K = I()
    dig = len(N)
    ans = 0
    for i in range(dig):
        if K == 0:
            ans += 1
            break
        if int(N[i]) == 0:
            continue
        if dig - i - 1 >= K:
            ans += combinations_count(dig - i - 1, K) * pow(9, K)
        if dig - i - 1 >= K - 1:
            ans += (int(N[i]) - 1) * combinations_count(dig - i - 1, K - 1) * pow(9, K - 1)
        if i == dig - 1:
            ans += 1
        K -= 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import math
def p(n, r):
    return math.factorial(n) // math.factorial(n - r)
def c(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if d < k:
    print(0)
    exit()

ans = 0
if d - n.count("0") >= k:
    # 上i桁が一致するときの桁が一致する場合の数
    dp = [0]*(k+1)
    dp[k] = 1
    for i in range(k)[::-1]:
        # 一致の時、1~n[i]のとき、0のとき
        if i != 0:
            dp[i] = dp[i+1] + (int(n[i])-1)*c(d-i-1,k-i-1)*pow(9,k-i-1) + c(d-i-1,k-i)*pow(9,k-i)
        elif i == 0:
            dp[i] = dp[i+1] + (int(n[i])-1)*c(d-i-1,k-i-1)*pow(9,k-i-1)
    # print(dp)
    # 桁数が一致しないときも足す
    ans += dp[0]

for i in range(k,d):
    # １つは一番左にあるので残りk-1を選ぶ
    ans += c(i-1,k-1)*pow(9,k)
    # print(ans)
print(ans)

Submission status: Wrong Answer

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

import math
def p(n, r):
    return math.factorial(n) // math.factorial(n - r)
def c(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if d < k:
    print(0)
    exit()
# 上i桁が一致するときの桁が一致する場合の数
dp = [0]*(k+1)
dp[k] = 1
for i in range(k)[::-1]:
    # 一致の時、1~n[i]のとき、0のとき
    if i != 0:
        dp[i] = dp[i+1] + (int(n[i])-1)*c(d-i-1,k-i-1)*pow(9,k-i-1) + c(d-i-1,k-i)*pow(9,k-i)
    elif i == 0:
        dp[i] = dp[i+1] + (int(n[i])-1)*c(d-i-1,k-i-1)*pow(9,k-i-1)
# print(dp)

# 桁数が一致しないときも足す
ans = dp[0]
for i in range(k,d):
    # １つは一番左にあるので残りk-1を選ぶ
    ans += c(i-1,k-1)*pow(9,k)
    # print(ans)
print(ans)

Submission status: Wrong Answer

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

dp = [[[0] * (K+1) for _ in range(2)] for _ in range(m+1)]
dp[0][0][0] = 1

for i in range(1,m+1):
    l = int(N[i-1])
    for k in range(K+1):
        if k-1>0:
            if l!=0:
                dp[i][0][k]=dp[i-1][0][k-1]
                dp[i][1][k] = dp[i-1][1][k] + 9 * dp[i-1][1][k-1]+dp[i-1][0][k] + (l-1) * dp[i-1][0][k-1]
            else:
                dp[i][0][k] = dp[i-1][0][k]
                dp[i][1][k] = dp[i-1][1][k] + 9 * dp[i-1][1][k-1]
        else:
            dp[i][0][k] = 0
            dp[i][1][k] = 1

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

Submission status: Wrong Answer

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

def c(i, j):
    i, j = i-1, j-1
    if j == 0:
        return 1
    r = 1
    for k in range(j):
        r *= (i-k) / (j-k)
    return int(r)


def d(n):
    if K == 1:
        return int(N[0])
    if K == 3:
        return (int(N[0])-1)*9**2 + (int(N[1])-1)*9 + int(N[2])
    if K == 2:
        return (int(N[0])-1) * 9 + int(N[1])


ans = 0
l = len(N)
for i in range(K, l+1):
    if i == l:
        ans += (c(i, K)-1)*int(N[0])*9**(K-1) + d(N)
    else:
        ans += c(i, K) * 9**K
    
print(ans)

Submission status: Wrong Answer

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

def c(i, j):
    i, j = i-1, j-1
    if j == 0:
        return 1
    r = 1
    for k in range(j):
        r *= (i-k) / (j-k)
    return int(r)


def d(n):
    if K == 1:
        return int(N[0])
    if K == 3:
        return (int(N[0])-1)*9**2 + int(N[1]) * int(N[2])
    if K == 2:
        return (int(N[0])-1) * 9 + int(N[1])


ans = 0
l = len(N)
for i in range(K, l+1):
    if i == l:
        ans += (c(i, K)-1)*int(N[0])*9**(K-1) + d(N)
    else:
        ans += c(i, K) * 9**K
    
print(ans)

Submission status: Wrong Answer

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

def c(i, j):
    i, j = i-1, j-1
    if j == 0:
        return 1
    r = 1
    for k in range(j):
        r *= (i-k) / (j-k)
    return int(r)


def d(n):
    if K == 1:
        return int(N[0])
    if K == 3:
        return (int(N[0])-1)*9**2 + int(N[1]) * int(N[2])
    if K == 2:
        return (int(N[0])-1) * 9 + int(N[1])


ans = 0
l = len(N)
for i in range(K, l+1):
    if i == l:
        print((c(i,K)-1)*int(N[0])*9**(K-1))
        ans += (c(i, K)-1)*int(N[0])*9**(K-1) + d(N)
    else:
        ans += c(i, K) * 9**K
    
print(ans)

Submission status: Wrong Answer

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

def c(i, j):
    i, j = i-1, j-1
    if j == 0:
        return 1
    r = 1
    for k in range(j):
        r *= (i-k) / (j-k)
    return int(r)


def d(n):
    if K == 1:
        return int(N[0])
    if K == 3:
        return (int(N[0])-1)*9**2 + int(N[1]) * int(N[2])
    if K == 2:
        return (int(N[0])-1) * 9 + int(N[1])


ans = 0
l = len(N)
for i in range(K, l+1):
    if i == l:
        ans += max(0,(c(i, K)-1))*9**(K-1)*int(N[0]) + d(N)
    else:
        ans += c(i, K) * 9**K
    
print(ans)

Submission status: Wrong Answer

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

def c(i, j):
    i, j = i-1, j-1
    if j == 0:
        return 1
    r = 1
    for k in range(j):
        r *= (i-k) / (j-k)
    return int(r)


def d(n, k):
    if K == 1:
        return int(N[0])
    if K == 3:
        return int(N[0]) * int(N[1]) * int(N[2])
    if K == 2:
        return (int(N[0])-1) * 9 + int(N[1])


ans = 0
l = len(N)
for i in range(K, l+1):
    if i == l:
        ans += max(0,(c(i, K)-1))*9**(K-1)*int(N[0]) + d(N,K)
    else:
        ans += c(i, K) * 9**K
    
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def per(n, r, mod=10**9+7):  # 順列数
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per


def com(n, r, mod=10**9+7):  # 組み合わせ数
    bunshi = per(n, r, mod)
    bunbo = 1
    for i in range(1, r+1):
        bunbo = bunbo*i % mod
    return bunshi*pow(bunbo, -1, mod) % mod


def main():
    n = list(map(int, list(input())))
    k = int(input())
    keta = len(n)
    count = [n[0]-1+com(keta-1, 1)*9, (n[0]-1)*com(keta-1, 1)*9+com(keta-1, 2)
             * 9**2, (n[0]-1)*com(keta-1, 2)*9**2+com(keta-1, 3)*9**3]
    nonzero = 1
    #print(count)
    for i in range(1, keta):
        if n[i] != 0:
            nonzero+=1
            if nonzero==2:
                count[1]+=(n[i]-1)+com(keta-i-1,1)*9
                count[2]+=(keta-i-1)*(n[i]-1)*9+com(keta-i-1,2)*9**2
            elif nonzero==3:
                count[2]+=(n[i]-1)+com(keta-i-1,1)*9
        #print(count)
    print(count[k-1]+(keta>=k))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def per(n, r, mod=10**9+7):  # 順列数
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per


def com(n, r, mod=10**9+7):  # 組み合わせ数
    bunshi = per(n, r, mod)
    bunbo = 1
    for i in range(1, r+1):
        bunbo = bunbo*i % mod
    return bunshi*pow(bunbo, -1, mod) % mod


def main():
    n = list(map(int, list(input())))
    k = int(input())
    keta = len(n)
    count = [n[0]-1+com(keta-1, 1)*9, (n[0]-1)*com(keta-1, 1)*9+com(keta-1, 2)
             * 9**2, (n[0]-1)*com(keta-1, 2)*9**2+com(keta-1, 3)*9**3]
    nonzero = 1
    #print(count)
    for i in range(1, keta):
        if n[i] != 0:
            nonzero+=1
            if nonzero==2:
                count[1]+=(n[i]-1)+com(keta-i-1,1)*9
                count[2]+=(keta-i-1)*(n[i]-1)*9+com(keta-i-1,2)*9**2
            elif nonzero==3:
                count[2]+=(n[i]-1)+com(keta-i-1,1)*9
        #print(count)
    print(count[k-1]+1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
if N<=10**6:
  ans=0
  for i in range(1,N+1):
    a=str(i)
    if len(a)-list(a).count("0")==K:
      ans+=1
  print(ans)
  exit()
L=list(map(int,list(str(N))))
ans=0
L=list(map(int,list(str(N))))
for i in range(N,N+1001):
  L=list(map(int,list(str(i))))
  s=L[:3]
  if s[0]!=0 and s[1]!=0 and s[2]!=0:
    go=i
    break
go=N
for i in range(N+1,go+1):
  a=str(i)
  if len(a)-list(a).count("0")==K:
    ans-=1
if K==1:#おけ
  print((len(str(N))-1)*9+int(str(N)[0]))
elif K==2:#おけ
  N=go
  for i in range(len(L)-1):
    ans+=(9*(int(str(N)[0])-1))
    for j in range(i+1,len(L)):
      if i==0:
        if j==1:
          ans+=int(str(N)[1])
        else:
          ans+=9
      else:
        ans+=81
  print(ans)
else:
  N=go
  le=len(L)
  for i in range(le-2):
    for j in range(i+1,le-1):
      for k in range(j+1,le):
        if i==0:
          ans+=81*(int(str(N)[0])-1)
          if j==1:
            ans+=9*(int(str(N)[1])-1)
            if k==2:
              ans+=int(str(N)[2])
            else:
              ans+=9
          else:
            ans+=81
        else:
          ans+=729
  print(ans)

Submission status: Wrong Answer

Solution code:
n = list(map(int, list(input())))
k = int(input())

dp0 = [0]*3
dp1 = [[0]*3]*len(n)
dp0[0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    if n[i]!=0:
        dp0 = [0]+dp0[:2]

    dp1[i] = [
        dp1[i-1][0]+dp0[0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[1]*(n[i]!=0)+dp0[0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[2]*(n[i]!=0)+dp0[1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]

print(dp0[k-1]+dp1[-1][k-1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N=input()
K=int(input())
L = len(N)
# dp = [[[0]*(L+1) for _ in range(L+1)] for _ in range(2)]
nonzero = [0]*(L+1)
# nonzero[i]: i-1ケタ目までの非ゼロの累積個数
for i in range(1, L+1):
    nonzero[i] = nonzero[i-1] + int(N[i-1] != 0)

if K == 1:
    if L == 1:
        ans = int(N)
    else:
        ans = 0
        for tpl in combinations(range(L), 1):
            d1 = tpl[0]
            if d1 == 0:
                ans += int(N[d1])
            else:
                ans += 9
elif K == 2:
    if L == 1:
        ans = 0
    else:
        ans = 0
        for tpl in combinations(range(L), 2):
            d1, d2 = sorted(list(tpl))
            n1 = int(N[d1])
            n2 = int(N[d2])
            if d1 == 0:
                ans += (n1-1)*9
                if nonzero[d2] > 1:
                    ans += 9
                else:
                    ans += n2
            else:
                ans += 9 * 9

else:
    if L <= 2:
        ans = 0
    else:
        ans = 0
        for tpl in combinations(range(L), 3):
            d1, d2, d3 = sorted(list(tpl))
            n1 = int(N[d1])
            n2 = int(N[d2])
            n3 = int(N[d3])
            if d1 == 0:
                ans += (n1-1)*9*9
                if nonzero[d2] > 1:
                    ans += 9*9
                else:
                    if nonzero[d3] == 1:
                        pass
                    elif nonzero[d3] == 2:
                        if n2 == 0:
                            pass
                        else:
                            ans += (n2-1)*9 + n3
                    else:
                        ans += n2 * 9
            else:
                ans += 9*9*9

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N=input()
K=int(input())
L = len(N)
# dp = [[[0]*(L+1) for _ in range(L+1)] for _ in range(2)]
nonzero = [0]*(L+1)
# nonzero[i]: i-1ケタ目までの非ゼロの累積個数
for i in range(1, L+1):
    nonzero[i] = nonzero[i-1] + int(N[i-1] != 0)

if K == 1:
    ans = 0
    for tpl in combinations(range(L), 1):
        d1 = tpl[0]
        if d1 == 0:
            ans += int(N[d1])
        else:
            ans += 9
elif K == 2:
    ans = 0
    for tpl in combinations(range(L), 2):
        d1, d2 = sorted(list(tpl))
        n1 = int(N[d1])
        n2 = int(N[d2])
        if d1 == 0:
            ans += (n1-1)*9
            if nonzero[d2] > 1:
                ans += 9
            else:
                ans += n2
        else:
            ans += 9 * 9

else:
    ans = 0
    for tpl in combinations(range(L), 3):
        d1, d2, d3 = sorted(list(tpl))
        n1 = int(N[d1])
        n2 = int(N[d2])
        n3 = int(N[d3])
        if d1 == 0:
            ans += (n1-1)*9*9
            if nonzero[d2] > 1:
                ans += 9*9
            else:
                if nonzero[d3] == 1:
                    pass
                elif nonzero[d3] == 2:
                    if n2 == 0:
                        pass
                    else:
                        ans += (n2-1)*9 + n3
                else:
                    ans += n2 * 9
        else:
            ans += 9*9*9

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N=input()
K=int(input())
L = len(N)
# dp = [[[0]*(L+1) for _ in range(L+1)] for _ in range(2)]
nonzero = [0]*(L+1)
# nonzero[i]: i-1ケタ目までの非ゼロの累積個数
for i in range(1, L+1):
    nonzero[i] = nonzero[i-1] + int(N[i-1] != 0)

if K == 1:
    ans = 0
    for tpl in combinations(range(L), 1):
        d1 = tpl[0]
        if d1 == 0:
            ans += int(N[d1])
        else:
            ans += 9
    print(ans)
elif K == 2:
    ans = 0
    for tpl in combinations(range(L), 2):
        d1, d2 = sorted(list(tpl))
        n1 = int(N[d1])
        n2 = int(N[d2])
        if d1 == 0:
            ans += (n1-1)*9
            if nonzero[d2] > 1:
                ans += 9
            else:
                ans += n2
        else:
            ans += 9 * 9

else:
    ans = 0
    for tpl in combinations(range(L), 3):
        d1, d2, d3 = sorted(list(tpl))
        n1 = int(N[d1])
        n2 = int(N[d2])
        n3 = int(N[d3])
        if d1 == 0:
            ans += (n1-1)*9*9
            if nonzero[d2] > 1:
                ans += 9*9
            else:
                if nonzero[d3] == 1:
                    pass
                elif nonzero[d3] == 2:
                    if n2 == 0:
                        pass
                    else:
                        ans += (n2-1)*9 + n3
                else:
                    ans += n2 * 9
        else:
            ans += 9*9*9

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N=input()
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(L+1)] for _ in range(2)]
nonzero = [0]*(L+1)
# nonzero[i]: i-1ケタ目までの非ゼロの累積個数
for i in range(1, L+1):
    nonzero[i] = nonzero[i-1] + int(N[i-1] != 0)

if K == 1:
    ans = 0
    for tpl in combinations(range(L), 1):
        d1 = tpl[0]
        if d1 == 0:
            ans += int(N[d1])
        else:
            ans += 9
    print(ans)
elif K == 2:
    ans = 0
    for tpl in combinations(range(L), 2):
        d1, d2 = sorted(list(tpl))
        n1 = int(N[d1])
        n2 = int(N[d2])
        if d1 == 0:
            ans += (n1-1)*9
            if nonzero[d2] > 1:
                ans += 9
            else:
                ans += n2
        else:
            ans += 9 * 9

else:
    ans = 0
    for tpl in combinations(range(L), 3):
        d1, d2, d3 = sorted(list(tpl))
        n1 = int(N[d1])
        n2 = int(N[d2])
        n3 = int(N[d3])
        if d1 == 0:
            ans += (n1-1)*9*9
            if nonzero[d2] > 1:
                ans += 9*9
            else:
                if nonzero[d3] > 2:
                    ans += n2 * 9
                else:
                    ans += (n2-1)*9 + n3
        else:
            ans += 9*9*9

print(ans)

Submission status: Wrong Answer

Solution code:
# 314159, 2,
# 0[xxxxx] 5C2 * 9*9 = 810
# 1[xxxxx] 5C1 * 9 = 45
# 2[xxxxx] 5C1 * 9 = 45
# 3[xxxxx] わからん!
# 31[0000] = 1
# 30[xxxx] = 4C1 * 9 合わせて937

# 9999, 3,
# 0[xxx] 3C3 * 9*9*9 = 729
# [yxxx] y=8, x=3C2 * 9*9 = 8 * 243
# 9[xxx] = 3C2 * 9*9 = 243

# 94599, 3,
# 0[xxxx] 4C3 * 9*9*9 = 4 * 729
# 1[xxxx] x=4C2 * 9*9 = 6 * 81
# ...
# 8[xxxx] x=4C2 * 9*9 = 6 * 81
# 94[x]00 = 5
# 940[xx] 2C1 * 9
# 93[xxx] 3C1 * 9
str_n = input()
n = int(str_n)
k = int(input())

if k > len(str_n):
  print(0)
  exit()

head = n
while head >= 10:
  head //= 10
def choice(p, q):
  if p < q:
    return 0
  if p == q:
    return 1
  res = 1
  for i in range(q):
    res = (res * p)
    p -= 1
  for i in range(q):
    res = res // (i+1)
  return res

ans = choice(len(str_n)-1, k) * (9 ** k)
# todo: 100 とか 101 とかの head が1の場合にNG
for i in range(1, head):
  ans += choice(len(str_n)-1, k-1) * (9 ** (k-1))
if k == 3:
  ans += int(str_n[2])  # 99x0000
  ans += choice(len(str_n) - 3, 1) * 9  # 990xxx
  ans += max(0, int(str_n[1])-1) * choice(len(str_n) - 2, 1) * 9  # 9[1:8]xxxx
  ans += choice(len(str_n) - 2, 2) * 9*9  # 90xxxxx
if k == 2:
  if head == 1:
    ans += n - head * (10 ** (len(str_n)-1))
  else:
    ans += int(str_n[1])  # 9x0000
    ans += choice(len(str_n) - 2, 1) * 9 # 90xxx
if k == 1:
  ans += int(str_n[0]) if len(str_n) > 1 else 1

print(ans)

Submission status: Wrong Answer

Solution code:
# 314159, 2,
# 0[xxxxx] 5C2 * 9*9 = 810
# 1[xxxxx] 5C1 * 9 = 45
# 2[xxxxx] 5C1 * 9 = 45
# 3[xxxxx] わからん!
# 31[0000] = 1
# 30[xxxx] = 4C1 * 9 合わせて937

# 9999, 3,
# 0[xxx] 3C3 * 9*9*9 = 729
# [yxxx] y=8, x=3C2 * 9*9 = 8 * 243
# 9[xxx] = 3C2 * 9*9 = 243

# 94599, 3,
# 0[xxxx] 4C3 * 9*9*9 = 4 * 729
# 1[xxxx] x=4C2 * 9*9 = 6 * 81
# ...
# 8[xxxx] x=4C2 * 9*9 = 6 * 81
# 94[x]00 = 5
# 940[xx] 2C1 * 9
# 93[xxx] 3C1 * 9
str_n = input()
n = int(str_n)
k = int(input())

if k > len(str_n):
  print(0)
  exit()

head = n
while head >= 10:
  head //= 10
def choice(p, q):
  if p < q:
    return 0
  if p == q:
    return 1
  res = 1
  for i in range(q):
    res = (res * p)
    p -= 1
  for i in range(q):
    res = res // (i+1)
  return res

ans = choice(len(str_n)-1, k) * (9 ** k)
for i in range(1, head):
  ans += choice(len(str_n)-1, k-1) * (9 ** (k-1))
if k == 3:
  ans += int(str_n[2])  # 99x0000
  ans += choice(len(str_n) - 3, 1) * 9  # 990xxx
  ans += max(0, int(str_n[1])-1) * choice(len(str_n) - 2, 1) * 9  # 9[1:8]xxxx
  ans += choice(len(str_n) - 2, 2) * 9*9  # 90xxxxx
if k == 2:
  ans += int(str_n[1])
  ans += choice(len(str_n) - 2, 1) * 9
if k == 1:
  ans += int(str_n[0]) if len(str_n) > 1 else 1

print(ans)

Submission status: Wrong Answer

Solution code:
# 314159, 2,
# 0[xxxxx] 5C2 * 9*9 = 810
# 1[xxxxx] 5C1 * 9 = 45
# 2[xxxxx] 5C1 * 9 = 45
# 3[xxxxx] わからん!
# 31[0000] = 1
# 30[xxxx] = 4C1 * 9 合わせて937

# 9999, 3,
# 0[xxx] 3C3 * 9*9*9 = 729
# [yxxx] y=8, x=3C2 * 9*9 = 8 * 243
# 9[xxx] = 3C2 * 9*9 = 243

# 94599, 3,
# 0[xxxx] 4C3 * 9*9*9 = 4 * 729
# 1[xxxx] x=4C2 * 9*9 = 6 * 81
# ...
# 8[xxxx] x=4C2 * 9*9 = 6 * 81
# 94[x]00 = 5
# 940[xx] 2C1 * 9
# 93[xxx] 3C1 * 9
str_n = input()
n = int(str_n)
k = int(input())

if k > len(str_n):
  print(0)
  exit()

head = n
while head >= 10:
  head //= 10
def choice(p, q):
  if p == q:
    return 1
  res = 1
  for i in range(q):
    res = (res * p)
    p -= 1
  for i in range(q):
    res = res // (i+1)
  return res

ans = choice(len(str_n)-1, k) * (9 ** k)
for i in range(1, head):
  ans += choice(len(str_n)-1, k-1) * (9 ** (k-1))
if k == 3:
  ans += int(str_n[2])  # 99x0000
  ans += choice(len(str_n) - 3, 1) * 9  # 990xxx
  ans += (int(str_n[1])-1) * choice(len(str_n) - 2, 1) * 9  # 9[1:8]xxxx
  ans += choice(len(str_n) - 2, 2) * 9*9  # 90xxxxx
if k == 2:
  ans += int(str_n[1])
  ans += choice(len(str_n) - 2, 1) * 9
if k == 1:
  ans += int(str_n[0]) if len(str_n) > 1 else 1

print(ans)

Submission status: Wrong Answer

Solution code:
# 314159, 2,
# 0[xxxxx] 5C2 * 9*9 = 810
# 1[xxxxx] 5C1 * 9 = 45
# 2[xxxxx] 5C1 * 9 = 45
# 3[xxxxx] わからん!
# 31[0000] = 1
# 30[xxxx] = 4C1 * 9 合わせて937

# 9999, 3,
# 0[xxx] 3C3 * 9*9*9 = 729
# [yxxx] y=8, x=3C2 * 9*9 = 8 * 243
# 9[xxx] = 3C2 * 9*9 = 243

# 94599, 3,
# 0[xxxx] 4C3 * 9*9*9 = 4 * 729
# 1[xxxx] x=4C2 * 9*9 = 6 * 81
# ...
# 8[xxxx] x=4C2 * 9*9 = 6 * 81
# 94[x]00 = 5
# 940[xx] 2C1 * 9
# 93[xxx] 3C1 * 9
str_n = input()
n = int(str_n)
k = int(input())

if k > len(str_n):
  print(0)
  exit()

head = n
while head >= 10:
  head //= 10
def choice(p, q):
  if p == q:
    return 1
  res = 1
  for i in range(q):
    res = (res * p)
    p -= 1
  for i in range(q):
    res = res // (i+1)
  return res

ans = choice(len(str_n)-1, k) * (9 ** k)
for i in range(1, head):
  ans += choice(len(str_n)-1, k-1) * (9 ** (k-1))
if k == 3:
  ans += int(str_n[2])  # 99x0000
  ans += choice(len(str_n) - 3, 1) * 9  # 990xxx
  ans += (int(str_n[1])-1) * choice(len(str_n) - 2, 1) * 9  # 9[1:8]xxxx
  ans += choice(len(str_n) - 2, 2) * 9*9  # 90xxxxx
if k == 2:
  ans += int(str_n[1])
  ans += choice(len(str_n) - 2, 1) * 9
if k == 1:
  ans += int(str_n[0])

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
if N<=10**6:
  ans=0
  for i in range(1,N+1):
    a=str(i)
    if len(a)-list(a).count("0")==K:
      ans+=1
  print(ans)
  exit()
if K==1:#おけ
  ans=0
  print((len(str(N))-1)*9+int(str(N)[0]))
elif K==2:#おけ
  ans=0
  L=list(map(int,list(str(N))))
  for i in range(len(L)-1):
    ans+=(9*(int(str(N)[0])-1))
    for j in range(i+1,len(L)):
      if i==0:
        if j==1:
          ans+=int(str(N)[1])
        else:
          ans+=9
      else:
        ans+=81
  print(ans)
else:
  ans=0
  L=list(map(int,list(str(N))))
  le=len(L)
  for i in range(le-2):
    for j in range(i+1,le-1):
      for k in range(j+1,le):
        if i==0:
          ans+=81*(int(str(N)[0])-1)
          if j==1:
            ans+=9*(int(str(N)[1])-1)
            if k==2:
              ans+=int(str(N)[2])
            else:
              ans+=9
          else:
            ans+=81
        else:
          ans+=729
  print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
if N<=10**6:
  ans=0
  for i in range(1,N+1):
    a=str(i)
    if len(a)-list(a).count("0")==K:
      ans+=1
  print(ans)
  #exit()
if K==1:#おけ
  ans=0
  print((len(str(N))-1)*9+int(str(N)[0]))
elif K==2:#おけ
  ans=0
  L=list(map(int,list(str(N))))
  for i in range(len(L)-1):
    ans+=(9*(int(str(N)[0])-1))
    for j in range(i+1,len(L)):
      if i==0:
        if j==1:
          ans+=int(str(N)[1])
        else:
          ans+=9
      else:
        ans+=81
  print(ans)
else:
  ans=0
  L=list(map(int,list(str(N))))
  le=len(L)
  for i in range(le-2):
    for j in range(i+1,le-1):
      for k in range(j+1,le):
        if i==0:
          ans+=81*(int(str(N)[0])-1)
          if j==1:
            ans+=9*(int(str(N)[1])-1)
            if k==2:
              ans+=int(str(N)[2])
            else:
              ans+=9
          else:
            ans+=81
        else:
          ans+=729
  print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

for i in range(len(N)):
    for k in range(K+1):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i] != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

dp = [[[0 for k in range(K+2)] for j in range(2)] for i in range(len(N) + 1)]
dp[0][1][0] = 1

for i in range(len(N)):
    for k in range(K+1):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i] != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

dp = [[[0 for k in range(K+2)] for j in range(2)] for i in range(len(N) + 1)]
dp[0][1][0] = 1

for i in range(len(N)):
    for k in range(K+1):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i] != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*max(int(N[i])-1,0)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

print(dp[len(N)][0][K] + dp[len(N)][1][K])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

dp = [[[0 for k in range(K+2)] for j in range(2)] for i in range(len(N) + 1)]
dp[0][1][0] = 1

for i in range(len(N)):
    for k in range(K+1):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i] != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

print(dp[len(N)][0][K] + dp[len(N)][1][K])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = "@"+input()
K = int(input())

dp = [[[0 for k in range(K+2)] for j in range(2)] for i in range(len(N))]
dp[0][1][0] = 1

for i in range(len(N)-1):
    for k in range(K+1):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i+1] != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i+1])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = "@"+input()
K = int(input())

dp = [[[0 for k in range(5)] for j in range(2)] for i in range(len(N))]
dp[0][1][0] = 1

for i in range(len(N)-1):
    for k in range(4):
        dp[i+1][0][k] += dp[i][0][k]
        dp[i+1][0][k+1] += dp[i][0][k]*9

        if N[i+1] != 0:
            dp[i+1][0][k] += dp[i][1][k]
            dp[i+1][0][k+1] += dp[i][1][k]*(int(N[i+1])-1)
            dp[i+1][1][k+1] += dp[i][1][k]
        else:
            dp[i+1][1][k] += dp[i][1][k]

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