Problem:


Score : 500 points

Problem Statement

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

Constraints

1 \leq N < 10^{100}

1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

19

The following 19 integers satisfy the condition:

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

Sample Input 2

25
2

Sample Output 2

14

The following 14 integers satisfy the condition:

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

Sample Input 3

314159
2

Sample Output 3

937

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300



Sample input:
100
1


Sample output:
19

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

S=input()
N=int(S)
L = len(S)
K=II()
res = 0
if N <= 100000:
    for i in range(N+1):
        st = str(i)
        res += (len(st) - st.count("0")) == K
else:
    tp = int(S[:3])
    for i in range(tp+1):
        st = str(i)
        nonzeros = len(st)-st.count("0")
        # if nonzeros <= K:
        #     print("i{} non{}".format(i, nonzeros))
        if nonzeros > K:
            continue
        elif nonzeros == K:
            res += 1
            continue
        elif K-nonzeros == 1:
            res += (L-3)*9
        elif K-nonzeros == 2:
            res += 81*((L-3)*(L-4)//2)
        elif K-nonzeros == 3:
            res += 729*((L-3)*(L-4)*(L-5)//6)

print(res)

Submission status: Wrong Answer

Solution code:
n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())

#割り算のやーつ
MOD = 1000000007

# 二項係数関連.
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0
# 最大桁数-1の桁の数について.
if(n_digit > k):
    ans += com.calc_COM(n_digit-1, k) * (9 ** k)
# 最大桁の桁の数について.
n_top = int(n_str[0])
if(k-1 <= 0):
    # これで終わりだから自由
    ans += n_top
else:
    # 最大桁がn_top未満なら残りは自由
    ans += com.calc_COM(n_digit-1, k-1) * (9 ** (k-1)) * (n_top - 1)
    # 最大桁がn_topなら、残りは自由じゃない……
    n_sec = 0
    count = 1
    for nc in n_str[1:]:
        n_sec = int(nc)
        if(n_sec > 0):
            break
        count += 1
    if((n_digit - count) >= k-1):
        # まだ可能性がある！
        left = n_digit - count
        # 次に来る1以上の数字がcountよりも先だったら二つとも自由
        ans += com.calc_COM(left-1, k-1) * (9 ** (k-1))
        # 次の1以上の数字がcountの位置に来る.
        if(k-2 <= 0):
            ans += n_sec # これで終わりだからその下は考えないでいいのじゃ.
        else:
            # 次に来る1以上の数字がcountで、n_sec未満なら残りは自由
            ans += (left-1) * 9 * (n_sec - 1)
            # 次に来る1以上の数字がcountで、n_secと同じなら、残りは自由じゃない……
            sec_count = 1
            n_third = 0
            for nc in n_str[count:]:
                n_third = int(nc)
                if(n_sec > 0):
                    break
                sec_count += 1
            if(left - sec_count >= k - 2):
                # まだ可能性がある！
                left_sec = left - sec_count
                # 最後の数字がcount+sec_countよりも下の位置
                ans += (left_sec-1) * 9
                # 最後の数字がcount+sec_countの位置
                ans += n_third

print(ans)

Submission status: Wrong Answer

Solution code:
n = list(input())
k = int(input())
ln = len(n)

if ln == 1:
    if k > 1:
        print(0)
    else:
        print(n)
elif ln == 2:
    if k > 2:
        print(0)
    elif k == 2:
        print((int(n[0])-1) * 9 + int(n[1]))
    else:
        print(9+int(n[0]))
else:
    if k == 1:
        print(9*(ln-1)+int(n[0]))
    elif k == 2:
        print((((ln-1)*(ln-2))//2)*81+(int(n[0])-1)*9*(ln-1)+9*(ln-2)+int(n[1]))
    else:
        print((((ln-1)*(ln-2)*(ln-3))//6)*(9**3)+(int(n[0])-1)*(((ln-1)*(ln-2))//2)*81+(((ln-2)*(ln-3))//2)*81+(int(n[1])-1)*9*(ln-2)+9*(ln-3)+int(n[2]))

Submission status: Wrong Answer

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

# 桁数調べる
# tmp = N
# digit = 1
# while tmp >= 10:
#     tmp //= 10
#     digit += 1
# print(digit)

if K > len(str(N)):
    print(0)
    exit()

if K == 1:
    N = str(N)
    ans = (len(N)-1) * (len(N)-2) * 9
    ans += int(N[0])
    print(ans)
    # N = str(N)
    # ans = 9*(len(N)-1)+int(N[0])
    # print(ans)
elif K == 2:
    N = str(N)
    # 最上位を避けた
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位ともう一つ
    ans += (int(N[0])-1) * (len(N)-1) * 9
    # 最上位の桁のみを選ぶ場合
    ans += 1 * int(N[1])
    # 最上位+何か
    ans += 1 * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    # 最上位を避けた選び方
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他
    ans += int(N[0]) * int(N[1]) * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
N = input()
n = int(N)
l = len(N)
k = int(input())
ans = 0
tmp = 0
def c(x,y):
  z = 1
  for w in range(y):
    z *= x - w
    z /= y - w
  return z
#print(c(5,2))
for i in range(l):
  for d in range(10):
    if d < int(N[i]):
      if d == 0:
        now = c(l-1-i,k-tmp) * 9**(k-tmp)
        ans += now
        #print(i,d,now,l-1-i,k-tmp)
      elif k - tmp - 1 >= 0:
        now =  c(l-1-i,k-tmp-1) * 9**(k-tmp-1)
        ans += now
        #print(i,d,now,l-1-i,k-tmp-1)
    elif d == int(N[i]):
      tmp += 1
  if tmp == k:
    ans += 1
    print(int(ans))
    break

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

S=input()
N=int(S)
L = len(S)
K=II()
res = 0
if N <= 10000:
    for i in range(N+1):
        st = str(i)
        res += (len(st) - st.count("0")) == K
else:
    tp = int(S[:3])
    for i in range(tp+1):
        st = str(i)
        nonzeros = len(st)-st.count("0")
        # if nonzeros <= K:
        #     print("i{} non{}".format(i, nonzeros))
        if nonzeros > K:
            continue
        elif nonzeros == K:
            res += 1
            continue
        elif K-nonzeros == 1:
            res += (L-3)*9
        elif K-nonzeros == 2:
            res += 81*((L-3)*(L-4)//2)
        elif K-nonzeros == 3:
            res += 729*((L-3)*(L-4)*(L-5)//6)

print(res)

Submission status: Wrong Answer

Solution code:
N=input()
K=input()
a=1
ans=0
while (a<=int(N)):
  a1=str(a).strip("0")
  L=len(str(a1))
  a=int(a)+1
  if(int(L)==int(K)):
    ans=ans+1
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
l = len(str(N))
cnt = 0
if K > l:
    cnt = 0
elif K == 1:
    cnt = 9 * (l - 1) + N // (10 ** (l - 1))
elif K == 2:
    a = int(str(N)[0])
    b = int(str(N)[1])
    cnt = 81 * ((l - 1) * (l - 2) // 2) + 9 * a * (l - 2) + (a - 1) * 9 + b
else:
    a = int(str(N)[0])
    b = int(str(N)[1])
    c = int(str(N)[2])
    cnt = 9 ** 3 * ((l - 1) * (l - 2) * (l - 3) // 6) + a * 9 * 9 * ((l - 2) * (l - 3) // 2) + (a - 1) * 9 * 9 * (l - 2) + (b - 1) * 9 * (l - 2) + 9 * (l - 3) + c

print(cnt)

Submission status: Wrong Answer

Solution code:
n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())

#割り算のやーつ
MOD = 1000000007

# 二項係数関連.
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0
# 最大桁数-1の桁の数について.
if(n_digit > k):
    ans += com.calc_COM(n_digit-1, k) * (9 ** k)
# 最大桁の桁の数について.
n_top = int(n_str[0])
if(k-1 <= 0):
    # これで終わりだから自由
    print(ans)
    ans += n_top
else:
    # 最大桁がn_top未満なら残りは自由
    ans += com.calc_COM(n_digit-1, k-1) * (9 ** (k-1)) * (n_top - 1)
    # 最大桁がn_topなら、残りは自由じゃない……
    n_sec = 0
    count = 1
    for nc in n_str[1:]:
        n_sec = int(nc)
        if(n_sec > 0):
            break
        count += 1
    if((n_digit - count) >= k-1):
        # まだ可能性がある！
        left = n_digit - count
        # 次に来る1以上の数字がcountよりも先だったら二つとも自由
        ans += com.calc_COM(left-1, k-1) * (9 ** (k-1))
        # 次の1以上の数字がcountの位置に来る.
        if(k-2 <= 0):
            ans += n_sec # これで終わりだからその下は考えないでいいのじゃ.
        else:
            # 次に来る1以上の数字がcountで、n_sec未満なら残りは自由
            ans += (left-1) * 9 * (n_sec - 1)
            # 次に来る1以上の数字がcountで、n_secと同じなら、残りは自由じゃない……
            sec_count = 1
            n_third = 0
            for nc in n_str[count:]:
                n_third = int(nc)
                if(n_sec > 0):
                    break
                sec_count += 1
            if(left - sec_count >= k - 2):
                # まだ可能性がある！
                left_sec = left - sec_count
                # 最後の数字がcount+sec_countよりも下の位置
                ans += (left_sec-1) * 9
                # 最後の数字がcount+sec_countの位置
                ans += n_third

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=list(input())
N=len(n)
k=int(input())
dp=[[0 for i in range(len(n))] for j in range(k)]
ans=0
x=int(n[0])
if N<k:
  print(0)
  sys.exit()

if k==1:
  ans+=(N-1)*9
  ans+=x
  print(ans)
  sys.exit()

elif k==2:
  ans+=(N-1)*(N-2)*81//2
  ans+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans+=(N2-1)*9
  ans+=x
  print(ans)
  sys.exit()

else:
  ans+=(N-1)*(N-2)*(N-3)*729//6
  ans+=(x-1)*(N-1)*(N-2)*81//2
  n=n[1:N+1]
  N=len(n)
  x=int(n[0])
  ans2=0
  ans2+=(N-1)*(N-2)*81//2
  ans2+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans2+=(N2-1)*9
  ans2+=x
  ans+=ans2
  print(ans)
  sys.exit()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
INF = float("inf")

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

len_n = len(str(n))

base = [[0]*4 for _ in range(100)]
for i in range(4):
    base[i][0] = 0

for i in range(100):
    base[i][0] = 1
for i in range(1, 100):
    base[i][1] = 9 * i
for i in range(2, 100):
    base[i][2] = 9 * 9 * i*(i-1)//2
for i in range(3, 100):
    base[i][3] = 9 * 9 * 9 * i * (i - 1) * (i-2) // 6

ans = 0
len_n = len(str(n))
n_str = str(n)

for i in range(len(n_str)):
    if int(n_str[i]) > 0:
        ans += (int(n_str[i])-1)*base[len_n-1][k-1] + base[len_n-1][k]
        # print(ans)
        k -= 1
    len_n -= 1
    if k == 0:
        break

print(ans+1)

Submission status: Wrong Answer

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


if int(n)<1000:
    c=0
    for i in range(1,int(n)+1):
       if len(str(i))-str(i).count("0")==k:
           c+=1
           
else:
    n_l=len(n)
    c=0
    if k==1:
        c=int(n[0])+9*(n_l-1)
    elif k==2:
        for i in range(2,n_l):
            c+=9*9*(i-1)
        c+=(int(n[0])-1)*9*(n_l-1)
        
        for i in range(1,n_l):
            if int(n[i])>0:
                c+=int(n[i])+(n_l-i-1)*9
                break

    else:
        for i in range(3,n_l):
            c+=9**3*((i-1)*(i-2)/2)
            
        c+=(int(n[0])-1)*(n_l*(n_l-1)/2)
        
        flag_i=False
        flag_j=False
        for i in range(1,n_l):
            if int(n[i])>0:
                flag_i=True
                for j in range(i+1,n_l):
                    if int(n[j])>0:
                        flag_j=True
                        break
            if flag_i:
                break
        if flag_i:
            c+=(int(n[i])-1)*9*(n_l-i-1)
            if flag_j:
                c+=(int(n[j])-1)+9*(n_l-j-1)
                c+=1
                
print(int(c))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
tmpn=int(str(n)[:k]+("0"*(len(str(n))-k)))
# print(tmpn)
if k==2 and n<11:
    print(0)
    quit()
if k==3 and n<111:
    print(0)
    quit()
nonzero=[0]*3
cnt=0
for i in range(keta):
    if str(n)[i]!=0:
        nonzero[cnt]=int(str(n)[i])
        cnt+=1
    if cnt==k:
        break
# print(nonzero)
    

ans=0
def combinations_count(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if k==1:
    ans+=int(str(n)[0])
    ans+=(keta-1)*9
if k==2:
    ans+=nonzero[1]+(int(str(n)[0])-1)*9
    ans+=int(str(n)[0])*(keta-2)*9
    ans+=combinations_count(keta-1,k)*81
if k==3:
    ans+=nonzero[2]+(nonzero[1]-1)*9+(int(str(n)[0])-1)*81
    ans+=int(str(n)[0])*nonzero[1]*(keta-k)*9
    ans+=int(str(n)[0])*combinations_count(keta-2,2)*81
    ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

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

l = len(n)

ans = 0

# n-1桁からKこ取る
tmp = 1
for i in range(1, k+1):
    tmp = tmp*9*(l-i)
for i in range(1, k+1):
    tmp = tmp // i
ans += tmp

# 最上位から1つ（最上位の数以外）とる。
tmp = n[0]-1
for i in range(1, k):
    tmp = tmp*9*(l-i)
for i in range(1, k):
    tmp = tmp // i
ans += tmp

# 最上位からその数をとる。
tmp = 0
if k == 3:
    sm = sum(n[2:])
    for i in range(1, l):
        aaaa = (n[i]-1) * 9 * (l-i-1)
        aaaa += 1 * sm
        tmp += aaaa
        sm -= n[i]
elif k == 2:
    sm = sum(n[2:])
    for i in range(1, l):
        if n[i] != 0:
            tmp += n[i] + 9*(l-i-1)
            break
else:
    tmp += 1

ans += tmp

print(ans)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
def Anger(n, k):
  d = int(n[0])
  if len(n) < k:
    return 0
  else:
    if k == 1:
      S = d + 9 * (len(n) - 1)
      return S
    else:
      if d == 0:
        return Anger(n[1:], k)
      else:
        S = (d - 1) * (9 ** (k-1))
        for j in range(k-1):
          S *= len(n) - j - 1
          S //= j + 1
        T = 9 ** k
        for j in range(k):
          T *= len(n) - j - 1
          T //= j + 1
        return S + T + Anger(n[1:], k - 1)
    
print(Anger(N, K))

Submission status: Wrong Answer

Solution code:
import math
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

answer=0

n=int(input())
k=int(input())
now=n
keta=0
while now!=0:
    now=now//10
    keta+=1
keta-=1

if k>keta+1:
    print(0)
else:
    moto=10**keta
    first=n//moto
    if k>=2:
        second=(n-first*moto)//(moto//10)
        if k>=3:
            third=(n-first*moto-second*(moto//10))//(moto//100)
    #print(keta)
    #print(first, second)
    if keta>=k:
        answer+=cmb(keta, k)*(9**k)
    answer+=max(first-1, 0)*cmb(keta, k-1)*(9**(k-1))
    if k==1:
        answer+=1
    elif k==2:
        if keta>=k and second!=0:
            answer+=cmb(keta-1, k-1)*(9**(k-1))
        answer+=cmb(keta-1, k-2)*max(second-1, 0)*(9**(k-2))
        if keta>=k:
            answer+=cmb(keta-2, k-2)*(9**(k-2))
        else:
            if second!=0:
                answer+=1
    else:
        if keta>=k and second!=0:
            answer+=cmb(keta-1, k-1)*(9**(k-1))
        answer+=cmb(keta-1, k-2)*max(second-1, 0)*(9**(k-2))
        if keta>=k and third!=0:
            answer+=cmb(keta-2, k-2)*(9**(k-2))
        if keta>=k:
            answer+=third
        else:
            if third!=0:
                answer+=1
    
    print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def main():
    N = list(map(int, input()))
    K = int(input())
    A = len(N)
    if A < K:
        return 0
    if K == 1:
        return N[0] + 9 * (A - 1)
    if K == 2:
        t = 9 * 9 * (A - 1) * (A - 2) // 2
        t += (N[0] - 1) * 9 + N[1] + (A - 2) * N[0] * 9
        return t
    if K == 3:
        if A == 3:
            if N[0] * 100 + N[1] * 10 + N[2] < 111:
                return 0
        t = 9 * 9 * 9 * (A - 1) * (A - 2) * (A - 3) // 6
        t += (N[0] - 1) * 9 * 9 * (A - 2) + (N[1] - 1) * 9 * (A - 2) + 9 * (A - 3) + N[2]
        for i, j in combinations(N[2:], 2):
            t += N[0] * 9 * 9
        return t

    

print(main())

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
l = len(N)
if K == 1:
    a = int(N[0])
    ans1 = 9*(l-1)+a
if K == 2:
    a=int(N[0])
    ans2 =(a-1)*9*(l-1)
    state = 0
    for n in N[1:]:
        if state:
            ans2 += 9
            continue
        if int(n) != 0:
            state = 1
        n = int(n)
        ans2 += n
    for i in range(2,l):
        ans2 += 81*(i-1)
    if l < K:
        ans2 = 0
if K == 3:
    a = int(N[0])
    ans3 = (a-1)*81*(l-1)*(l-2)/2
    state = 0
    for i in range(1,l):
        n = int(N[i])
        if state:
            ans3 += 81*(l-i-1)
            continue
        if n !=0:
            state = 1
        else:
            continue
        S = 0
        for j in range(i+1,l):
            m = int(N[j])
            if S:
                ans3 += n*9
                continue
            if m != 0:
                S = 1
            ans3 += n*m
    for i in range(3,l):
        ans3 += 729*(i-1)*(i-2)/2
    if l < K:
        ans3 = 0
if K == 1:
    print(ans1)
if K == 2:
    print(int(ans2))
if K == 3:
    print(int(ans3))

Submission status: Wrong Answer

Solution code:
import itertools
S=input()
SS=int(S)
N=len(S)
K=int(input())
def base9(n):
    res=""
    while(n>0):
        res=str((n%9)+1)+res
        n=n//9
    return "1"*(K-len(res))+res
ans=0
for seq in itertools.combinations(range(N),K):
    #print(seq,ans)
    low=0
    high=-1+9**K
    tmp=sum([9*10**(seq[i]) for i in range(K)])
    #print(tmp,SS)
    if tmp<=SS:
        ans+=9**K
        continue
    while(high-low>1):
        mid=(high+low)//2
        tmp2=base9(mid)
        tmp=sum([int(tmp2[i])*10**(seq[-i-1]) for i in range(K)])
        #print(tmp,tmp2,SS,low,mid,high)
        if tmp<=SS:
            low=mid
        else:
            high=mid
    ans+=low+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):
    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] * (L[i] - 1)
    DP[i][j][0] += DP[i - 1][j][1] 
    DP[i][j][1] = DP[i - 1][j - 1][1]

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

Submission status: Wrong Answer

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

len_n = len(str(n))

base = [[0]*4 for _ in range(100)]
for i in range(4):
    base[i][0] = 0

for i in range(100):
    base[i][0] = 1
for i in range(1, 100):
    base[i][1] = 9 * i
for i in range(2, 100):
    base[i][2] = 9 * 9 * i*(i-1)//2
for i in range(3, 100):
    base[i][3] = 9 * 9 * 9 * i * (i - 1) * (i-2) // 6

ans = 0
len_n = len(str(n))
n_str = str(n)

for i in range(len(n_str)):
    if int(n_str[i]) > 0:
        ans += (int(n_str[i])-1)*base[len_n-1][k-1] + base[len_n-1][k]
        # print(ans)
    len_n -= 1
    k -= 1
    if k == 0:
        break

print(ans+1)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
def Anger(n, k):
  d = int(n[0])
  if len(n) < k:
    return 0
  else:
    if k == 1:
      S = d + 9 * (len(n) - 1)
      return S
    else:
      if d == 0:
        return Anger(n[1:], k - 1)
      else:
        S = (d - 1) * (9 ** (k-1))
        for j in range(k-1):
          S *= len(n) - j - 1
          S //= j + 1
        T = 9 ** k
        for j in range(k):
          T *= len(n) - j - 1
          T //= j + 1
        return S + T + Anger(n[1:], k - 1)
    
print(Anger(N, K))

Submission status: Wrong Answer

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

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    ret = 0
    for c in n:
        if c != '0':
            ret += 1
    return ret

ans = 0
if len(n) == k and cnt(n) == k:
    ans +=1

for i in range(len(n)):
    if len(n)-i > k:
        ans += calc(i, k)
    if int(n[i]) == 0:
        continue
    k -= 1
    if k < 0:
        break
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)

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):
    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] * (L[i] - 1)
    DP[i][j][0] += DP[i - 1][j][1] 
    DP[i][j][1] = DP[i - 1][j - 1][1]

print(DP[-1][-1][0] + DP[-1][-1][1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
tmpn=int(str(n)[:k]+("0"*(len(str(n))-k)))
# print(tmpn)
if k==2 and n<11:
    print(0)
    quit()
if k==3 and n<111:
    print(0)
    quit()
nonzero=[0]*3
cnt=0
for i in range(keta):
    if str(n)[i]!=0:
        nonzero[cnt]=int(str(n)[i])
        cnt+=1
    if cnt==k:
        break
# print(nonzero)
    

ans=0
def combinations_count(n, r):
    if n<=0 or r<=0 or n-r<=0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if k==1:
    ans+=int(str(n)[0])
    ans+=(keta-1)*9
if k==2:
    ans+=nonzero[1]+(int(str(n)[0])-1)*9
    ans+=int(str(n)[0])*(keta-2)*9
    ans+=combinations_count(keta-1,k)*81
if k==3:
    ans+=nonzero[2]+(nonzero[1]-1)*9+(int(str(n)[0])-1)*81
    ans+=int(str(n)[0])*nonzero[1]*(keta-k)*9
    ans+=int(str(n)[0])*combinations_count(keta-2,2)*81
    ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = [int(sys.stdin.buffer.readline()) for _ in range(2)]
N = str(N)

DIGIT = len(N)
# d から K 個選ぶ
dp = np.zeros((DIGIT + 1, K + 1, 2), dtype=int)
dp[0, 0, 0] = 1
for d in range(1, DIGIT + 1):
    nd = int(N[d - 1])
    if nd > 0:
        dp[d, :, 1] += dp[d - 1, :, 0]
        dp[d, :, 1] += dp[d - 1, :, 1]
        for k in range(1, K + 1):
            # この d で 1 個使う
            dp[d][k][0] += dp[d - 1][k - 1][0]
            dp[d][k][1] += dp[d - 1][k - 1][0] * (nd - 1)
            dp[d][k][1] += dp[d - 1][k - 1][1] * 9
    else:
        dp[d][:][0] += dp[d - 1][:][0]
        dp[d][:][1] += dp[d - 1][:][1]
        for k in range(1, K + 1):
            # この d で 1 個使う
            dp[d][k][0] += dp[d - 1][k - 1][0]
            dp[d][k][1] += dp[d - 1][k - 1][0] * (nd - 1)
            dp[d][k][1] += dp[d - 1][k - 1][1] * 9
print(dp[-1][K].sum())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K):
    if len(N) < K:
        return 0
    M = len(N)
    ans = 1
    for i in range(K):
        ans *= M - i
        ans //= i+1
        ans *= 9
    if K >= 1:
        t = 9 - int(N[0])
        for i in range(K-1):
            t *= len(N) - 1 - i
            t //= i+1
            t *= 9
        ans -= t
    if K >= 2:
        t = 9 - int(N[1])
        for i in range(K-2):
            t *= len(N) - 2 - i
            t //= i+1
            t *= 9
        ans -= t
    if K >= 3:
        t = 9 - int(N[2])
        ans -= t
    return ans


def main():
    N = read_str()
    K = read_int()
    print(slv(N, K))

    # N = str(random.randint(1, 10))
    # K = random.randint(1, 3)
    # print(N)
    # print(K)
    # print(slv(N, K))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()

S = str(N)
bl = len(S)

if K==1:
    print(int(S[0])+9*(bl-1))

if K==2:
    ans = 0
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    print(ans)

if K==3:
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    S = S[1:]
    bl = len(S)
    ans += (int(S[0])-1)*9*(bl-1)
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
ans = list()
notans = list()
for i in range(1, n+1):
    if len(str(i)) == k:
        ans.append(i)
    if ("0" in str(i) and len(str(i)) == k):
        notans.append(i)
print(len([elem for elem in ans if elem not in notans ]))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
m = len(str(n))
if n < 10^4:
  s = 0
  for i in range(1,n+1):
    if sum([1 for j in str(i) if j!="0"])==k:
      s += 1
else:
  if k==1:
    s = n//(10**(m-1)) + 9*(m-1)
  elif k==2:
    s = n//(10**(m-1))*9*(m-1) - (9-n//(10**(m-2))%10) + 9*9*(m-1)*(m-2)//2
  elif k==3:
    s = n//(10**(m-1))*9*9*(m-1)*(m-2)//2 - (99-n//(10**(m-3))%100) + 9*9*9*(m-1)*(m-2)*(m-3)//6
print(s)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
l = len(N)
if K == 1:
    a = int(N[0])
    ans1 = 9*(l-1)+a
if K == 2:
    a=int(N[0])
    ans2 =(a-1)*9*(l-1)
    state = 0
    for n in N[1:]:
        if state:
            ans2 += 9
            continue
        if int(n) != 0:
            state = 1
        n = int(n)
        ans2 += n
    for i in range(2,l):
        ans2 += 81*(i-1)
    if l < K:
        ans2 = 0
if K == 3:
    a = int(N[0])
    ans3 = (a-1)*81*(l-1)*(l-2)/2
    state = 0
    for i in range(1,l):
        n = int(N[i])
        if state:
            ans3 += 81*(l-i-1)
            continue
        if n !=0:
            state = 1
        else:
            continue
        State = 0
        for j in range(i+1,l):
            m = int(N[j])
            if State:
                ans3 += n*9
                continue
            if m != 0:
                State = 1
            ans3 += n*m
    for i in range(3,l):
        ans3 += 729*(i-1)*(i-2)/2
    if l < K:
        ans3 = 0
if K == 1:
    print(ans1)
if K == 2:
    print(int(ans2))
if K == 3:
    print(int(ans3))

Submission status: Wrong Answer

Solution code:
a = int(input())
k = int(input())
c  = 0
st = str(a)
s = len(str(a))
if k> s:
    print(0)
    exit()
if k ==1:
    l = int(st[0])
    c += l
    c += 9*(s-1)
elif k == 2:
    c += int(st[1])+9*(s-2)#senntousonomama
    # print(c)

    c += int(int(st[0])-1)*9*(s-1)#senntoutukau

    c += ((s-1)*(s-2)*81)//2

elif k == 3:
    c += int(st[2])+9*(s-3)#senntousonomama
    # print(c)
    c += (int(st[1])-1)*9*(s-2)#senntousonomama

    c += ((s-3)*(s-2)*81)//2

    c += (int(int(st[0])-1)  *((s-2)*(s-1)*81)//2    )

    c += ((s-3)*(s-2)*(s-1)*729)//6


print(max(0,c))