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: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a
 
show_flg=False
show_flg=True
 
ans=0

s=input()
n=len(s)
K=I()

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

# dp[i][j][d] to i-th , j of digit with 1-9, d=0:x<N
dp[0][0][0]=1
#dp[0][0][1]=0



def solve():
    for i in range(n):
        c=int(s[i])
        for sm in range(1):
            for j in range(K+1):
            
            
                # 0以外をつける J+=1
                if j!=K:
                    if c!=0:
                        # x=N かも　のまま cをつける
                        dp[i+1][0][j+1]+=dp[i][0][j]
                        # 同じからN未満に確定
                        dp[i+1][1][j+1]+=dp[i][0][j]*(c-1 if c!=0 else 0)
                        # N未満のまま
                        dp[i+1][1][j+1]+=dp[i][1][j]*9
                    else:
                        # x=N かも　のまま cをつける
                        #dp[i+1][0][j+1]+=dp[i][0][j]
                        # 同じからN未満に確定
                        #dp[i+1][1][j+1]+=dp[i][0][j]
                        # N未満のまま
                        dp[i+1][1][j+1]+=dp[i][1][j]*9
                        
                
                # 0をつける j+=0
                if c!=0:
                    # x=N かも　のまま
                    0
                    # 同じからN未満に確定
                    dp[i+1][1][j]+=dp[i][0][j]
                    # N未満のまま
                    dp[i+1][1][j]+=dp[i][1][j]
                else:
                    # x=N かも　のまま
                    dp[i+1][0][j]+=dp[i][0][j]
                    # 同じからN未満に確定
                    0
                    # N未満のまま
                    dp[i+1][1][j]+=dp[i][1][j]


solve()

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

Submission status: Accepted

Solution code:
n=int(input())
m=len(str(n))
k=int(input())
def c(n,m):
    import math
    if n-m<0 or m<=0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))
def f(m,k):
    return c(m,k)*9**(k)
#ans=f(m-1,k)
#ans+=f(m-1,k-1)*(int(str(n)[0])-1)

def slove(n,k):
    if k==0:
        return 0
    m=len(str(n))
    t=0
    t+=f(m-1,k)
    t+=f(m-1,k-1)*(int(str(n)[0])-1)
    if k==1:
        t+=int(str(n)[0])
    if n>9:
        t+=slove(int(str(n)[1:]),k-1)
    else:
        if k==1:
            return n
    return t

print(slove(n,k))

Submission status: Accepted

Solution code:
n = input()
K = int(input())
len_n = len(n)
ans = 0
#自由な数字を選んでいいのかどうか？、今使った0以外、今の桁数
def calc(free, count, now):
    global ans
    if count == K:
        ans += 1
        return
    if now == len_n:
        return 
    if free:
        for _ in range(9):
            calc(free, count + 1, now+1)
        #この数字を0にするとき
        calc(free, count, now+1)
    else:
        #自由に数字選べない時
        if n[now] != '0':
            for _ in range(int(n[now])-1):
                calc(not free, count + 1, now+1)
            #この数字を元の数字と同じ
            calc(free, count+1, now+1)
        #このすうじを0にする
            calc(not free, count, now+1)
        else:
            calc(free, count, now+1)
calc(False,0,0)
print(ans)

Submission status: Accepted

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)

def calc1(S):
    if len(S)<1:
        return 0
    flag = False
    ans = 0
    for s in S:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    return ans

def calc2(S):
    bl = len(S)
    ans = 0
    if bl<2:
        return 0
    # 最上位bitに0
    ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    val = -1
    for i in range(1,len(S)):
        if S[i]!='0':
            val = i
            break
    if val!=-1:
        newS = S[val:]
        ans += calc1(newS)
    return ans

def calc3(S):
    bl = len(S)
    if bl<3:
        return 0
    ans = 0
    # 最上位bitに0
    ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    val = -1
    for i in range(1,len(S)):
        if S[i]!='0':
            val = i
            break
    if val!=-1:
        newS = S[val:]
        ans += calc2(newS)
    return ans

if K==1:
    print(calc1(S))
if K==2:
    print(calc2(S))
if K==3:
    print(calc3(S))

Submission status: Accepted

Solution code:
from itertools import combinations as com
def comb(a,b):
  if a == 0:
    return 1
  r = 1
  for i in range(b):
    r *= a
    a -= 1
  r = r // [1,2,6][b-1]
  return r
n = input()
nl = len(n)
k = int(input())
i = 0
c = 0
while i < nl:
  if i+1 >= nl:
    break
  if i+1 < k:
    pass
  else:
    if k == 1:
      c += 9
    elif k == 2:
      c += 81 * i
    else:
      c += 729 * (i*(i-1))//2
  i += 1
lis = []
if k == 1:
  for cur in range(1,10):
    cur = cur * 10**i
    lis.append(cur)
elif k == 2:
  for j in range(i):
    for k in range(1,10):
      for cur in range(1,10):
        cur = cur * 10**i + k * 10**j
        lis.append(cur)
else:
  for j,k in com(range(i),2):
    for l in range(1,10):
      for m in range(1,10):
        for cur in range(1,10):
          if cur < int(n[0]):
            c += 1
          else:
            cur = str(cur) + '0'*(i-k-1) + str(l) + '0'*(k-j-1) + str(m) + '0'*j
            if cur <= n:
              c += 1
n = int(n)
for i in lis:
  if i <= n:
    c += 1
print(c)

Submission status: Accepted

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

M = len(str(N)) # 桁数

def solve_1(n,m):
    ans = 0
    ans += 9*(m-1)
    x = n//(10**(m-1))
    ans += x
    return ans

def solve_2(n,m):
    ans=0
    if m<2:
        return ans
    elif m>2:
        ans+= (9**2)*int((m-2)*(m-1)/2) 

    x = n//(10**(m-1))
    ans+= (x-1)*(m-1)*9

    y=int(str(n)[1:])
    ans+=solve_1(y,len(str(y)))
    # ans+= int(str(n)[1])+9*(m-2)
    return ans

def solve_3(n,m):
    ans=0
    if m<3:
        return ans
    elif m>3:
        ans+=int((9**3)*(1/6)*(m-1)*(m-2)*(m-3))
    
    x = n//(10**(m-1))
    ans+=int((x-1)*(m-1)*(m-2)/2*81)
    
    y= int(str(n)[1:])

    ans+=solve_2(y,len(str(y)))
    return ans

if K==1:
    ans = solve_1(N,M)
if K==2:
    ans = solve_2(N,M)
if K==3:
    ans = solve_3(N,M)

print(ans)

Submission status: Accepted

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
if(n_digit < k):
    # 満たす物は無い.
    print(0)
else:
    # 最大桁数-1の桁の数について、何が入っても問題ないので、3箇所選んで1-9をそれぞれ選ぶ.
    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 += (n_top - 1) * com.calc_COM(n_digit-1, k-1) * (9 ** (k-1))
        # 最大桁がn_topなら、残りは自由じゃない……
        n_sec = 0
        count = n_digit
        i = 1
        for nc in n_str[1:]:
            i += 1
            count -= 1
            n_sec = int(nc)
            if(n_sec > 0):
                break
        if(count >= k-1):
            # まだ可能性がある！
            # 次に来る1以上の数字がcountよりも先だったら二つとも自由
            ans += 1 * com.calc_COM(count-1, k-1) * (9 ** (k-1))
            # 次の1以上の数字がcountの位置に来る.
            if(k-2 <= 0):
                ans += 1 * n_sec # これで終わりだからその下は考えないでいいのじゃ.
            else:
                # 次に来る1以上の数字がn_sec未満なら残りは自由
                ans += 1 * (n_sec - 1) * com.calc_COM(count-1, k-2) * (9 ** (k-2))
                # 次に来る1以上の数字がn_secと同じなら、残りは自由じゃない……
                n_third = 0
                sec_count = count
                for nd in n_str[i:]:
                    sec_count -= 1
                    n_third = int(nd)
                    if(n_third > 0):
                        break
                if(sec_count >= k-2):
                    # まだ可能性がある！
                    # 最後の数字がsec_countよりも下の位置
                    ans += 1 * 1 * (sec_count-1) * 9
                    # 最後の数字がsec_countの位置
                    ans += 1 * 1 * n_third

    print(ans)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

import math

def f(m, k):
    if k > m:
        return 0

    return math.factorial(m)//(math.factorial(m-k)*math.factorial(k))*(9**k)


def g(N, k, i):
    if k == 0:
        return 1
        
    M = len(N)-i

    if M < k:
        return 0

    n = int(N[i])

    s = 0

    if n > 0:
        s += f(M-1, k) + (n-1)*f(M-1, k-1) + g(N, k-1, i+1)
    else:
        s += g(N, k, i+1)

    return s


N = input()
K = int(input())
print(g(N, K, 0))

Submission status: Accepted

Solution code:
N = int(input()) # 数字を変数に格納
K = int(input()) # 数字を変数に格納

num = len(str(N))
n = str(N)
List = [[0,0],[0,0],[0,0]]
count = 0

for i in range(num):
    if n[i] != '0':
        List[count][0] = int(n[i])
        List[count][1] = num - i
        count += 1
        if count == 3:
            break
        
result = 0

if K == 1:
    result += List[0][0] + (List[0][1] - 1) * 9
elif K == 2:
    if N <= 10:
        result = 0
    else:
        if List[1][1] != 0:
            result += List[1][0] + (List[1][1] - 1) * 9 # 最高桁数固定
        result += (List[0][0] - 1) * (List[0][1] - 1) * 9 # 最高桁数が上記以外
        result += 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) / 2 # 最高桁数が0
elif K == 3:
    if N <= 110:
        result = 0
    else:
        if List[2][1] != 0:
            result += List[2][0] + (List[2][1] - 1) * 9 # 最高1桁2桁固定
        if List[1][1] != 0:
            result += (List[1][0] - 1) * (List[1][1] - 1) * 9 # 最高1桁固定2桁が上記以外
        result += 9 * 9 * (List[1][1] - 1) * (List[1][1] - 2) / 2 # 最高1桁固定2桁が0
        result += (List[0][0] - 1) * 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) / 2 # 最高1桁が上記以外
        result += 9 * 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) * (List[0][1] - 3) / 3 / 2 # 最高1桁が0

print(int(result))

Submission status: Accepted

Solution code:
import math
def comb(n, r):
  if n >= r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0
N = int(input())
K = int(input())
A = []
ans = 0


for i in range(K):
  n = int(str(N)[0])
  dig = len(str(N)) - 1
  A.append([n, dig])
  N -= n * 10**dig
  if N == 0:
    break
#print(A)

for i in range(len(A)):
  if A[i][1] >= K-i:
    ans += comb(A[i][1], K-i) * 9 ** (K-i) 
#    print(ans)
  ans += (A[i][0]-1) * comb(A[i][1], K-i-1) * 9 ** (K-i-1)
#  print(ans)
if len(A) == K:
  ans += 1


print(ans)

Submission status: Accepted

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

if n_num < k:
    print('0')
else:

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

    dp[0][0][0] = 1
    for i in range(n_num):
        for smaller in range(2):
            for j in range(n_num):
                lim = 9 if smaller else n_list[i]
                for x in range(lim + 1):
                    if x != 0:
                        ns = j + 1
                    else:
                        ns = j
                    nlt = smaller | (x < n_list[i])
                    dp[i + 1][nlt][ns] += dp[i][smaller][j]
    ans = dp[n_num][0][k] + dp[n_num][1][k]
    print(ans)

Submission status: Accepted

Solution code:
N = [int(i) for i in input()]
n = len(N)
K = int(input())
lis = [0]*3
foo = 0
for i in range(n):
    if N[i]!=0:
        lis[foo] = i
        foo += 1
    if foo==3:
        break



if n < K:
    print(0)
else:
    if K ==3:
        ans = (n-1)*(n-2)*(n-3)*9**3//6
        ans += (N[0]-1)*(n-1)*(n-2)*9**2 //2
        if lis[1]!=0:
            ans += (n-1-lis[1])*(n-2-lis[1])*9**2//2
        if lis[2]!=0:
            ans += (N[lis[1]]-1)*(n-1-lis[1])*9 +(n-1-lis[2])*9 +N[lis[2]]
    elif K ==2:
        ans = (n-1)*(n-2)//2 *9**2 +(N[0]-1)*(n-1)*9
        if lis[1]!=0:
            ans += (n-1-lis[1])*9 +N[lis[1]]
    elif K ==1:
        ans = 9*(n-1) +N[0]

    print(max(0,ans))

Submission status: Accepted

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

def nine(x, y):
  if y == 0:
    return 1
  elif x < y:
    return 0
  elif x == y:
    return 9 ** x
  elif y < 0:
    return 0
  else:
    r = 1
    for i in range(y):
      r *= x - i
      r //= i + 1
    r *= 9 ** y
    return r

ans = 0
if n > 10000:
  while n >= 10**(k-1):
    d = math.floor(math.log(n, 10))
    ans += nine(d, k)
    ans += nine(d, k-1) * (n//(10**d) - 1)
    n %= 10**d
    if k > 0:
      k -= 1
    else:
      break
  print(ans)
else:
  for i in range(1,n+1):
    if str(i).count('0')==len(str(i))-k:
      ans += 1
  print(ans)

Submission status: Accepted

Solution code:
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
K = int(input())
strN = str(N)
lenn = len(strN)
if K == 1:
    print((lenn-1)*9 + int(strN[0]))
elif K == 2:
    if lenn == 1:
        print(0)
    else:
        ans1 = 81*comb(lenn-1,2)
        ans1 += (int(strN[0])-1)*9*(lenn-1)
        for i in range(1,lenn):
            if int(strN[i]) != 0:
                ans1 += int(strN[i])
                ans1 += 9*(lenn-i-1)
                break
        print(ans1)
else:
    if lenn <= 2:
        print(0)
    else:
        ans1 = (9**3)*comb(lenn-1,3)
        ans1 += (int(strN[0])-1)*81*comb(lenn-1,2)
        for i in range(1,lenn):
            if strN[i] != '0':
                break
        strN = strN[i:]
        lenn = len(strN)
        if lenn == 1:
            ans2 = 0
        else:
            ans2 = 81*comb(lenn-1,2)
            ans2 += (int(strN[0])-1)*9*(lenn-1)
            for i in range(1,lenn):
                if int(strN[i]) != 0:
                    ans2 += int(strN[i])
                    ans2 += 9*(lenn-i-1)
                    break
        print(ans1+ans2)

Submission status: Accepted

Solution code:
def f2(n):
    c = len(n)-1
    nn = n[1:]
    s = c*(c-1)//2 * 9*9 
    s += c * (int(n[0])-1)*9
    nn = str(int(nn))
    s += (len(nn)-1)*9 + int(nn[0])
    return s

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

if k == 1:
    print((len(n)-1)*9 + int(n[0]))
if k == 2:
    if len(n) >= 2:
        print(f2(n))
    else:
        print(0)
        
if k == 3:
    if len(n) >= 3:
        c = len(n)-1
        nn = n[1:]
        nn = str(int(nn))
        s = c*(c-1)*(c-2)//(3*2) * 9*9*9
        s += (int(n[0])-1) * c*(c-1)//2 * 9*9 
        if len(nn) >= 2:
            s += f2(nn)
        print(s)
    else:
        print(0)

Submission status: Accepted

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
    if tmp//9>SS:
        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: Accepted

Solution code:
N=input()
n=int(N)
K=int(input())
import math

l=len(N)

if l==1:
  if K==1:
    print(N)
  else:
    print(0)
else:
  a=[0]*3
  b=[l]*3
  k=0
  for i in range(l):
    if int(N[i])!=0:
      a[k]=int(N[i])
      b[k]=i
      k+=1
    if k==3:
      break
  #print(a,b,l)
  x=0
  for i in range(l-1):
    if K==1:
      x+=9
    elif K==2:
      x+=81*i
    else:
      x+=(729*i*(i-1))//2
  
  if K==1:
    x+=a[0]
  elif K==2:
    x+=(a[0]-1)*9*(l-1)+max([0,(l-b[1]-1)*9])+a[1]
  else:
    x+=((a[0]-1)*81*(l-2)*(l-1))//2
    x+=(81*max([0,(l-b[1]-1)])*max([0,(l-b[1]-2)]))//2
    x+=max([0,(a[1]-1)])*9*max([0,(l-b[1]-1)])
    x+=9*max([0,(l-b[2]-1)])+a[2]
  
  print(x)

Submission status: Accepted

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

def take_k_comb(a, b):
    if b == 0:
        return 1
    if b == 1 and a >= 1:
        return a * 9
    if b == 2 and a >= 2:
        return a*(a-1)//2 * 9 * 9
    if b == 3 and a >= 3:
        return a*(a-1)*(a-2)//6*9*9*9
    return 0

def constrained_nk(n, k):
    if k == 0:
        return 1
    if n == "":
        if k == 0:
            return 1
        else:
            return 0
    h = int(n[0])
    rest = n[1:]
    if h == 0:
        return constrained_nk(rest, k)
    s = take_k_comb(len(rest), k)
    s += (h-1) * take_k_comb(len(rest), k - 1)
    s += constrained_nk(rest, k-1)
    return s

print(constrained_nk(n, k))

Submission status: Accepted

Solution code:
import math

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

def calc(n, k):
    if n < 10**(k-1):
        ans = 0
    elif n == 0:
        ans=0
    else:
        ans = 0
        digits = int(math.log10(n))+1
        #Nより小さい桁数
        if k <= digits-1:
            for n_dig in range(k, digits):
                ans += 9 * combinations_count(n_dig-1,k-1) * (9**(k-1))
                #print(n_dig,tot)
        #Nと桁数が同じ
        top = n//10**(digits-1)
        ans += (top-1) * combinations_count(digits-1,k-1) * (9**(k-1))
        if k>1:
            ans += calc(n-top*10**(digits-1), k-1)
        elif k==1:
            ans += 1
    #print(n,k,ans)
    return ans
    

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

tot = calc(N,K)

print(tot)

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
def nonzero1(N):
    m = len(str(N))
    a = int(str(N)[-m]) 
    return a + 9*(m-1)
def nonzero2(N):
    m = len(str(N))
    a = int(str(N)[-m])
    n = N - a * (10**(m-1))
    s = ((m-1)*(m-2)*9*9)//2 + (m-1)*(a-1)*9
    return s + nonzero1(n)
def nonzero3(N):
    m = len(str(N))
    a = int(str(N)[-m])
    n = N - a * (10**(m-1))
    s = ((m-1)*(m-2)*(m-3)*9*9*9)//6 +((m-1)*(m-2)*9*9*(a-1))//2
    return s + nonzero2(n)
if K == 1:
    print(nonzero1(N))
elif K == 2:
    print(nonzero2(N))
else:
    print(nonzero3(N))

Submission status: Accepted

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):
    cnt = 0
    for c in n:
        if c != "0":
            cnt += 1
    return cnt

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


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

Submission status: Accepted

Solution code:
import sys 
N = list(input())
K = int(input())

L = len(N)
if K>L:
    print(0)
    sys.exit()
#%%
def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        L2 -= 1
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)* int((L2-1)>0)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == K:
    ans += 1
print(int(ans))

Submission status: Accepted

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

#print(N_str)
digit_N=len(N_str)

#dp[i][j][k]
#i:eqflag, j:digit, k:K
#dp=[[[0]*2 for _ in range(digit_N)] for _ in range(K+1)]
dp=[[[0]*(K+1) for _ in range(digit_N)] for _ in range(2)]
dp[0][0][0]=1
dp[0][0][1]=int(N_str[0])-1
dp[1][0][1]=1
#print(dp)

for j in range(1,digit_N):
  digit=int(N_str[j])
  for k in range(K+1):
    if digit==0:
      if k==0:
        dp[0][j][0]=dp[0][j-1][0]
      else:
        dp[0][j][k]=dp[0][j-1][k]+9*dp[0][j-1][k-1]
        dp[1][j][k]=dp[1][j-1][k]
    else:
      if k==0:
        dp[0][j][0]=dp[0][j-1][0]
      else:
        dp[0][j][k]=dp[0][j-1][k]+9*dp[0][j-1][k-1]+dp[1][j-1][k]+(digit-1)*dp[1][j-1][k-1]
        dp[1][j][k]=dp[1][j-1][k-1]
    
#print(dp)
print(dp[0][-1][K]+dp[1][-1][K])

Submission status: Accepted

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

top = int(s[0])



def k_2(s):
    d = len(s)
    top = int(s[0])
    first_non_zero = -1
    first_pos = -1
    for i in range(1, d):
        if s[i] != '0':
            first_non_zero = int(s[i])
            first_pos = d - i
            break
    x = ((d-2) * (d-1) // 2) * 81
    y =  (top-1) * 9 * (d-1)
    z = first_non_zero + (first_pos-1) * 9 if first_pos >= 0 else 0
    return (x+y+z)    


if k == 1:
    print((d-1) * 9 + top)

elif k == 2:
    print(k_2(s))

else:
    x = ((9 ** 3) * (((d-3)*(d-2)*(2*d-5) // 6) + ((d-3)*(d-2) // 2)) //2)
    y = (top-1) * 81 * ((d-1)*(d-2) // 2)
    
    first_non_zero = -1
    ind = -1
    for i in range(1, d):
        if s[i] != '0':
            ind = i
            break
    z = k_2(s[ind:])
    # print(x)
    # print(y)
    # print(z)
    print(x + y + z)

Submission status: Accepted

Solution code:
def make_num(n, k):
    if k == 0 or len(n)<k:
        return 0
    else:
        if int(n[0]) == 0:
            return make_num(n[1:], k)
        else:
            ln = len(n)
            if k == 3:
                return (((ln-1)*(ln-2)*(ln-3))//6)*(9**3) + (int(n[0])-1)*81*(((ln-1)*(ln-2))//2) + make_num(n[1:], k-1)
            elif k == 2:
                return (((ln-1)*(ln-2))//2)*81 + (int(n[0])-1)*9*(ln-1)  + make_num(n[1:], k-1)
            elif k == 1:
                return 9 * (ln-1) + int(n[0])

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

print(make_num(n,k))

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
m = len(list(str(n)))
n0 = list(str(n))
for i in range(m):
    n0[i] = int(n0[i])
ans = 0
comb = 1
if k < m:
    for j in range(k):
        comb *= (m-1-j)
        comb //= (j+1)
    ans += comb*(9**k)
#print(ans,k,m)
if k == 1:
    ans += n0[0]
elif k == 2:
    if m >= 2:
        ans += (n0[0]-1)*9*(m-1)
        c = 1
        while n0[c] == 0 and c < m-1:
            c += 1
        if n0[c] > 0:
            ans += n0[c]
            ans += 9*(m-c-1)
    else:
        ans = 0
else:
    if m >= 3:
        ans += (n0[0]-1)*9*9*(m-1)*(m-2)//2
        c = 1
        while n0[c] == 0 and c <= m-2:
            c += 1
        if c < m-1:
            ans += (n0[c]-1)*9*(m-c-1)
            ans += 9*9*(m-c-1)*(m-c-2)//2
            c1 = c+1
            while n0[c1] == 0 and c1 < m-1:
                c1 += 1
            if n0[c1] > 0:
                ans += n0[c1]
                ans += 9*(m-c1-1)
    else:
        ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
n=list(input())
N=len(n)
k=int(input())
x=int(n[0])
if N<k:
  print(0)
  sys.exit()

def s1(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s1(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=(N-1)*9
    ans+=x
    return ans

def s2(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s2(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=((N-1)*(N-2))*81//2
    ans+=((x-1)*(N-1))*9
    m2=m[1:N+1]
    ans+=s1(m2)
    return ans
  
def s3(m):
  N=len(m)
  x=int(m[0])
  if N>1 and x==0:
    m2=m[1:N+1]
    return s3(m2)
  elif x==0:
    return 0
  else:
    ans=0
    ans+=((N-1)*(N-2)*(N-3)*729)//6
    ans+=((x-1)*(N-1)*(N-2)*81)//2
    m2=m[1:N+1]
    ans+=s2(m2)
    return ans

if k==1:
  print(s1(n))
  sys.exit()

if k==2:
  print(s2(n))
  sys.exit()

if k==3:
  print(s3(n))
  sys.exit()

Submission status: Accepted

Solution code:
import itertools
import math

def solve():
  N = int(input())
  K = int(input())
  log_N = math.ceil(math.log10(N+1))
  digit_table = range(0,log_N)
  ret = 0
  for comb in itertools.combinations(digit_table, K):
    num = 0
    stack = [0]
    next_stack = []
    log_N
    if sum(9*(10**c) for c in comb) <= N: 
      ret += 9**K
      continue
    for c in comb:
      while stack:
        num_base = stack.pop()
        for d in range(1,10):
          num = num_base+d*10**c

          # print(num)
          if c == comb[-1]:
            if num <= N: 
              # print(num)
              ret += 1
          else:
            next_stack.append(num)

      stack = next_stack
      next_stack = []

  print(ret)
  
solve()

Submission status: Accepted

Solution code:
N=int(input())
K = int(input())
def one(N):
    n = list(str(N))
    A = (len(n)-1)*9
    A += int(n[0])
    return A

def two(N):
    n = list(str(N))
    r = len(n)
    A = (int(n[0])-1)*(r-1)*9 #r-1C1*9
    A = A + (r-2)*(r-1)*81/2  #r-1C2*81
    A = A + one(N%(10**(r-1)))
    return(A)

if K==1:
    print(int(one(N)))

elif K==2:
    print(int(two(N)))

elif K==3:
    n = list(str(N))
    r = len(n)
    A = two(10**(r-1)-1)*(int(n[0])-1)
    A = A + two(N%(10**(r-1)))
    A = A + (r-2)*(r-1)*(r-3)*81*9/6
    print(int(A))

Submission status: Accepted

Solution code:

def solve(n,k):
    for i in range(len(n)):
        if n[i] != 0:
            break
    n = n[i:]
    if n == []:
        return 0
    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:
        tmp += solve(n[1:],k-1)

    elif k == 2:
        for i in range(1, l):
            if n[i] != 0:
                tmp += n[i] + 9*(l-i-1)
                break
    else:
        tmp += 1
    ans += tmp
    return ans

n = list(map(int, input()))
k = int(input())

print(solve(n,k))

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
d=len(str(n))
from math import factorial as f
def c(n):
  if n<2:
    return 0
  else:
    return f(n)//(f(n-2)*f(2))
def kk(n):
  dd=len(str(n))
  s=9*(dd-1)
  s+=int(str(n)[0])
  return s
def kkk(n):
  d=len(str(n))
  s=81*(d-1)*(d-2)//2
  s+=9*(d-1)*(int(str(n)[0])-1)
  s+=kk(int(str(n)[1:]))
  return s

if d==1 and k!=1:
  print(0)
else:
  if k==1:
    ans=kk(n)
  elif k==2:
    ans=kkk(n)
  else:
    t=0
    for i in range(2,d-1):
      t+=c(i)
    ans=729*t
    ans+=81*c(d-1)*(int(str(n)[0])-1)
    ans+=kkk(int(str(n)[1:]))
  print(ans)