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:
N=9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
K=3
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if int(n[i])==0:
        return 0
    else:
        return int(n[i])-1


if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:ans+=mi(0)*(a-1)*9+(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(0)*81*(combi(a-1,2))+9*mi(1)+int(n[2])
    else:ans+=mi(0)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*mi(1)+int(n[2])+(a-3)*9

print(ans)

Submission status: Wrong Answer

Solution code:
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    z = N.count('0')
    o = N.count('1')
    f = 0
    if z + o == L:
      f = 1
    if f == 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(N[1:]),K - 1)
    else:
      if len(str(int(N[1:]))) != 1:
        return ans + top(str(int(N[1:])),K - 1)
      else:
        return ans

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

print(int(top(N,K)))

Submission status: Wrong Answer

Solution code:
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
    return ans + top(str(N[1:]),K - 1)

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

print(int(top(N,K)))

Submission status: Wrong Answer

Solution code:
import itertools

def read():
    N = str(input().strip())
    K = int(input().strip())
    return N, K

def solve(N, K):
    L = len(N)
    D = [int(N[i]) for i in range(L)]
    dp0 = [[0 for k in range(K+1)] for i in range(L+1)]
    dp1 = [[0 for k in range(K+1)] for i in range(L+1)]
    
    dp0[0][0] = 1
    for i in range(L):
        for k in range(K+1):
            if k+1 <= K and D[i] > 0:
                dp0[i+1][k+1] += dp0[i][k]
                for d in range(1, D[i]):
                    dp1[i+1][k+1] += dp0[i][k]
            dp1[i+1][k] += dp0[i][k]
            if k+1 <= K:
                for d in range(1, 10):
                    dp1[i+1][k+1] += dp1[i][k]
            dp1[i+1][k] += dp1[i][k]
    return dp0[L][K] + dp1[L][K]


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

Submission status: Wrong Answer

Solution code:
import itertools

def read():
    N = str(input().strip())
    K = int(input().strip())
    return N, K

def solve(N, K):
    L = len(N)
    D = [int(N[i]) for i in range(L)]
    dp0 = [[0 for k in range(K+1)] for i in range(L+1)]
    dp1 = [[0 for k in range(K+1)] for i in range(L+1)]
    
    dp0[0][0] = 1
    for i in range(L):
        for k in range(K+1):
            if k+1 <= K:
                dp0[i+1][k+1] += dp0[i][k]
                for d in range(1, D[i]):
                    dp1[i+1][k+1] += dp0[i][k]
            dp1[i+1][k] += dp0[i][k]
            if k+1 <= K:
                for d in range(1, 10):
                    dp1[i+1][k+1] += dp1[i][k]
            dp1[i+1][k] += dp1[i][k]
    return dp0[L][K] + dp1[L][K]


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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N=int(input())
K=int(input())

lN=len(str(N))

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

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

for i in range(lN):
    num=int(str(N)[i])
    for j in range(K+1):
        if num==0:
            dp[i+1][0][j] = dp[i][0][j]
        else:
            if j==0:
                dp[i+1][0][j] = 0
            else:
                dp[i+1][0][j] = dp[i][0][j-1]
        
        if j==0:
            dp[i+1][1][j] = 1
        else:
            if num==0:
                dp[i+1][1][j] = dp[i][1][j-1]*9 + dp[i][1][j]*1 + dp[i][0][j-1]*(num-1)
            else:
                dp[i+1][1][j] = dp[i][1][j-1]*9 + dp[i][1][j]*1 + dp[i][0][j-1]*(num-1) + dp[i][0][j]*1

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

Submission status: Wrong Answer

Solution code:
x = int(input())
X = [int(i) for i in str(x)]
y = int(input())
dp = [[[0] * 2 for i in range(4)] for j in range(len(str(x))+1)]
dp[0][0][0] = 1

for i in range(len(str(x))):
  for j in range(4):
    for m in range(2):
      for n in range(10):
        nj = j + 1 if n != 0 else j
        if nj == 4: continue
        nm = m        
        if X[i] > n and m == 0:
          nm = 1
        if X[i] < n and m == 0:
          continue
        dp[i+1][nj][nm] += dp[i][j][m]
print(len(X))
print(dp)
print(dp[len(X)][y][0]+dp[len(X)][y][1])
print("finish")

Submission status: Wrong Answer

Solution code:
N=input()
K=int(input())
dp_0 = [[0]*(len(N)) for i in range(K+1)]
dp_1 = [[0]*(len(N)) for i in range(K+1)]
dp_0[0][0]=1
dp_0[1][0]=int(N[0])-1
dp_1[1][0]=1
for i in range(len(N)-1):
    for j in range(K+1):
        if j==K:
            dp_0[j][i+1] += dp_0[j][i]
        elif j==0:
            dp_0[j][i+1] =dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        else:
            dp_0[j][i+1] += dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        if j != K and N[i] != '0':
            dp_0[j+1][i+1] += (int(N[i+1])-1)*dp_1[j][i]
            dp_0[j][i+1] += dp_1[j][i]
            dp_1[j+1][i+1] = dp_1[j][i]
        elif N[i] =='0':
            dp_1[j][i+1] = dp_1[j][i]
        else:

            dp_0[j][i+1] += dp_1[j][i]
print(dp_0[K][len(N)-1]+dp_1[K][len(N)-1])

Submission status: Wrong Answer

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

dp = [0] * (k+1)
dp[0] = 0
limit_non_zero = 0


for l in n:
  limit_non_zero += (l != 0)
  for i in range(k, 0, -1):
    dp[i] = dp[i-1] * 9 + dp[i]
    if limit_non_zero == i and l > 0:
      dp[i] += l - 1
    elif limit_non_zero -1 == i:
      dp[i] += 1
  dp[0] = 1

print(dp[-1]+ (limit_non_zero == k))

Submission status: Wrong Answer

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

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

for d in range(int(N[0])+1):
    DP[0][d<int(N[0])][d!=0] += 1

for i in range(len(N)-1):
    for j in range(2):
        for k in range(K+1):
            for d in range(10 if j else int(N[i+1])+1):
                if k+(d!=0) <= K:
                    DP[i+1][j|(d<int(N[i]))][k+(d!=0)] += DP[i][j][k]

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

Submission status: Wrong Answer

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

n = len(s)

dp = [[[0] * 2 for _ in range(4)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni = i+1; nj = j; nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500)


def calc(N, K):
    if len(N) < K or K <= 0:
        return 0
    tmp = 9 - int(N[0])
    for i in range(K-1):
        tmp *= 9 * (len(N) - 1 - i)
    for i in range(K-1):
        tmp //= (i+1)
    return tmp + calc(N[1:], K-1)


def main():
    N = input()
    K = int(input())
    if len(N) < K:
        print(0)
        return
    ans = 1
    for i in range(K):
        ans *= 9 * (len(N) - i)
    for i in range(K):
        ans //= (i+1)
    ans -= calc(N, K)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

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

def count(num_str,k):
    digits = len(num_str)
    if digits == 0:
        return 0
    else:
        if k == 0:
            # print(num_str,1)
            return 1
        if num_str[0] == '0':
            # print(num_str,count(num_str[1:],k-1))
            return count(num_str[1:],k-1)
        else:
            if digits == 1 and k == 1:
                # print(num_str,int(num_str))
                return int(num_str)
            elif digits == 1 and k > 1:
                # print(num_str,0)
                return 0
            if digits >= k+1:
                count_0 = combinations_count(digits-1,k)*(9**k)
            else:
                count_0 = 0
            count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
            # print(num_str,count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1))
        return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(n),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 or n<0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())
length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if K-count3 >=1:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        if K-count3-1 >=0: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
        #count+=int(N[i])
        break
print(count)

Submission status: Wrong Answer

Solution code:
import math

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

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

def count(num_str,k):
    digits = len(num_str)
    if digits == 0:
        return 0
    else:
        if k == 0:
            print(num_str,1)
            return 1
        if num_str[0] == '0':
            print(num_str,count(num_str[1:],k-1))
            return count(num_str[1:],k-1)
        else:
            if digits == 1 and k == 1:
                print(num_str,int(num_str))
                return int(num_str)
            elif digits == 1 and k > 1:
                print(num_str,0)
                return 0
            if digits >= k+1:
                count_0 = combinations_count(digits-1,k)*(9**k)
            else:
                count_0 = 0
            count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
            print(num_str,count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1))
        return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(n),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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())
length=len(str(N))
if length<K:
    print(0)
    exit()

count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3 >=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1 >=0: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
        #count+=int(N[i])
        break
    if i==length-1:
        count+=int(N[i])
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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3 >=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1 >=0: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
        count+=int(N[i])
        break

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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3 >=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1 >=0: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 i==length-1:
        count+=int(N[i])
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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

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

    if K-count3==0:
        count+=1
        break
    if i==length-1:
        count+=int(N[i])




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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3 >=1:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1 >=1: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 i==length-1:
        count+=int(N[i])




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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3 +1>=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1 +1>=0: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 i==length-1:
        count+=int(N[i])




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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3>=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1>=0: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 i==length-1:
        #if K-count3>0:
            count+=int(N[i])
        #if K-count3==0:
        #    count+=1



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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3>=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1>=0: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 i==length-1:
        if K-count3>0:
            count+=int(N[i])
        #if K-count3==0:
        #    count+=1



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

Submission status: Wrong Answer

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

Nstr = str(N)

l = len(Nstr)

DP = [[[0]*2 for j in range(K+1)] for i in range(l+1)]

DP[0][0][1] = 1

for i in range(l):
    for j in range(K+1):
        if int(Nstr[i])!=0:
            DP[i+1][j][0] += DP[i][j][1] + DP[i][j][0] 
        else:
            DP[i+1][j][0] += DP[i][j][0]
        if j>0:
            DP[i+1][j][0] += (int(Nstr[i])-1)*DP[i][j-1][1] + 9*DP[i][j-1][0] 
            if int(Nstr[i])!=0:
                DP[i+1][j][1] += DP[i][j-1][1]
        if int(Nstr[i])==0:
            DP[i+1][j][1] += DP[i][j][1]

print(DP[l][K][0] + DP[l][K][1])

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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

length=len(str(N))
count=0
count3=0
flag=1
for i in range(length):
    if N[i]!="0":
        if i<length-1:
            if K-count3>=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1>=0: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 i==length-1:
        if K-count3>0:
            count+=int(N[i])
        if K-count3==0:
            count+=1



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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

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



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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    else:
        return factorial(n) // (factorial(n - r) * factorial(r))
N=input()
K=int(input())

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



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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    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":
        if i<length-1:
            if K-count3>=0:count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
            if K-count3-1>=0:count+=combinations_count(length-1-count3,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        else:
            if K-count3>0:
                count+=int(N[i])
            if K-count3==0:
                count+=1
        count3+=1

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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    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":
        if i<length-1 and combinations_count(length-1-count3,K-count3):
            count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        if i<length-1 and combinations_count(length-1-count3,K-count3-1) and (int(N[i])-1):
            count+=combinations_count(length-1-count3,K-count3-1)*(9**(K-1-count3))*(int(N[i])-1)
        count3+=1
        if K-count3==0:
            if i<length-1:
                count+=1
            else:
                count+=int(N[i])
            break
if count<0:
    count=0
print(count)

Submission status: Wrong Answer

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

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

dp[0][0][0]=1
for i in range(m):
  keta=int(n[i])
  for j in range(3):
    dp[i+1][j][0]+=dp[i][j][0]*(keta==0)
    dp[i+1][j+1][0]+=dp[i][j][0]*(keta!=0)
    dp[i+1][j][1]+=dp[i][j][0]*(keta>0)+dp[i][j][1]
    dp[i+1][j+1][1]+=dp[i][j][0]*max(keta-1,0)+dp[i][j][1]*9
                      
print(dp[m][k][0]+dp[m][k][1])

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 or n<=0:
        return(0)
    elif r==0:
        return(1)
    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":
        if combinations_count(length-1-count3,K-count3):
            count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        if combinations_count(length-1-count3,K-count3-1) and (int(N[i])-1):
            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:
#!python3

from math import factorial

iim = lambda: map(int, input().rstrip().split())

def cmb(a, b):
    c = a - b
    if c < b:
        b = c
    if b == 0: return 1

    ans = 1
    for i in range(b):
        ans *= a - i

    return ans // factorial(b)

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

    n10 = 10 ** (K-1)
    if N < n10:
        return 0

    n10 *= 10
    k1 = K - 1
    n9 = 9 ** K
    n91 = 9 ** k1

    ans = 0
    a = n10
    i = 0
    while a < N:
        a *= 10; i += 1
    a //= 10; i -= 1
    if i > 0:
        ans = cmb(i+K, K) * n9
        #print(f"{i+K}C{K}", ans)

    n, b = divmod(N, a)
    if n > 1:
        ans += (n - 1) * cnt(a-1, K - 1)
    ans += cnt(b, K - 1)


    return ans

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

    print(cnt(N, K))

if __name__ == "__main__":
    resolve()

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":
        if combinations_count(length-1-count3,K-count3):
            count+=combinations_count(length-1-count3,K-count3)*(9**(K-count3))
        if combinations_count(length-1-count3,K-count3-1) and (int(N[i])-1):
            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:
def f(s,t,k):
 n=len(s)
 if k>n: return 0
 a=max(t,int(s[0]))
 z=0
 if k==1:z=a+(n-1)*9
 elif a==0:z=f(s[1:],t,k)
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))

Submission status: Wrong Answer

Solution code:
n=input()
k=int(input())
lenn=len(n)
dp=[[[0]*2 for i in range(k+1)] for j in range(lenn)]
dp[0][1][1]+=int(n[0])-1
dp[0][0][1]+=1
dp[0][1][0]+=1
for i in range(1,lenn):
  keta=int(n[i])
  for j in range(k):
    dp[i][j+1][1]+=dp[i-1][j][1]*9
    dp[i][j][1]+=dp[i-1][j][1]
    dp[i][j+1][1]+=dp[i-1][j][0]*(keta-1)
    if keta>0:
      dp[i][j+1][0]+=dp[i-1][j][0]
      dp[i][j][1]+=dp[i-1][j][0]
    else:
      dp[i][j][0]+=dp[i-1][j][0]
  dp[i][k][1]+=dp[i-1][k][1]
  if keta>0:
    dp[i][k][1]+=dp[i-1][k][0]
  else:
    dp[i][k][0]+=dp[i-1][k][0]
print(dp[lenn-1][k][1]+dp[lenn-1][k][0])

Submission status: Wrong Answer

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

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

dp[0][0][0]=1
for i in range(m):
  keta=int(n[i])
  for j in range(3):
    dp[i+1][j+1][1]+=9*dp[i][j][1]
    dp[i+1][j][1]+=dp[i][j][1]
    if keta>0:
      dp[i+1][j+1][1]+=dp[i][j][0]*(keta-1)
      dp[i+1][j][1]+=dp[i][j][0]
      dp[i+1][j+1][1]+=dp[i][j][0]
    else:
      dp[i+1][j][0]+=dp[i][j][0]
  dp[i+1][3][1]+=dp[i][3][1]
  dp[i+1][3][keta>0]+=dp[i][3][0]
print(dp[m][k][0]+dp[m][k][1])

Submission status: Wrong Answer

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

L=len(str(N))
ans=0
if L-1>=K:
    ans=cmb(L-1,K)*(9**K)
#print(ans)

List=[]
for i in range(1,10):
    List.append(i*10**(L-1))
#print(List)

import sys
if K==1:
    for i in List:
        if i<=N:
            ans+=1
        else:
            print(ans)
            sys.exit()
    print(ans)
elif K==2:
    for i in List:
        for j in range(L-1):
            for k in range(1,10):
                T=i+k*10**j
                if T<=N:
                    ans+=1
                else:
                    print(ans)
                    sys.exit()
    print(ans)
elif K==3:
    for i in List:
        for j in range(L-1):
            for k in range(j+1,L-1):
                if i+9*10**j+9*10**k<=N:
                    ans+=81
                else:
                    for l in range(1,10):
                        for m in range(1,10):
                            T=i+m*10**j+l*10**k
                            if T<=N:
                                ans+=1
                            else:
                                print(ans)
                                sys.exit()
    print(ans)
else:
    print(0)