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:
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import math

def comb2(n):
    return (n*(n-1)//2)

def comb3(n):
    return ((n)*(n-1)*(n-2)//6)


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

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

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

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

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

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

nrow=input()
k = int(input())
if (k > len(nrow)):
  print('0')
elif k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))

Submission status: Wrong Answer

Solution code:

import math

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

def comb2(n):
    return (n*(n-1)//2)

def comb3(n):
    return ((n)*(n-1)*(n-2)//6)


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

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

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

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

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

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

nrow=input()
k = int(input())
if (k > len(nrow)):
  print('0')
elif k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import math

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

def comb2(n):
    return int(n*(n-1)/2)

def comb3(n):
    return int(comb2(n)*(n-2)/3)


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

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

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

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

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

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

nrow=input()
k = int(input())
if (k > len(nrow)):
  print('0')
elif k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))

Submission status: Wrong Answer

Solution code:

import math

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

def comb2(n):
    return int(n*(n-1)/2)

def comb3(n):
    return int(n*(n-1)*(n-2)/6)


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

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

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

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

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

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

nrow=input()
k = int(input())
if (k > len(nrow)):
  print('0')
elif k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
#nより小さいことが確定しているdp
#dp_0[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数
dp_0 = [[0 for i in range(k+1)] for j in range(len(n)+1)]
#nより小さいことが確定していないdp

#dp_1[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数。
dp_1 = [[0 for i in range(k+1)] for j in range(len(n)+1)]
for i in range(len(n) + 1):
    dp_0[i][0] = 1
    dp_1[i][0] = 1
for i in range(k+1):
    dp_0[0][i] = 1
    dp_1[0][i] = 1
for i in range(1,len(n)+1):
    for j in range(1,k+1):
        #0以外の数字を使う場合(使える場合)
        if j < k:
            #今回の桁が0でないことを想定
            if n[i-1] != '0':
                #0を使う場合と使わない場合両方考える
                #まずは使わない場合
                dp_0[i][j] += dp_0[i-1][j-1] * 9 + dp_1[i-1][j-1] * (int(n[i-1]) - 1)
                dp_1[i][j] += dp_1[i-1][j-1]
                #0を使う場合。この時はjが変化しない。なぜなら0を使うから
                dp_0[i][j] += dp_0[i-1][j] + dp_1[i-1][j]
                #dp_1の更新は無し。
                #なぜなら、今回の桁が0でないことを想定しているため、もうnを超えることはないから
            else:
                #今回の桁が0の場合
                #dp_1を遷移式に入れない理由は、今回の桁が0だった時は、どんな数字の選び方をしても
                #さっきの桁まででnより小さいことが確定しないものが
                #今回の桁の決め方で確定することはないから。
                dp_0[i][j] += dp_0[i-1][j] * 9
                dp_1[i][j] += dp_1[i-1][j]
        else:
            #もうkを使い切った場合
            #今回の数字は0で固定される
            dp_0[i][j] += dp_0[i-1][j] + dp_1[i-1][j]
#print(dp_0)
#print(dp_1)
print(dp_0[-1][k] + dp_1[-1][k])

Submission status: Wrong Answer

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

from math import factorial

str_n = str(N)
len_n = len(str(str_n))

def conb(n, r):
    return factorial(n)//factorial(r)//factorial(n-r)
    
def get_num(top, k_val, depth):
    if depth>len_n:
        return 0
    elif k_val>(len_n - depth + 1):
        return 0
    elif k_val==0:
        return 1
    elif top:
        if int(str_n[depth - 1])==0:
            return get_num(top, k_val, depth + 1)
        else:
            b1 = get_num(top, k_val - 1, depth + 1)
            b2 = (int(str_n[depth-1])-1) * get_num(False, k_val-1, depth+1)
            b3 = get_num(False, k_val, depth + 1)
            return b1+b2+b3
    else:
        return 9**(k_val) * conb(len_n - depth + 1, k_val)
    
    
a1 = get_num(True, K-1, 2)
a2 = (int(str_n[0])-1)*get_num(False, K-1, 2)
a3 = get_num(False, K, 2)

#print(a1, a2, a3)
print(a1+a2+a3)

Submission status: Wrong Answer

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

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

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

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


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

Submission status: Wrong Answer

Solution code:

import math

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

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

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

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

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

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

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

nrow=input()
k = int(input())
if (k > len(nrow)):
  print('0')
elif k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
def permutations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // factorial(n - r)
def combinations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
for i in range(length):
    if N[i]!="0":
        count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        count+=combinations_count(length-1-count3,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        count3+=1

        if K-count3==0:
            count+=1
            break


if count<0:
    count=0
print(count)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
def permutations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // factorial(n - r)
def combinations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
for i in range(length):
    if N[i]!=0:
        count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        count+=combinations_count(length-1-count3,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        count3+=1
        if K-count3==0:
            count+=1
            break

if count<0:
    count=0
print(count)

Submission status: Wrong Answer

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
def permutations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // factorial(n - r)
def combinations_count(n, r):
    if not n>=r>=0:
        return(0)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count2=1
count3=0
for i in range(length):
    if N[i]!=0:
        count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        count+=combinations_count(length-1-count3,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        count2*=int(N[i])
        count3+=1
        if K-count3==0:
            count+=1
            break


print(count)

Submission status: Wrong Answer

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


def C(n, r):
    if r <= 0 or n < r:
        return 0
    elif r == 1:
        return n
    elif r == 2:
        return n*(n-1) // 2
    else:
        return n*(n-1)*(n-2) // 6


def func(i, k, smaller):
    if i == len(N):
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    if smaller:
        return C(len(N) - i, k) * 9**k
    else:
        return func(i+1, k, True) + \
            func(i+1, k-1, True) * (int(N[i]) - 1) + \
            func(i+1, k-1, False)


print(func(0, K, False))

Submission status: Wrong Answer

Solution code:
import itertools as it
import math

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

keta = len(N)

ans = 0
num = "9" *K
def perm(n,k):
    return math.factorial(n)//math.factorial(n-k)
                                        
ans=0
if keta > K:
    ans += (9**K) * perm(keta-1, K)//math.factorial(K)
#print(ans)

if K>keta:
    ans = 0
elif K==1:
    ans += int(N[0])
elif K==2:
    ans += (int(N[0])-1) * 9 * (keta-1)#あたまが1小さい
    ans += int(N[1])#頭が同じ
    if keta >= 3 and int(N[1])>0:
        ans += 9 * (keta-2)
else:
    ##頭が1小さい
    ans += (int(N[0]) - 1)*(9**2)*perm(keta-1, 2)//2 
    ##頭が同じ
    if keta-2 >= 2 and int(N[1])>0:
        ans += 9**2 * perm(keta-2, 2)//2
    if int(N[1])>0:#上2桁目-1
        ans += (int(N[1])-1)*9*(keta-2)
        #上2桁目まで同じ
    if keta-3>0:
        ans += 9*(keta-3)
        #上3桁目まで同じ
    ans += int(N[2])
                    
print(ans)

Submission status: Wrong Answer

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


def C(n, r):
    if r == 0:
        return 1
    elif r == 1:
        return n
    elif r == 2:
        return n*(n-1) // 2
    else:
        return n*(n-1)*(n-2) // 6


def func(i, k, smaller):
    if i == len(N):
        if k == 0:
            return 1
        else:
            return 0

    if k == 0:
        return 1

    if smaller:
        return C(len(N) - i, k) * 9**k
    else:
        return func(i+1, k, True) + \
            func(i+1, k-1, True) * (int(N[i]) - 1) + \
            func(i+1, k-1, False)


print(func(0, K, False))

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
    if i == n-1:
        if k == 0:
            ans += 1
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
l = len(n)
ans = 0
if l >= 2 and k == 2:
  ans += 9**2*(l-1)*(l-2)//2
  ans += (int(n[0])-1)*9*(l-1)
  for i in range(1,l):
    if n[i] != "0":
      ans += int(n[i])+9*(l-i-1) 
      break
elif l >= 3 and k == 3:
  ans += 9**3*(l-1)*(l-2)*(l-3)//6
  ans += (int(n[0])-1)*9**2*(l-1)*(l-2)//2
  for i in range(1,l-1):
    if n[i] != "0":
      ans += int(n[i])*9*(l-i-1)
      ans += 9**2*(l-i-1)*(l-i-2)//2
      break
elif k == 1:
  ans += 9*(l-1)+int(n[0])
else:
  ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
l = len(n)
ans = 0
if l >= 2 and k == 2:
  ans += 9**2*(l-1)*(l-2)//2
  ans += (int(n[0])-1)*9*(l-1)
  for i in range(1,l):
    if n[i] != "0":
      ans += int(n[i])+9*(l-i-1) 
      break
elif l >= 3 and k == 3:
  ans += 9**3*(l-1)*(l-2)*(l-3)//6
  ans += (int(n[0])-1)*9**2*(l-1)*(l-2)//2
  for i in range(1,l-1):
    if n[i] != "0":
      ans += int(n[i])*9*(l-i-1)
      if l-i-2 > 0:
        ans += 9**2*(l-i-1)*(l-i-2)//2
      break
elif k == 1:
  ans += 9*(l-1)+int(n[0])
else:
  ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = 0
ans = 0
for i in range(n):
    if k > K:
        break
    x = int(S[i])
    y = n - 1 - i
    z = K - k
    if i == 0:
        ans += (x-1)*(9**(y-z))*c(y,z)
        continue
    if x == 0:
        k += 1
        continue
    if x == 1:
        if k == K:
            continue
        else:
            ans += (9**(y-z+1))*c(y,z-1)
            continue
    ans += (x-2)*(9**(y-z))*c(y,z)
    if k < K:
        ans += 9**(y-z+1)*c(y,z-1)
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools

N = input()
K = int(input())
lN = len(N)

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,2):
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f >= v[1]:
                if not0s >= v[2]:
                    ans += (int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += (int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += (int(N[0])-1)*9*9

    print(ans)

Submission status: Wrong Answer

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


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

    M = len(N)
    hd, tl = int(N[0]), N[1:]

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

Solution code:
import itertools

N = input()
K = int(input())
lN = len(N)


if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 == v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[v[1]])
            elif not0 < v[1]:
                ans += int(N[0])*9
            else:
                ans += max(0,int(N[0])-1)*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                elif not0s < v[2]:
                    ans += int(N[0])*int(N[v[1]])*9
                else:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += max(0,int(N[0])-1)*9*9

    print(ans)

Submission status: Wrong Answer

Solution code:
#500
N = int(input())
K = int(input())
string = str(N)
digit = len(string)
dp = [[[0,0] for _ in range(K+1)] for _ in range(digit+1)]

dp[0][0][0] = 1
dp[0][0][1] = 0

for i in range(digit):
    for j in range(K):
        dp[i+1][0][1] = 1
        dp[i+1][j+1][0] += dp[i][j][0]
        if string[i] == "0":
            dp[i+1][j+1][0] += dp[i][j+1][0]
        dp[i+1][j+1][1] += 9*dp[i][j][1] + dp[i][j+1][1]
        if string[i] != "0":
            dp[i+1][j+1][1] += dp[i][j+1][0] + (int(string[i])-1)*dp[i][j][0]
            
if N - 10*(digit-1) and K >= 2:
    n = dp[digit][K][1]
else:
    n = dp[digit][K][0] + dp[digit][K][1]
print(n)

Submission status: Wrong Answer

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


def solve(N, K):
    if int(N) < K:
        return 0

    if K == 0:
        return 1

    M = len(N)
    hd, tl = int(N[0]), N[1:] or 0

    res = nCk(M - 1, K) * (9 ** K)
    if hd == 0:
        return res

    res += solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

Solution code:
#500
N = int(input())
K = int(input())
string = str(N)
digit = len(string)
dp = [[[0,0] for _ in range(K+1)] for _ in range(digit+1)]

dp[0][0][0] = 1
dp[0][0][1] = 0

for i in range(digit):
    for j in range(K):
        dp[i+1][0][1] = 1
        dp[i+1][j+1][0] += dp[i][j][0]
        if string[i] == "0":
            dp[i+1][j+1][0] += dp[i][j+1][0]
        dp[i+1][j+1][1] += 9*dp[i][j][1] + dp[i][j+1][1]
        if string[i] != "0":
            dp[i+1][j+1][1] += dp[i][j+1][0] + (int(string[i])-1)*dp[i][j][0]
            
if N % 10 == 0 and K >= 2:
    n = dp[digit][K][1]
else:
    n = dp[digit][K][0] + dp[digit][K][1]
print(n)

Submission status: Wrong Answer

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


def solve(N, K):
    if N == "" and K > 0:
        return 0

    if K == 0:
        return 1

    M = len(N)
    hd, tl = int(N[0]), N[1:]

    res = solve(tl, K - 1)
    res += (hd - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))

    if M > K:
        res += nCk(M - 1, K) * (9 ** K)

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

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

def case1(x):
    return (len(x) - 1) * 9 + int(x[0])

def case2(x):
    if (len(x) < 2):
        return 0
    ret = (len(x) - 1) * (len(x) - 2) // 2 * 81
    ret += case1('9' * (len(x) - 1)) * (int(x[0]) - 1)
    for i in range(1, len(x)):
        if x[i] != 0:
            ret += case1(x[i:])
            break
    return ret

def case3(x):
    if (len(x) < 3):
        return 0
    ret = (len(x) - 1) * (len(x) - 2) * (len(x) - 3) // 6 * 729
    ret += case2('9' * (len(x) - 1)) * (int(x[0]) - 1)
    for i in range(1, len(x)):
        if x[i] != 0:
            ret += case2(x[i:])
            break
    return ret

if k == 1:
    print(case1(n))
elif k == 2:
    print(case2(n))
else:
    print(case3(n))

Submission status: Wrong Answer

Solution code:
#500
N = int(input())
K = int(input())
string = str(N)
digit = len(string)
dp = [[[0,0] for _ in range(K+1)] for _ in range(digit+1)]

dp[0][0][0] = 1
dp[0][0][1] = 0

for i in range(digit):
    for j in range(K):
        dp[i+1][0][1] = 1
        dp[i+1][j+1][0] += dp[i][j][0]
        if string[i] == "0":
            dp[i+1][j+1][0] += dp[i][j+1][0]
        dp[i+1][j+1][1] += 9*dp[i][j][1] + dp[i][j+1][1]
        if string[i] != "0":
            dp[i+1][j+1][1] += dp[i][j+1][0] + (int(string[i])-1)*dp[i][j][0]
            

n = dp[digit][K][0] + dp[digit][K][1]
print(n)

Submission status: Wrong Answer

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


def solve(N, K):
    M = len(N)
    if M < K:
        return 0

    if K == 0:
        return 1

    x = int(N[0])

    res = nCk(M - 1, K) * (9 ** K)
    if x == 0:
        return res

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

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

Solution code:
#500
N = int(input())
K = int(input())
string = str(N)
digit = len(string)
dp = [[[0,0] for _ in range(K+1)] for _ in range(digit+1)]

dp[0][0][0] = 1
dp[0][0][1] = 0

for i in range(digit):
    for j in range(K):
        dp[i+1][0][0] = 0
        dp[i+1][0][1] = 1
        dp[i+1][j+1][0] += dp[i][j][0]
        if string[i] == "0":
            dp[i+1][j+1][0] += dp[i][j+1][0]
        dp[i+1][j+1][1] += 9*dp[i][j][1] + dp[i][j+1][1]
        if string[i] != "0":
            dp[i+1][j+1][1] += dp[i][j+1][0] + (int(string[i])-1)*dp[i][j][0]
            

n = dp[digit][K][0] + dp[digit][K][1]
print(n)

Submission status: Wrong Answer

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

def solve(num_str, k, smaller):
    if k > 0 and len(num_str) == L:
        return 0
    if k == 0 or num_str == "":
        return 1

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

Submission status: Wrong Answer

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

def solve(num_str, k, smaller):
    #if k > 0 and len(num_str) == L:
    #    return 0
    if k == 0 or num_str == "":
        return 1

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

Submission status: Wrong Answer

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


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

    M = len(N)
    if M < K:
        return 0

    x = int(N[0])

    res = nCk(M - 1, K) * (9 ** K)
    if x == 0:
        return res

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

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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


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

    M = len(N)
    if M < K:
        return 0

    x = int(N[0])

    res = 0
    res += solve(N[1:], K - 1)
    res += (x - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))
    if M > K:
        res += nCk(M - 1, K) * (9 ** K)

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

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


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

    M = len(N)
    if M < K:
        return 0

    x = int(N[0])

    res = 0
    if x != 0:
        res += solve(N[1:], K - 1)
        res += (x - 1) * nCk(M - 1, K - 1) * (9 ** (K - 1))
    res += nCk(M - 1, K) * (9 ** K)

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

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


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

    M = len(N)
    if M < K:
        return 0

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

    return res


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

print(solve(N, K))

Submission status: Wrong Answer

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


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

    M = len(N)
    if M < K:
        return 0

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

    return res


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

print(solve(N, K))