Problem:


Score : 500 points

Problem Statement

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

1 \leq N < 10^{100}

1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

19

The following 19 integers satisfy the condition:

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Sample Input 2

25
2

Sample Output 2

14

The following 14 integers satisfy the condition:

11,12,13,14,15,16,17,18,19,21,22,23,24,25

Sample Input 3

314159
2

Sample Output 3

937

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300



Sample input:
100
1


Sample output:
19

Submission status: Wrong Answer

Solution code:
import math
n=input()
k=int(input())
if len(n)>=3:
    x=int(n[0]+n[1]+n[2])
if len(n)>=2:
    y=int(n[0]+n[1])
z=int(n[0])

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

# k==1のもの数える
if k==1:
    print(z*len(n)+(9-z)*(len(n)-1))

elif k==2 and len(n)>=2:
    a=0
    for i in range(1,10):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            else:
                break

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

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

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

#range(2)は場合分けの2？
for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

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

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
def dp(n, k): #0以上n以下の数で０でない数字がちょうどk個あるもの。
  if n == 0 and k == 0:
    return 1
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    fdigit = int(s[-1])
    m = int((n - fdigit)/10)
    if m >= 1 and k >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif m >=1 and k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

Submission status: Wrong Answer

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

b = len(str(n)) #桁数
'''
ans = 0

for i in range(k, b + 1):
    in0 = i - 1 #0が入る可能性のあるところの桁数
    if in0 > 0:
        #print(in0, k - 1, in0 - k + 1)
        a = math.factorial(in0) // math.factorial(k - 1) // math.factorial(in0 - k + 1)
        ans += 9 * pow(9, k - 1)
        #print(9 * pow(9, a))
        print('a', 9 * pow(9, k - 1))
    else:
        ans += pow(9, i)
        print('b', pow(9, i))

print(ans)

for i in range(n + 1, pow(10, b)):
    #print(i)
    num = str(i)
    cnt = 0
    for j in range(b):
        if num[j] == '0':
            cnt += 1
    if cnt == b - k:
        ans -= 1
        #print(i, ans)
'''

if b > k:
    a = math.factorial(b - 1) // math.factorial(k) // math.factorial(b - 1 - k)
    ans = a * pow(9, k)
else: 
    ans = 0

if k == 1:
    ans += int(str(n)[0])
elif k == 2:
    c = int(str(n)[0])
    for i in range(1, b): #2つめの1-9が入る場所
        for j in range(1, c + 1): #1つめの1-9の数字
            if j < c or i > 1:
                ans += 9
            else:
                #print(i, j, int(str(n)[i]))
                ans += int(str(n)[i])
else:
    c = [int(str(n)[i]) for i in range(b)] #桁数分離
    d = 1 #初めて0以外の数字が出てくる桁
    for i in range(1, b):
        if c[i] == 0:
            d += 1
        else:
            break
    if d < b: #n0000000とかでないとき
        ans += (c[0] - 1) * 81 * math.factorial(b - 1) // math.factorial(2) // math.factorial(b - 3) #1つめの数字がc[0]より小さい
        if b - d > 2:
            ans += 81 * math.factorial(b - d - 1) // math.factorial(2) // math.factorial(b - d - 3) #1つめの数字が一緒で2つめの数字の位置が低い場合
        ans += (c[d] - 1) * 9 * (b - d - 1) #1つめの数字が一緒で2つめの数字の位置が一緒で値が小さいとき
        #print(ans)
        #1つめと2つめの数字が一緒のとき
        for i in range(d + 1, b): #3つめの数字の位置
            for j in range(1, 10): #3つめの数字の値
                e = ['0' for _ in range(b)]
                e[0] = c[0]
                e[d] = c[d]
                e[i] = j
                f = ''
                for k in range(b):
                    f += str(e[k])
                f = int(f)
                if f <= n:
                    ans += 1






print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
def dp(n, k): #0以上n以下の数で０でない数字がちょうどk個あるもの。
  if n == 0 and k == 0:
    return 1
  else:
    n = int(n)
    s = str(n)
    digit = len(s)
    fdigit = int(s[-1])
    m = int((n - fdigit)/10)
    if m >= 1 and k >= 1:
        return int(dp(m, k-1) * fdigit + dp(m-1, k-1)* (9-fdigit) + dp(m, k))
    elif m >=1 and k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2 or k == 3:
        return 0
    else:
        return 1
if K == 0:
    answer = dp(N, K)-1
else:
    answer = dp(N, K)
print(int(answer))

Submission status: Wrong Answer

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

n_max = len(N)
ans = 0

if n_max < K:
	print(0)
	exit()


for n in range(K,n_max):
	if K == 1:
		ans += 9
	elif K == 2:
		ans += (n-1)*9*9
	elif K == 3:
		ans += (n-1)*(n-2)*9*9*9//2

if K == 1:
	ans += int(N[0])
elif K == 2:
	ans += (int(N[0])-1)*(n_max-1)*9
	ans += int(N[1]) + (n_max-2)*9
elif K == 3:
	ans += (int(N[0])-1)*(n_max-1)*(n_max-2)*9*9//2
	N_reduction = N[1:len(N)]
	n_max -= 1
	ans += (int(N_reduction[0])-1)*(n_max-1)*9
	ans += int(N_reduction[1]) + (n_max-2)*9
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()+"9";n=len(s);X=[1,0,0,0];Y=[1,0,0,0];
while n:
 n-=1;k=3
 while k:a=int(s[n]);Y[k],X[k]=(X[k]+(a-1)*X[k-1]+Y[k-1]if a else Y[k],X[k]+9*X[k-1]);k-=1
print(Y[int(input())])

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])
  if topmax==0:
    return 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=int(input())
K=int(input())

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=(dp[i][j]-1)*9+int(n[i+1])
    dp[i+1][K]+=dp[i][K]
    
    print(dp)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  if n[i] > 0:
    # n[:i] 0 {1..9}*k 0*(l-i-1-k)
    count += 9 ** k * comb(l-i-1, k)
    # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
    if k >= 1:
      count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
    else:
      break
    # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
    k -= 1
  elif i == l-1 and k == 0:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  else:
    break
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  if n[i] > 0:
    k -= 1
print(count)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  if 0 <= k <= n:
    c = 1
    for i in range(k):
      c *= n-i
      c //= i+1
    return c
  else:
    return 0

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1 and n[i] > 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  if n[i] > 0:
    k -= 1
  if k < 0:
    break
print(count)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1 and n[i] > 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  else:
    break
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  if n[i] > 0:
    k -= 1
print(count)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  else:
    break
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  k -= 1
print(count)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  print(i, count)
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  else:
    break
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  k -= 1
print(count)

Submission status: Wrong Answer

Solution code:
def comb(n, k):
  if 0 <= k <= n:
    c = 1
    for i in range(k):
      c *= n-i
      c //= i+1
    return c
  else:
    return 0

n = [int(i) for i in input()]
l = len(n)
k = int(input())
count = 0
for i in range(min(l, k+1)):
  count += 9 ** (k-i) * comb(l-i-1, k-i)
  count += 9 ** (k-i-1) * comb(l-i-1, k-i-1) * (n[i]-1)
print(count)

Submission status: Wrong Answer

Solution code:
import math
import itertools as it
import fractions as fra
N=int(input())
K=int(input())
answer=0

if K==1:
    if N>=10:
        print((int(math.log10(N))-1)*9+int(str(N)[0])+9)
    else:
        print(N)
elif K==2:
    if N>=100:
        for i in range(1,int(math.log10(N))):
            answer+=81*i
        answer+=(N//(10**int(math.log10(N))))*9*int(math.log10(N))
        print(answer)
    else:
        for i in range(1,N+1):
            if i>10:
                if i%10!=0:
                    answer+=1
        print(answer)
else:
    if N>=1000:
        for i in range(2,int(math.log10(N))):
            answer+=729*math.factorial(i)/(math.factorial(i-2)*math.factorial(2))
        answer+=N//(10**int(math.log10(N)))*81*math.factorial(int(math.log10(N))-1)/(math.factorial(int(math.log10(N))-3)*2)
        print(answer)
    else:
        for i in range(1,N+1):
            base=str(i)
            if len(base)-base.count("0")==3:
                answer+=1
        print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())

k = int(input())

keta = len(str(n))

dp = [[[0 for j in range(keta+2)] for _ in range(2)]  for i in range(keta)]

s = str(n)

#dp[何桁目か][未満フラグ 0 = 未満][ゼロ以外のの個数]

x = int(s[0])
if x == 1:
    dp[0][1][0] = 1
else:
    dp[0][1][0] += 1
    dp[0][0][0] += x - 1


for index, c in enumerate(s[1:]):
    i = index + 1
    x = int(c)
    dp[i][0][0] += 9
    for j in range(keta+1):
        dp[i][0][j] += dp[i-1][0][j]
        if x == 0:
            dp[i][1][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
        elif x:
            dp[i][0][j + 1] += dp[i - 1][1][j]
            dp[i][0][j] += dp[i - 1][1][j]
            dp[i][0][j + 1] += dp[i - 1][0][j] * 9
            dp[i][0][j + 1] += dp[i - 1][1][j] * (x - 1)
    # print(sum(dp[i][0]) + sum(dp[i][1]))




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

Submission status: Wrong Answer

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

def search(d, k, isLess):
    if k == K:
        return 1
    if d == len(N):
        return 0

    ret = search(d + 1, k, isLess or int(N[d]) > 0)

    if k < K:
        if isLess:
            ret += search(d + 1, k + 1, True) * 9
        else:
            ret += search(d + 1, k + 1, True) * (int(N[d]) - 1) + search(d + 1, k + 1, False)

    return ret

ans = search(0, 0, False)
print(max(0, ans))

Submission status: Wrong Answer

Solution code:
import math

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

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

if K>digits:
    print(0)
elif digits==1:
    print(N)
else:
    max_digits_val= int(str(N)[-digits])
    max_digits_val_2= int(str(N)[-(digits-1)])
    max_digits_val_3 = int(str(N)[-(digits-2)])
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        f1 = combinations_count(digits,K)*(9**K)
        if K==digits:
            f2 = combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
            f3 = combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        else:
            f2 = combinations_count(digits-1,K-2)*(9**(K-1))*(9-max_digits_val)
            f3 = combinations_count(digits-2,K-2)*(9**(K-1))*(9-max_digits_val_2)
        answer=f1-f2-f3
        print(answer)
    if K==3:
        f1 = combinations_count(digits,K)*(9**K)
        f2 = combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        f3 = combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        f4 = combinations_count(digits-3,K-3)*(9**(K-3))*(9-max_digits_val_3)
        answer=f1-f2-f3-f4
        print(answer)

Submission status: Wrong Answer

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

def search(d, k, isLess):
    if k == K:
        return 1
    if d == len(N):
        return 0

    ret = search(d + 1, k, isLess or int(N[d]) > 0)

    if k < K:
        if isLess:
            ret += search(d + 1, k + 1, True) * 9
        else:
            ret += search(d + 1, k + 1, True) * (int(N[d]) - 1) + search(d + 1, k + 1, False)

    return ret

ans = search(0, 0, False)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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

if K>digits:
    print(0)
elif digits==1:
    print(N)
else:
    max_digits_val= int(str(N)[-digits])
    max_digits_val_2= int(str(N)[-(digits-1)])
    max_digits_val_3 = int(str(N)[-(digits-2)])
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        f1 = combinations_count(digits,K)*(9**K)
        f2 = combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        f3 = combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        print(f1,f2,f3)
        answer=f1-f2-f3
        print(answer)
    if K==3:
        f1 = combinations_count(digits,K)*(9**K)
        f2 = combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        f3 = combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        f4 = combinations_count(digits-3,K-3)*(9**(K-3))*(9-max_digits_val_3)
        answer=f1-f2-f3-f4
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

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

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

if K>digits:
    print(0)
elif digits==1:
    print(N)
else:
    max_digits_val= int(str(N)[-digits])
    max_digits_val_2= int(str(N)[-(digits-1)])
    max_digits_val_3 = int(str(N)[-(digits-2)])
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        f1 = combinations_count(digits,K)*(9**K)
        f2 = combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        f3 = combinations_count(digits-2,K-2)*(9**(K-1))*(9-max_digits_val_2)
        print(f1,f2,f3)
        answer=f1-f2-f3
        print(answer)
    if K==3:
        f1 = combinations_count(digits,K)*(9**K)
        f2 = combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        f3 = combinations_count(digits-2,K-2)*(9**(K-1))*(9-max_digits_val_2)
        f4 = combinations_count(digits-3,K-3)*(9**(K-1))*(9-max_digits_val_3)
        answer=f1-f2-f3-f4
        print(answer)

Submission status: Wrong Answer

Solution code:
import math

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

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


if K>digits:
    print(0)
elif digits==1:
    print(N)
else:
    max_digits_val= int(str(N)[-digits])
    max_digits_val_2= int(str(N)[-(digits-1)])
    max_digits_val_3 = int(str(N)[-(digits-2)])
    if K==1:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)
        print(answer)
    if K==2:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)
        print(answer)
    if K==3:
        answer = combinations_count(digits,K)*(9**K)- combinations_count(digits-1,K-1)*(9**(K-1))*(9-max_digits_val)- combinations_count(digits-2,K-2)*(9**(K-2))*(9-max_digits_val_2)- combinations_count(digits-3,K-3)*(9**(K-3))*(9-max_digits_val_3)
        print(answer)

Submission status: Wrong Answer

Solution code:
import math
import sys

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

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

if K ==1:
    ans = 0
    l = len(str(N))
    ans += 9*(l-1)
    head = int(str(N)[0])
    ans += head
    print(ans)
elif K == 2: 
    ans = 0
    l = len(str(N))
    if l < 2 :
        print(0)
        sys.exit()
    for i in range(1,l-1):
        ans += 9*(9*i)
    
    head = int(str(N)[0])
    ans += (head-1)*(9*(l-1))
    ans += int(str(N)[1]) + (9*(l-2))
    print(ans)
elif K == 3: # right
    ans = 0
    l = len(str(N))
    if l < 3:
        print(0)
        sys.exit()
    for i in range(0,l-3):
        ans += 9*(81*combinations_count(i+2,2))
    
    head = int(str(N)[0])
    ans += (head-1)*(81*combinations_count(l-1,2))
    ans += ( (int(str(N)[1])-1) * 9  * (l-2) )  + int(str(N)[2]) + (9 * (l-3) ) 
    if l > 3 : 
        ans += (81*combinations_count(l-2,2))
    print(ans)

Submission status: Wrong Answer

Solution code:
n = input()

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

dp[0][0] = 1

for i in range(1, len(n)+1):
    dp[i][0] = dp[i-1][0]
    dp[i][1] = dp[i-1][1]*10+dp[i-1][0]*int(n[i-1])

print(dp[len(n)][0]+dp[len(n)][1])

Submission status: Wrong Answer

Solution code:
N = input()
n = [ int(x) for x in list(N)]

K = int(input())
nl = len(N)
cnt = 0

if K == 1:
    cnt += n[0]   + (nl-1) * 9
elif K == 2 and n.count(0) <= nl - 2:
    if nl == 2:
        cnt += (n[0]-1) * 9 + n[1]
    if nl > 2:
        cnt += (nl-1) * (nl-2) * 9 * 9 // 2
        cnt += (n[0]-1) * 9 * (nl-1)
        for i in range(1,nl+1):
            if n[i] > 0:
                cnt += n[i] + (nl - i -1) * 9
                break
elif K == 3 and n.count(0) <= nl - 3:
    if nl == 3:
        cnt += (n[0]-1) * 9 * 9
        cnt += (n[1]-1) * 9 + n[2]
    elif nl > 3:
        cnt += (nl-1) * (nl-2) * (nl-3) // 6 * 9 * 9 * 9
        cnt += (n[0]-1) * (nl-1) * (nl-2) //2 * 9 * 9
        for i in range(1,nl):
            if n[i] > 0:
                cnt += (nl-i-1) * (nl-i-2) // 2 * 9 * 9
                cnt += (n[i]-1) * (nl-i-1) * 9
                for j in range(i+1,nl+1):
                    if n[j] > 0:
                        cnt += (nl-j-1) * 9
                        cnt += n[j]
                        break
                break
print (cnt)

Submission status: Wrong Answer

Solution code:
N = input()
n = [ int(x) for x in list(N)]

K = int(input())
nl = len(N)
cnt = 0

if K == 1:
    cnt += (n[0] - 1)  + (nl-1) * 9
elif K == 2 and n.count(0) <= nl - 2:
    if nl == 2:
        cnt += (n[0]-1) * 9 + n[1]
    if nl > 2:
        cnt += (nl-1) * (nl-2) * 9 * 9 // 2
        cnt += (n[0]-1) * 9 * (nl-1)
        for i in range(1,nl+1):
            if n[i] > 0:
                cnt += n[i] + (nl - i -1) * 9
                break
elif K == 3 and n.count(0) <= nl - 3:
    if nl == 3:
        cnt += (n[0]-1) * 9 * 9
        cnt += (n[1]-1) * 9 + n[2]
    elif nl > 3:
        cnt += (nl-1) * (nl-2) * (nl-3) // 6 * 9 * 9 * 9
        cnt += (n[0]-1) * (nl-1) * (nl-2) //2 * 9 * 9
        for i in range(1,nl):
            if n[i] > 0:
                cnt += (nl-i-1) * (nl-i-2) // 2 * 9 * 9
                cnt += (n[i]-1) * (nl-i-1) * 9
                for j in range(i+1,nl+1):
                    if n[j] > 0:
                        cnt += (nl-j-1) * 9
                        cnt += n[j]
                        break
                break
print (cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    K=int(input())
    str_N=str(N)
    M=len(str(N))
    dp=[[[0]*2 for _ in range(K+1)] for _ in range(M+1)]
    dp[0][0][0]=1
    for keta in range(M):
        dp[keta+1][0][1]=dp[keta][0][0]+dp[keta][0][1]
        for k in range(K):
            dp[keta+1][k+1][1]=dp[keta][k][0]*(int(str_N[keta])-1)+dp[keta][k][1]*9+dp[keta][k+1][1]
            if int(str_N[keta])==0:
                dp[keta+1][k+1][0]=dp[keta][k+1][0]
            else:
                dp[keta+1][k+1][0]=dp[keta][k][0]
                dp[keta+1][k+1][1]+=dp[keta][k+1][0]
    ans=sum(dp[M][K])
    print(max(ans,0))
                

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
out = []
N = int(input())
K = int(input())
for n in range(1,10):
    fun = lambda t: str(t).count(str(n)) == K
    fil = filter(fun, range(1,N))
    [out.append(o) for o in fil]
print(out)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    K=int(input())
    str_N=str(N)
    M=len(str(N))
    dp=[[[0]*2 for _ in range(K+1)] for _ in range(M+1)]
    dp[0][0][0]=1
    for keta in range(M):
        dp[keta+1][0][1]=dp[keta][0][0]+dp[keta][0][1]
        for k in range(K):
            dp[keta+1][k+1][1]=dp[keta][k][0]*(int(str_N[keta])-1)+dp[keta][k][1]*9+dp[keta][k+1][1]
            if int(str_N[keta])==0:
                dp[keta+1][k+1][0]=dp[keta][k+1][0]
            else:
                dp[keta+1][k+1][0]=dp[keta][k][0]
                dp[keta+1][k+1][1]+=dp[keta][k+1][0]
    print(sum(dp[M][K]))
                

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 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(int(n[0]))*(a-1)*9+zero(1)*(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(int(n[0]))*81*(combi(a-1,2))+9*mi(int(n[1]))+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 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(int(n[0]))*(a-1)*9+zero(1)*(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(int(n[0]))*81*(combi(a-1,2))+9*mi(int(n[1]))+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                print(b,bs,c,cs)
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 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+zero(1)*(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(0)*81*(combi(a-1,2))+9*mi(1)+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 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+zero(1)*(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(0)*81*(combi(a-1,2))+9*mi(1)+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                print(b,bs,c,cs)
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
dp1=[[0 for _ in range(4)] for _ in range(101)]
dp2=[[0 for _ in range(4)] for _ in range(101)]
dp1[0][0]=1
for i in range(1, 101):
    dp1[i][0]=1
    for j in range(1, 4):
        dp1[i][j]=dp1[i-1][j-1]*9+dp1[i-1][j]
dp2[0][1]=1
for i in range(1, 101):
    dp2[i][1]=dp1[i][1]+1
    dp2[i][2]=dp1[i][2]
    dp2[i][3]=dp1[i][3]
ans=0
i=len(str(N))-1
cnt=0
while i>=0:
    k=int(str(N)[cnt])
    if k==0:
        i-=1
        continue
    ans+=dp2[i][K-cnt]
    cnt+=1
    if K-cnt<0:
        break
    ans+=dp1[i][K-cnt]*(k-1)
    i-=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
dp1=[[0 for _ in range(4)] for _ in range(101)]
dp2=[[0 for _ in range(4)] for _ in range(101)]
dp1[0][0]=1
for i in range(1, 101):
    dp1[i][0]=1
    for j in range(1, 4):
        dp1[i][j]=dp1[i-1][j-1]*9+dp1[i-1][j]
dp2[0][1]=1
for i in range(1, 101):
    dp2[i][1]=dp1[i][1]+1
    dp2[i][2]=dp1[i][2]
    dp2[i][3]=dp1[i][3]
ans=0
i=len(str(N))-1
cnt=0
while i>=0:
    ans+=dp2[i][K-cnt]
    k=int(str(N)[cnt])
    cnt+=1
    if K-cnt<0:
        break
    ans+=dp1[i][K-cnt]*(k-1)
    i-=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
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)