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

# 桁DP
# dp[桁数][未満フラグ][0じゃない数の数]
# 010みたいなときに頭の0を数えないよう注意（0を数えると面倒、0じゃないを数えれば問題なし）

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

# ある数が与えられたときに、その数未満で0じゃない数の値を返す
def getMiman(X):
  if X>0:
    return X-1
  else:
    return 0

x0=int(N[0])
# 未満じゃないのに先頭が0はあり得ない
dp[0][0][0]=0
# 未満で、0じゃない数が存在しないのは先頭から0の場合のみ
dp[0][1][0]=1
# 未満じゃなく、0でない数が1->元の数の場合なので1
dp[0][0][1]=1
# 未満で、0でない数が1　3の場合2,1
dp[0][1][1]=getMiman(x0)

for i in range(1,keta):
  # 全桁をDP
  x=int(N[i])
  # 未満じゃないのに0じゃない数が0個なのはあり得ない
  dp[i][0][0]=0
  # 未満で、0じゃない数が存在しないのはここまでずっと0だった場合のみ
  dp[i][1][0]=1
  for j in range(1,K+1):
    # 未満じゃなくて、0じゃない数がj個なのは以下の合計：
    # ・前の桁（未満じゃない）で0じゃない数がj-1個で、今回の桁が0じゃない場合
    # ・前の桁（未満じゃない）で0じゃない数がj個で、今回の桁が0
    dp[i][0][j]=dp[i-1][0][j-1]*(x!=0)+dp[i-1][0][j]*(x==0)
    
    # 未満で、0じゃない数がj個なのは以下の合計：
    # ・前の桁（未満じゃない）で0じゃない数がj-1個で、今回の桁が未満相当（getMiman）
    # ・前の桁（未満じゃない）で0じゃない数がj個で、今回の桁が0でない場合に0を選択する
    # ・前の桁（未満）で0じゃない数がj-1個で、今回は1-9まで選べるので9通り
    # ・前の桁（未満）で0じゃない数がj個で、今回は0を選ぶ
    dp[i][1][j]=dp[i-1][0][j-1]*getMiman(x)+dp[i-1][0][j]*(x!=0)+dp[i-1][1][j-1]*9+dp[i-1][1][j]*1
  
print(dp[keta-1][0][K]+dp[keta-1][1][K])

Submission status: Accepted

Solution code:
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()
length = len(str(N))

def F(length, K, N):
    if length < K:
        return 0
    if K == 0:
        return 1
    if length == 1: #この時、Kも1
        return N
    ret = 0
    top = int(str(N)[0])
    if length-K >= 1:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K # 一個前まで    
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) # 一桁目がtopより小さい数  
    # 一桁目がtopと同じ数
    if K > 1: 
        N = int(str(N)[1:])
        length = len(str(N))
        ret += F(length, K-1, N)
    else:
        ret += 1 # 2000のような数
    return ret

answer = F(length, K, N)
print(answer)

Submission status: Accepted

Solution code:
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
else:

    def main(d, k):
        if d == L:
            return 0
        if N[d] == "0":
            return main(d + 1, k)
        if (L - d) < k:
            return 0
        if k == 1:
            return ((L - d) - 1) * 9 + int(N[d])
        elif k == 2:
            return (
                ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81
                + ((L - d) - 1) * 9 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )
        elif k == 3:
            return (
                ((((L - d) - 1) * ((L - d) - 2) * ((L - d) - 3)) // 6) * (9 ** 3)
                + ((((L - d) - 1) * ((L - d) - 2)) // 2) * 81 * (int(N[d]) - 1)
                + main(d + 1, k - 1)
            )

    print(main(0, K))

Submission status: Accepted

Solution code:

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

keta1=len(str(N))
maxN=int(str(N)[0])
secN=0
keta2=0
if keta1>1:
    keta2=len(str(int(str(N)[1:])))
    secN=int(str(int(str(N)[1:]))[0])
    if keta2>1:
        keta3=len(str(int(str(int(str(N)[1:]))[1:])))
        thiN=int(str(int(str(int(str(N)[1:]))[1:]))[0])
only1=0
only2=0
if secN==0:
    only1=1
if keta2>1:
    if str(int(str(int(str(N)[1:]))[0]))[0]==0:
        only2=1
import math

if keta1<K:
    print(0)
else:
    if K==1:
        print(maxN+9*(keta1-1))
    if K==2:
        if keta1-2!=0:
            if only1:
                print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2)
            else:
                if keta2-1!=0:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN+(keta2-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN)
        else:
            print((maxN-1)*(keta1-1)*9+secN)
    if K==3:
        if keta1-3!=0:
            if only1:
                print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6)
            else:
                if keta2-2!=0:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN+(keta3-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN)
        else:
            if only1:
                print((maxN-1)*(keta1-1)*9)
            else:
                print((maxN-1)*(keta1-1)*9+(secN-1)*9+thiN)

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline
n = int(input())
k = int(input())
t = n
m = 0
while t:
    m += 1
    t //= 10

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

ans = 9 ** k * comb(m-1, k)
tk = k

def dfs(i, mt, kt):
    a = i // 10 ** mt
    b = n // 10 ** mt
    if kt < 0:
        return 0
    if mt < kt:
        return 0
    if a < b:
        if mt > 0:
            return 9 ** kt * comb(mt, kt)
        else:
            return 1
    elif a > b:
        return 0
    if i == n and kt == 0:
        return 1
    elif i > n:
        return 0
    ret = 0
    for j in range(10):
        f = 0
        if j != 0:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

t_ans = 0
for i in range(1, n // (10 ** (m-1) )+1):
    ti = i * 10 ** (m-1)
    t_ans += dfs(ti, m-1, k-1)

print(int(ans+t_ans))

Submission status: Accepted

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

fact = [1]
for i in range(1, 101):
    fact += [fact[i-1] * i]


def nCk(N, K):
    if K > n or K < 0:
        return 0
    return fact[N] // fact[K] // fact[N-K]


def digits(N):
    N = abs(N)
    ret = 0
    x = 1
    while x <= N:
        ret += 1
        x *= 10
    return ret

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

    d = digits(N)
    if d < K:
        return 0

    top = N // (10**(d-1))
    return (top-1) * 9**(K-1) * nCk(d-1,K-1) + 9**(K) * nCk(d-1,K) + solve(N % (10**(d-1)), K-1)

print(solve(n,k))

Submission status: Accepted

Solution code:
import copy
N=str(input())
K=int(input())
m=len(N)
def con(n,r):
  if r==0:
    return 1
  else:
    return (n/r)*con(n-1,r-1)
S=0
for i in range(1,m):
  S=S+(9**K)*con(i-1,K-1)
if K==1:
  S=S+int(N[0])
  print(int(S))
if K==2:
  S=S+9*(m-1)*(int(N[0])-1)
  for i in range(1,m):
    for i1 in range(1,10):
      N1=(int(N[0]))*(10**(m-1))+i1*10**(m-i-1)
      if int(N)>=N1:
        S=S+1
  print(int(S))
if K==3:
  S=S+(int(N[0])-1)*(9**2)*con(m-1,K-1)
  for i in range(1,m-1):
    for j in range(i+1,m):
      for i1 in range(1,10):
        for j1 in range(1,10):
          N1=(int(N[0]))*(10**(m-1))+i1*10**(m-i-1)+j1*10**(m-j-1)
          if int(N)>=N1:
            S=S+1
  print(int(S))

Submission status: Accepted

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

d_sum = [[0,0,0] for i in range(101)]
pre = [0,0,0]
for i in range(1,101):
    pre[0] += 9
    pre[1] += 81*(i-1)
    pre[2] += (9**3)*(i-1)*(i-2)//2
    d_sum[i][0] = pre[0]
    d_sum[i][1] = pre[1]
    d_sum[i][2] = pre[2]

s = str(n)

ans = d_sum[len(s)-1][k-1]

nonzero = 0
for ind, i in enumerate(s):
    if int(i)==0:
        continue
    digit = len(s)-ind-1
    if ind==0:
        nonzero += 1
        if nonzero==k:
            ans += int(i)
            break
        ans += (int(i)-1)*d_sum[digit][k-nonzero-1]
    else:
        ans += d_sum[digit][k-nonzero-1]
        nonzero += 1
        if nonzero==k:
            ans += int(i)
            break
        ans += (int(i)-1)*d_sum[digit][k-nonzero-1]

print(ans)

Submission status: Accepted

Solution code:
import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r or n==r:
    return 1
  elif r==0:
    return 1
  else:
    return 0
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    #print(ans)
    if not_zero==K:
      ans+=1
      break
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(1000010)

SN = input()
N = int(SN)
K = int(input())
# print(N,K)

m = [[0,0,0,0]]
s = [ 1, 9, 0, 0 ]
m.append(s)
#print(m) 


for i in range(2,101):
    t = [s[0], s[0]*9 + s[1], s[1]*9 + s[2], s[2]*9 + s[3] ]
    s = t
    m.append(s)

# print(m)


def count(n,k):
    if n ==0:
        if k == 0:
            return 1
        else:
            return 0
    if n < 10:
        if k == 0:
            return 1
        elif k == 1:
            return n
        else:
            return 0
    if k == 0:
        return 1

    if n < 10 ** (k-1):
        return 0
        
    t = n 
    p = 1 
    q = 0
    while t >= 10:
        t = t //10
        p = p * 10
        q = q + 1 
    # Saijoui 0 : 00000-09999
    #print("t,q", t,q)
        
    ans = m[q][k]
    #print(n,k, "#1", ans)
    # Saijoun 1-(t-1): x0000-x9999
    #print(n,k,"#2",(t-1)* m[q][k-1])
    ans = ans + (t-1)* m[q][k-1]

    # Saijoui t: t0000-tbcdrf
    remain = n - p * t 
    x = count(remain,k-1)
    #print(n,k, "#3", x)
    ans = ans + x
    # print(n,k,"#4",ans)
    return ans

print(count(N,K))

Submission status: Accepted

Solution code:
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()
length = 0
for i in range(1, 102):
    if 10 ** i > N:
        length = i
        break

answer = 0
def F(length, K, N):
    ret = 0
    if length == 1:
        if K == 1:
            return N
        elif K == 0:
            return 1
        else:
            return 0
    if length < K:
        return 0
    top = int(str(N)[0])
    if length-K >= 1:
        ret += factorial(length-1) // factorial(K) // factorial(length-K-1) * 9 ** K # 一個前まで    
    ret += factorial(length-1) // factorial(K-1) // factorial(length-K) * (top-1) * 9 ** (K-1) # 一桁目がtopより小さい数  
    if K > 1: # 一桁目がtopと同じ数
        N = int(str(N)[1:])
        length = 0
        for i in range(1, 100):
            if 10 ** i > N:
                length = i
                break
        ret += F(length, K-1, N)
    else:
        ret += 1 # 2000のような数
    return ret

answer = F(length, K, N)
print(answer)

Submission status: Accepted

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

def K1(num):
	return int(num[0]) + (len(num)-1)*9

def K2(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K1(tmp)
	out1 = (int(num[0])-1)*(L-1)*9
	out2 = ((L-1)*(L-2)//2)*9*9
	return out + out1 + out2

def K3(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K2(tmp)
	out1 = (int(num[0])-1)*((L-1)*(L-2)//2)*9*9
	out2 = ((L-1)*(L-2)*(L-3)//6)*9*9*9
	return out + out1 + out2

if len(N) < K:
	ans = 0
else:
	if K == 1:
		ans = K1(N)
	elif K==2:
		ans = K2(N)
	else:
		ans = K3(N)

print(ans)

Submission status: Accepted

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

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

for i in range(D):
    for j in range(2):
        for d in range(10 if j else N[i] + 1):
            for k in range(4):
                if d:
                    if k + 1 <= 3:
                        dp[i + 1][j | (d < N[i])][k + 1] += dp[i][j][k]
                    else:
                        continue
                else:
                    dp[i + 1][j | (d < N[i])][k] += dp[i][j][k]

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

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 5 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
    for smaller in range(2):
        for j in range(4):
            for x in range((9 if smaller else n[i]) + 1):
                dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from itertools import combinations, product

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

S_len = len(S)
N_first = int(S[0])

def combinations_count(n, r):
  if n < r:
    return 0
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

if K > S_len:
  print(0)
else:
  count = 0
  if K > 1:
    for l in combinations(range(1, S_len), K-1):
      for m in product('123456789', repeat=K-1):
        s = S[0] + '0' * (S_len - 1)
        for i in range(K-1):
          s = s[:l[i]] + m[i] + s[l[i]+1:]
        if int(s) <= N:
          count += 1
  else:
    count += 1
  count += (N_first-1) * combinations_count(S_len-1, K-1) * (9 ** (K-1))
  count += combinations_count(S_len-1, K) * (9 ** K)
  print(count)

Submission status: Accepted

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

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  return ans


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

print(syou(n, k))

Submission status: Accepted

Solution code:
from math import factorial as fac

def comb(n,r):
    if ( r<0 or r>n ):
        return 0
    return fac(n)/(fac(r)*fac(n-r))


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

nn=str(n)
keta=len(nn)

ans=0

if keta<k:
    print(0)
    exit()

zero=0

# for i in range(keta):
#     if int(nn[i])==0:zero+=1
#     ans+=comb(keta-i-1,k-i+zero)*9**(k-i)
#     if int(nn[i])-1>=0:
#         ans+=(int(nn[i])-1)*comb(keta-i-1,k-i-1+zero)*9**(k-i-1+zero)
#
# if keta-zero==k:ans+=1

def search(n,k):
    if k<=0:return
    global ans
    nn = str(n)
    keta = len(nn)
    ans += comb(keta - 1, k ) * 9 ** k
    if int(nn[0])-1>0:
        ans+=(int(nn[0])-1)*comb(keta-1,k-1)*9**(k-1)
    ne=n-int(nn[0])*10**(keta-1)
    search(ne,k-1)


search(n,k)
for i in range(keta):
    if nn[i]=="0":zero+=1
if keta-zero>=k:ans+=1
print(int(ans))

Submission status: Accepted

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

strN = str(N)
maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLeN in range(2):
        for m in range(K+1):
            x = 0
            if not isLeN and x > Nd: continue
            isLeN2 = isLeN or x < Nd
            dp[d+1][isLeN2][m] += dp[d][isLeN][m]
            for x in range(1, 10):
                if not isLeN and x > Nd: continue
                isLeN2 = isLeN or x < Nd
                m2 = m+1
                if m2 > K: continue
                dp[d+1][isLeN2][m2] += dp[d][isLeN][m]
#    print(d+1, Nd, dp[d+1])

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

Submission status: Accepted

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

def kosu(p):
  if p == 1:
    answer = [9, 0, 0]
  elif p == 2:
    answer = [9, 81, 0]
  elif p == 3:
    answer = [9, 162, 729]
  else:
    k1 = 9
    k2 = (9 ** 2) * (p - 1)
    k3 = int((9 ** 3) * (p - 1) * (p - 2) / 2)
    answer = [k1, k2, k3]
  return answer

if keta == 1:
  if K == 1:
    print(N)
  else:
    print("0")
  quit()
  
ans = 0  
for i in range(1, keta):
  ans += kosu(i)[K - 1]

#print(ans)  
if K == 1:
  ans += int(str(N)[0])
elif K == 2:
  y = 0
  i = 1
  while y == 0:
    if int(str(N)[i]) != 0:
      y = i
      ans += int(str(N)[i]) + 9 * (keta -y - 1)
    i += 1
    if i == keta:
      y = keta
    
  #print(x)
  ans += (int(str(N)[0]) - 1) * 9 * (keta - 1)
  
else:
  if keta >= 3:
    ans += int((int(str(N)[0]) - 1) * (9 ** 2) * (keta - 1) * (keta - 2) / 2)
    #print(ans)
    x = 0
    i = 1
    while x <= 1:
      if int(str(N)[i]) != 0:
        x += 1
        if x == 1:
          ans += (int(str(N)[i]) - 1) * (9 * (keta - i - 1))
          if i <= keta - 3:
            ans += (9 ** 2) * (keta - i - 1) * (keta - i - 2) / 2
        else:# x = 2
          ans += int(str(N)[i]) + 9 * (keta - i - 1)
      i += 1
      if (i == keta - 1) and (x == 0):
        x = 2
      if i == keta:
        x = 2
        

print(int(ans))

Submission status: Accepted

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
alist=[]
while now!=0:
    amari=now%10
    now=now//10
    alist.append(amari)
    keta+=1
alist.reverse()
zlist=[]
for al in range(len(alist)):
    if alist[al]!=0:
        zlist.append([al, alist[al]])

if k>keta:
    print(0)
else:
    moto=10**(keta-1)
    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-1>=k:
        answer+=cmb(keta-1, k)*(9**k)
    answer+=max(first-1, 0)*cmb(keta-1, k-1)*(9**(k-1))
    if k==1:
        answer+=1
    elif k==2:
        if keta-1>=k and second!=0:
            answer+=cmb(keta-2, k-1)*(9**(k-1))
        answer+=cmb(keta-2, k-2)*max(second-1, 0)*(9**(k-2))
        if second!=0:
            answer+=1
        else:
            swit=0
            kaz=0
            for zl in zlist:
                if zl[0]>=1 and swit==0:
                    swit=zl[0]
                    kaz=zl[1]
            if swit!=0:
                answer+=(keta-swit-1)*9
                answer+=kaz
    else:
        if keta-1>=k and second!=0:
            answer+=cmb(keta-2, k-1)*(9**(k-1)) #30xxxx
        answer+=cmb(keta-2, k-2)*max(second-1, 0)*(9**(k-2)) #31xxxx, 32xxxx
        if keta-1>=k and third!=0 and second!=0:
            answer+=cmb(keta-3, k-2)*(9**(k-2)) #330xxx
        if second!=0:
            if keta-1>=k:
                if third!=0:
                    answer+=third
                else:
                    swit=0
                    keta2=0
                    kaz=0
                    for zl in zlist:
                        if zl[0]>=2 and swit<=0:
                            swit+=1
                            keta2=zl[0]
                            kaz=zl[1]
                    if swit>0:
                        answer+=(keta-keta2-1)*9
                        answer+=kaz
            else:
                if third!=0:
                    answer+=third
        else:
            if keta-1>=k:
                if True:
                    swit=0
                    keta2=0
                    kaz=0
                    for zl in zlist:
                        if zl[0]>=2 and swit<=1:
                            swit+=1
                            keta2=zl[0]
                            kaz=zl[1]
                    if swit>1:
                        answer+=(keta-keta2-1)*9
                        answer+=kaz
                    elif swit==1:
                        if keta2!=keta:
                            answer+=cmb(keta-keta2-1, 2)*81
            else:
                if third!=0:
                    answer+=third
    
    print(answer)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from math import floor, log
from itertools import combinations, product

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

S_len = len(S)
N_first = int(S[0])

def combinations_count(n, r):
  if n < r:
    return 0
  if r == 0:
    return 1
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

if K > S_len:
  print(0)
else:
  count = 0
  if K > 1:
    for l in combinations(range(1, S_len), K-1):
      for m in product('123456789', repeat=K-1):
        s = S[0] + '0' * (S_len - 1)
        for i in range(K-1):
          s = s[:l[i]] + m[i] + s[l[i]+1:]
        if int(s) <= N:
          count += 1
  else:
    count += 1
  count += (N_first-1) * combinations_count(S_len-1, K-1) * (9 ** (K-1))
  count += combinations_count(S_len-1, K) * (9 ** K)
  print(count)

Submission status: Accepted

Solution code:
def anss(N,K):
    c=0
    for i in range(1,N+1):
        if len(str(i))-str(i).count('0') == K:
            c+=1
    return c
def solve(p,n,k):
    if p == 0:
        return 0
    if k==1:
        return 10 + 9*(n-1)+(p-1)
    elif k==2:
        return 81 * n*(n-1)//2 + (p-1)*9*n
    else:
        return 729 * n*(n-1)*(n-2)//6 + (p-1)*81*n*(n-1)//2

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

N=str(N)
NN = [i for i in list(N) if i != '0']
dig = len(N) - 1

if K == 2:
    if len(NN) == 1:
        n0 = int(N[0])
        ans= (solve(n0,dig,2))
    else:
        n0 = int(N[0])
        for inn,nn in enumerate(N[1:]):
            if nn != '0':
                n1 = int(nn)
                break
        ans= (solve(n0,dig,2) + solve(n1,dig-inn-1,1))
elif K == 3:
    if len(NN) == 1:
        n0 = int(NN[0])
        ans=solve((n0),dig,3)
    elif len(NN) == 2:
        n0 = int(N[0])
        for inn,nn in enumerate(N[1:]):
            if nn != '0':
                n1 = int(nn)
                break
        ans= (solve(n0,dig,3) + solve(n1,dig-inn-1,2))
    else:
        n0 = int(N[0])
        
        n1 = int(N[1])
        n2 = int(N[2])
        ans=solve((n0),dig,3) + solve(n1,dig-1,2) + solve(n2,dig-2,1)
elif K == 1:
    ans=(solve(int(N[0]),dig,1))
    
print(ans)

Submission status: Accepted

Solution code:
# ABC154e


def main():
    import sys
    import math
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)
    # 再帰関数を使わない限りPypyで出すこと

    n = int(input())
    ns = str(n)
    k = int(input())
    keta = len(ns)

    if keta < k:
        print(0)
        exit(0)

        # dp[i+1][smaller][j]=i桁目までで、未満フラグをsmaller、0の個数j
    dp = [[[0]*(keta+1) for i in range(2)]
          for j in range(keta + 1)]

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

    for i in range(keta):
        for smaller in range(2):
            for j in range(i+1):
                for x in range(10 if smaller == 1 else int(ns[i])+1):
                    # if i == 0 and x == 0:
                    #    continue
                    dp[i + 1][1 if smaller == 1 or x < int(ns[i])
                              else 0][j if x != 0 else j+1] += dp[i][smaller][j]
    # print(dp)
    # print(dp[keta][0][keta-k])
    #print(dp[keta][1][keta - k])
    print(dp[keta][0][keta-k]+dp[keta][1][keta - k])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod



N = int(input())
K = int(input())
SN = str(N)
LN = list(SN)
keta =len(LN)
Nzer = keta-K
Nsei = K
output = 0
if keta>=K:
    output += comb(keta,K,10**9+7)*9**K
    t = 0
    s = 0
    while (s<=K-1)and(t<=keta-1):
        if LN[t]!="0":
            output -= (9-int(LN[t]))*comb(keta-1-t,K-1-s,10**9+7)*9**(K-1-s)
            t += 1
            s += 1
        elif LN[t]=="0":
            output -= (9-int(LN[t]))*comb(keta-1-t,K-1-s,10**9+7)*9**(K-1-s)
            t+=1
print(int(output))

Submission status: Accepted

Solution code:
tmp=input()
n=int(tmp)
l=len(tmp)
k=int(input())
if k==1:
    ans=9*(l-1)
    last=int(tmp[0])
    ans+=last
    print(ans)
    exit()
if k==2:
    c=l-2
    ans=(9**2)*((c*(c+1))//2)
    num=0
    for i in range(1,l):
        for head_i in range(9,0,-1):
            for tail_i in range(9,0,-1):
                cal=str(head_i)
                cal+="0"*len(tmp[1:i])
                cal+=str(tail_i)
                cal+="0"*len(tmp[i+1:])
                if int(cal)<=n:
                    num+=1
    
    ans+=num
    print(ans)
    exit()


c=0
for i in range(3,l):
    c+=(i-1)*(i-2)//2
ans=(9**3)*c
num=0
for i in range(1,l):
    for j in range(i+1,l):
        for f_i in range(1,10):
            if f_i<int(tmp[0]):
                num+=81
                continue
            for s_i in range(1,10):
                for t_i in range(1,10):
                    cal=f_i*(10**(l-1))+s_i*(10**(l-1-i))+t_i*(10**(l-1-j))
                    if cal<=n:
                        num+=1
ans+=num
print(ans)

Submission status: Accepted

Solution code:
import itertools, math

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    return (math.factorial(n) // math.factorial(r)) // math.factorial(n-r)

def ans_when_K1(N):
    max_digit = len(str(N))
    return 9 * (max_digit-1) + int(str(N)[0])

def ans_when_K2(N):
    max_digit = len(str(N))
    if max_digit < 2:
        return 0

    digit = 2
    ans = 0
    while digit < max_digit:
        ans += 9 * (digit-1) * 9
        digit += 1

    second_non_zero_idx = -1
    for i in range(1, max_digit):
        if str(N)[i] != "0":
            second_non_zero_idx = i
            break

    ans += (int(str(N)[0]) -1) * (digit-1) * 9
    if second_non_zero_idx != -1:
        ans += ans_when_K1(int(str(N)[second_non_zero_idx:]))
    return ans

def ans_when_K3(N):
    max_digit = len(str(N))
    if max_digit < 3:
        return 0

    digit = 3
    ans = 0
    while digit < max_digit:
        ans += 9 * cmb(digit-1, 2) * 9 * 9
        digit += 1

    second_non_zero_idx = -1
    for i in range(1, max_digit):
        if str(N)[i] != "0":
            second_non_zero_idx = i
            break

    ans += (int(str(N)[0]) -1) * cmb(digit-1, 2) * 9 * 9
    if second_non_zero_idx != -1:
        ans += ans_when_K2(int(str(N)[second_non_zero_idx:]))
    return ans

if K == 1:
    print(ans_when_K1(N))
elif K == 2:
    print(ans_when_K2(N))
else:
    print(ans_when_K3(N))

Submission status: Accepted

Solution code:
import math

def Comb(n, r):
  if n < r:
    return 0
  else:
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

N = input()
K = int(input())
ans = 0
for i in range(1, len(N)):
  if i < K:
    pass
  else:
    ans += 9 ** K * Comb(i-1, K-1)
ans += (int(N[0])-1) * Comb(len(N)-1, K-1) * 9 ** (K-1)
if K == 1:
  ans += 1
elif K == 2:
  for i in range(1, len(N)):
    if N[i] != '0':
      ans += int(N[i]) + 9 * (len(N) - i - 1)
      break
else:
  for i in range(1, len(N)):
    if N[i] != '0':
      if len(N) - i - 1 >= 2:
        ans += Comb(len(N) - i - 1, 2) * 9 ** 2
      if len(N) - i - 1 >= 1:
        ans += (int(N[i]) - 1) * 9 * (len(N) - i - 1)
      for j in range(i+1, len(N)):
        if N[j] != '0':
          ans += int(N[j]) + 9 * (len(N) - j - 1)
          break
      break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(N: str, K: int):
    M = len(N)
    DP = [[[0]*2 for __ in range(K+1)] for _ in range(M+1)]
    Nstr = N

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

    for i in range(M):
        DP[i+1][0][True] = 1
        DP[i+1][0][False] = 0
        for k in range(K):
            DP[i+1][k+1][True] = DP[i][k][True]*9 + DP[i][k+1][True]*1
            if int(Nstr[i]) != 0:
                DP[i+1][k+1][True] += DP[i][k+1][False]
                DP[i+1][k+1][True] += DP[i][k][False]*(int(Nstr[i])-1)
            if int(Nstr[i]) == 0:
                DP[i+1][k+1][False] = DP[i][k+1][False]
            else:
                DP[i+1][k+1][False] = DP[i][k][False]
    print(DP[M][K][True]+DP[M][K][False])
    # print(*DP, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = str(next(tokens))  #
    K = int(next(tokens))  # type: int
    solve(N, K)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def tail(x):
	s = str(x)
	a = int(s[0]); d = len(s)
	return x - a * 10 ** (d - 1)

def K1(N):
	s = str(N)
	a = int(s[0]); d = len(s)
	res = 9 * (d - 1) + a
	return res

def K2(N):
	s = str(N)
	a = int(s[0]); d = len(s)
	res = (d - 1) * (d - 2) // 2 * 81
	res += (a - 1) * (d - 1) * 9
	res += K1(tail(N))
	return res
	
def K3(N):
	s = str(N)
	a = int(s[0]); d = len(s)
	res = (d - 1) * (d - 2) * (d - 3) // 6 * 729
	res += (a - 1) * (d - 1) * (d - 2) // 2 * 81
	res += K2(tail(N))
	return res

N = int(input())
K = int(input())
if K == 1:
	ans = K1(N)
elif K == 2:
	ans = K2(N)
elif K == 3:
	ans = K3(N)

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k = get_all_int()

# m桁の数値でf(n)=kとなる数の個数
# dp[k][m]
dp = [ [None]*101 for _ in range(4)]

for i in range(101):
    dp[0][i] = 1
dp[0][0] = 0
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0
dp[1][1] = 9
dp[2][1] = 0
dp[3][1] = 0

dp[1][2] = 1 * dp[1][1] + 9 * dp[0][1]
for i in range(2,101):
    dp[1][i] = 1 * dp[1][i-1] + 9 * dp[0][i-1]
    dp[2][i] = 1 * dp[2][i-1] + 9 * dp[1][i-1]
    dp[3][i] = 1 * dp[3][i-1] + 9 * dp[2][i-1]

# log(dp[1])
# log(dp[2])

ans = 0

keta = 0
x = n
while x > 0:
    keta += 1
    x //= 10

def sol(n, keta, k):
    if k == 0:
        return 1
    if k < 0:
        return 0
    if keta < k:
        return 0
    if keta == 0:
        return 1
    
    top = n//10**(keta-1)%10
    if keta==1:
        return top
    ans = 0
    # 0のとき
    if top == 0:
        ans += sol(n, keta-1, k)
    else:
        ans += 1 * (0 if keta==1 else dp[k][keta-1])
    # ans += sol(n, keta-1, k)
    log(keta,top,k,ans)

    # 1～top-1のとき
    if top != 0:
        if top == 1:
            ans += sol(n, keta-1, k-1)
        else:
            ans += (top-1) * (1 if keta==1 else dp[k-1][keta-1])
        # ans += (top-1) * sol(n, keta-1, k-1)
        log(keta,top,k,ans)

    # topのとき
    if top > 1:
        ans += sol(n, keta-1, k-1)
        log(keta,top,k,ans)
    return ans

if keta < k:
    print(0)
    exit()
ans += sol(n, keta, k)

print(ans)