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:
def count(keta,kazu):
    if(keta<kazu):
        return 0
    result=1
    wari=1
    for i in range(kazu):
        wari*=i+1
        result*=keta-i
    result//=wari
    #print(result)
    for i in range(kazu):
        result*=9
    return result


def Ans(moji,kazu):
    #print(moji,kazu)
    naga=len(moji)
    if(naga<kazu):
        return 0
    if(kazu==0):
        return 1
    sento=int(moji[0])
    if(naga==1):
        return sento
    #return Ans(moji[1:],kazu)+Ans(moji[1:],kazu-1)+count()
    if(sento==0):
        plus=Ans(moji[1:],kazu)
        return plus
    else:
        plus=Ans(moji[1:],kazu-1)
        #print(count(naga-1,kazu),count(naga-1,kazu-1),plus)
        return count(naga-1,kazu)+count(naga-1,kazu-1)*(sento-1)+plus

n=input()
l=len(n)
k=int(input())


print(Ans(n,k))

#ans=count(l-1,k)
#print(ans)
#batu=0
#for i in range(l):
#    suji=int(n[i])
#    if(suji!=0):
#        batu+=1
#    if(k<batu):
#        break
#    nok=count(l-i-1,k-batu)
#    print(suji,nok)
#    ans+=nok*(suji-1)

#print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, open(0).read().split())

X = str(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(X) + 1)]
dp[0][0][0] = 1

for i in range(len(X)):
    D = int(X[i])
    for j in range(2):
        for k in range(K + 1):
            for d in range((9 if j == 1 else D) + 1):
                if k + int(d != 0) <= K:
                    dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k]

print(dp[-1][-1][-1] + int(X.count("0") == len(X) - K))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
# import itertools
N = int(input())
K = int(input())

L = list(str(N))
leng = len(L)
st = int(L[0])
cnt = 0

#N(3003)と左桁数(0)をもらってOKな桁数(3)とその数値を返す
def keta(n,l):
    for i in range(l,leng):
        d = n[i]
        if d=='0':
            continue
        else:
            return (i,int(d))
    return -1,-1

if K==1:
    cnt += st
    cnt += 9*(leng-1)
elif K==2:
    i,d = keta(L,1)
    if not i==-1:
        cnt += d + 9*(leng-i-1)

    cnt += (st-1)*9*(leng-1) + 9*9*(leng-1)*(leng-2)//2
else:
    i_1,d_1 = keta(L,1)
    i_2,d_2 = keta(L,i_1+1)
    if not i_1==-1:
        a = (leng-i_1-1)
        cnt += (d_1-1)*9*a
        cnt += 9*9*(a*(a-1)//2)
    if not i_2==-1:
        cnt += d_2 + 9*(leng-i_2-1)
    cnt += (st-1)*9*9*(leng-1)*(leng-2)//2 + (9**3)*(leng-1)*(leng-2)*(leng-3)//6
print(cnt)

Submission status: Accepted

Solution code:
a = int(input())
b = int(input())
def aez(n, k):
    s = str(n)
    ln = len(s)-1
    n1 = int(s[0])
    if len(s) < k:
        return 0
    else:
        if k == 1:
            return 9 * ln + n1 
        elif k == 2:
            return (81 * ln * (ln-1) // 2) + aez(int('9'*ln), 1)*(n1-1) + aez(int(s[1:]), 1)
        else:
            return (729*ln*(ln-1)*(ln-2)//6) + aez(int('9'*ln), 2)*(n1-1) + aez(int(s[1:]), 2)
print(aez(a, b))

Submission status: Accepted

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

def solve1(n):
    l = len(n)
    if l > 0:
        return int(n[0]) + 9 * (l-1)
    else:
        return 0

def solve2(n):
    l = len(n)
    if l > 1:
        ret = (int(n[0]) - 1) * 9 * (l-1) + 9 * 9 * (l - 1) * (l - 2)  // 2
        n = n[1:]
        while (n[0] == "0"):
            if (n == "0"):
                n = ""
                break
            
            n = n[1:]
        return ret + solve1(n)
    else:
        return 0

def solve3(n):
    l = len(n)
    if l > 2:
        ret = (int(n[0])-1) * 9 * 9 * (l - 1) * (l - 2) // 2 + 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6
        n = n[1:]
        while (n[0] == "0"):
            
            if (n == "0"):
                n = ""
                break
            n = n[1:]
        return ret + solve2(n)
    else:
        return 0

if k == 1:
    print(solve1(n))
elif k == 2:
    print(solve2(n))
else:
    print(solve3(n))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from functools import lru_cache


def cmb(n, r):
    # combination
    if n < 1 or r < 0:
        return 0
    if n < r:
        return 0
    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


@lru_cache(maxsize=None)
def solve(N, k):
    if len(N) > 1 and N[0] == "0":
        return solve(N[1:], k)
    n = int(N)
    if k < 0:
        return 0
    elif len(N) < k:
        return 0
    elif n == 0:
        if k == 0:
            return 1
        elif k > 0:
            return 0
    elif n < 10:
        if k == 1:
            return n
        elif k == 0:
            return 1

    a = solve(N[1:], k - 1)
    b = (int(N[0]) - 1) * cmb(len(N) - 1, k - 1) * int(9**(k - 1))
    c = cmb(len(N) - 1, k) * int(9**k)
    # print(N, k, a, b, c)
    return a + b + c


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

L = len(str(N))

# print(ans)
print(solve(str(N), K))

Submission status: Accepted

Solution code:
N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if m < K:
        return ans
    else:
        if K == 1:
            y = Z[0]
            ans += (m-1) * 9 + y
            #print(ans)
        elif K == 2:
            #0 
            ans += ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * (m-1) * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break            
            ans += nn(Z,K,m)
            #print(ans)
        elif K == 3:
            #0 
            ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break
            ans += nn(Z,K,m)
        return ans
if len(str(N)) < K:
    ans = 0
else:
    ans = nn(Z,K,m)        
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys


def count(n):
    c = 0
    for s in str(n):
        if s != "0":
            c += 1
    return c


@lru_cache()
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)


def C(i, j):
    return fact(i) // (fact(j) * fact(i - j))


def calc(N, K):
    if K==0:
        return 1
    if N < 10000:
        retval = 0
        for i in range(N + 1):
            if count(i) == K:
                retval += 1
        return retval

    keta = len(str(N))
    retval = C(keta - 1, K) * (9**K)
    retval += calc(int(str(N)[1:]),K-1)
    retval += (int(str(N)[0])-1)*calc(10**(keta-1)-1,K-1)
    return retval



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

print(calc(N,K))

Submission status: Accepted

Solution code:
def main():
    N = input()
    len_N = len(N)
    K = int(input())
    dp = [[[0] * (K+5) for _ in range(2)] for _ in range(len_N + 5)]
    dp[0][0][0] = 1
    for i in range(1,len_N+1):
        for smaller in range(2):
            for k in range(K+1):
                if smaller == 0:
                    for x in range(int(N[i-1])+1):
                        if int(N[i-1]) == x:
                            if x == 0:
                                dp[i][smaller][k] += dp[i-1][smaller][k]
                            else:
                                dp[i][smaller][k+1] += dp[i-1][smaller][k]
                        else:
                            if x == 0:
                                dp[i][1][k] += dp[i-1][smaller][k]
                            else:
                                dp[i][1][k+1] += dp[i-1][smaller][k]
                else:
                    for x in range(10):
                        if x == 0:
                            dp[i][smaller][k] += dp[i-1][smaller][k]
                        else:
                            dp[i][smaller][k+1] += dp[i-1][smaller][k]


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







if __name__ == "__main__":
    main()

Submission status: Accepted

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

l = len(str(N))
"""
print("N=",N)
print("K=",K)
print("l=",l,"桁")
"""
#l桁の数字

if K == 1:
    y = 9*(l-1)
    for i in range(1,10):
        p = i*10**(l-1)
        # print(p)
        if p <= N:
            y += 1
        else:
            break
    print(y)
    
elif K == 2:
    # print("mode 2")
    #l-1桁まででNより小さい数の個数
    y = 81*(l-1)*(l-2)//2
    # print(y)
    
    #l桁の数
    for i in range(1,int(str(N)[0])+1):
        for j in range(1,10):
            for k in range(l-1):
                # print(i,j,k)
                p = int(str(i)+"0"*k+str(j)+"0"*(l-2-k))
                if p <= N:
                    y += 1
                # print(p)
    print(y)

else:
    # print("mode 3")
    #l-1桁まででNより小さい数の個数
    y = 729*(l-1)*(l-2)*(l-3)//6
    # print(y)
    
    #l桁の数で頭の数がNのそれより小さい場合
    top = int(str(N)[0])
    y += (top-1)*81*(l-1)*(l-2)//2
    
    #l桁の数(頭の数字はNと一緒)
    for j in range(1,10):
        for k in range(1,10):
            for m in range(l-2):
                for n in range(l-2-m):
                    # print(m,n,l-3-m-n)
                    p = int(str(top)+"0"*m+str(j)+"0"*n+str(k)+"0"*(l-3-m-n))
                    if p <= N:
                        y += 1
                    # print("p:",p)
    print(y)

Submission status: Accepted

Solution code:
def calc(n,k):
    while n[0] == '0' and len(n)>1:
        n=n[1:]
    
    digit = len(n)
    if digit < k:
        return 0
    
    comb = [1]*(k+1)
    for i in range(1,k+1):
        comb[i] = comb[i-1] * (digit-i) //i
    if k==1:
        return 9*comb[1] + int(n[0])
    elif k==2:
        return (9**2)*comb[2] + (int(n[0])-1) * 9*comb[1] + calc(n[1:],1)
    elif k==3:
        return (9**3)*comb[3] + (int(n[0])-1) * (9**2) * comb[2] + calc(n[1:],2)

n=input()
k=int(input())
print(calc(n,k))

Submission status: Accepted

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

digit_length = len(N_str)
topmost_digit = int(N_str[0])

C_table = [[0, 0, 0, 0] for _ in range(digit_length+10)]


def C(all, pick):
    if C_table[all][pick] == 0:
        count_child = 1
        count_parent = 1
        for i in range(pick):
            count_child *= all - i
            count_parent *= i + 1
        C_table[all][pick] = count_child // count_parent
    return C_table[all][pick]


def get_count(top_digit, digit_count, needed_nonzero):
    if needed_nonzero <= 0 or needed_nonzero > digit_count:
        return 0

    if digit_count == 1:
        if needed_nonzero == 1:
            return top_digit
        else:
            return 0

    if top_digit == 0:
        return get_count(int(N_str[digit_length - digit_count + 1]) ,digit_count - 1, needed_nonzero)

    if top_digit >= 1:
        count = C(digit_count - 1, needed_nonzero) * (9 ** needed_nonzero)
        if needed_nonzero == 1:
            count += 1

    if top_digit > 1:
        count += C(digit_count - 1, needed_nonzero - 1) * (9 ** (needed_nonzero - 1)) * (top_digit - 1)

    return count + get_count(int(N_str[digit_length - digit_count + 1]) ,digit_count - 1, needed_nonzero - 1)


print(get_count(topmost_digit, digit_length, K))

Submission status: Accepted

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

Nlen = len(N)

def func(N, K):
    Nlen = len(N)
    ans = 0
    if K == 1:
        ans += (Nlen - 1) * 9
        ans += int(N[0])
    if K == 2:
        for i in range(1, Nlen - 1):
            ans += 9 * 9 * i
        ans += (int(N[0]) - 1) * 9 * (Nlen - 1)
        for i in range(1, len(N)):
            if not N[i] == '0':
                ans += func(N[i:], 1)
                break
    if K == 3:
        for i in range(2, Nlen - 1):
            ans += 9 * 81 * i * (i - 1) // 2
        ans += (int(N[0]) - 1) * 81 * (Nlen - 1) * (Nlen - 2) // 2
        for i in range(1, len(N)):
            if not N[i] == '0':
                ans += func(N[i:], 2)
                break
    return ans
    
print(func(N, K))

Submission status: Accepted

Solution code:
N = list(map(int,input()))
K = int(input())
L = len(N)

def comb(n,k):
    if n < 0 or k < 0 or k > n:
        return 0
    ans = 1
    for i in range(k):
        ans *= n-i
    for i in range(k):
        ans //= i+1
    return ans

i = 0
D = [0] * K
M = K
for k in range(K):
    while i < L and N[i] == 0:
        i += 1
    if i < L:
        D[k] = i
        i += 1
    else:
        M = k
        break

ans = 0
for k in range(M):
    i = D[k]
    ans += comb(L-1-i,K-k)*(9**(K-k))
    ans += (N[i]-1) * comb(L-1-i,K-1-k)*(9**(K-1-k))
if K == M:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
l = len(str(N))
K = int(input())
def calc(a, b, c):
    t = 0
    if a-b-1>=0:
        t = (math.factorial(a-1) // (math.factorial(a-b-1) * math.factorial(b)))*(9**(b))
    if b==1:
        t2 = int(str(c)[0])
    else:
        t2 = (math.factorial(a-1) // (math.factorial(a-b) * math.factorial(b-1)))*(9**(b-1))*(int(str(c)[0])-1)
    t3 = 0
    try:
        n = int(str(c)[1:])
        if 2<=b<=len(str(n))+1:
            t3 = calc(len(str(n)), b-1, n)
    except:
        pass
    return t+t2+t3

if l>=K:
    print(calc(l, K, N))
else:
    print(0)

Submission status: Accepted

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

cmb = [[0]*(101) for _ in range(101)]
cmb[0][0] = 1
for i in range(1, 101):
    for j in range(i+1):
        if j == 0:
            cmb[i][j] = 1
            continue
        cmb[i][j] = cmb[i-1][j-1]+cmb[i-1][j]

S = str(N)
ans = 0
if K == len(S):
    for i in range(K):
        ans += (int(S[i])-1)*9**(K-i-1)
    ans += 1
else:
    for i in range(K, len(S)):
        ans += 9*cmb[i-1][K-1]*9**(K-1)
    if K == 1:
        ans += int(S[0])
    if K == 2:
        ans += (int(S[0])-1)*(len(S)-1)*9
        i = 1
        while i < len(S) and S[i] == "0":
            i += 1
        if i < len(S):
            ans += (len(S)-1-i)*9
            ans += int(S[i])
    if K == 3:
        ans += (int(S[0])-1)*cmb[len(S)-1][K-1]*9**(K-1)
        i = 1
        while i < len(S)-1 and S[i] == "0":
            i += 1
        flag = True
        if i < len(S)-1:
            ans += cmb[len(S)-i-1][2]*9**2
            ans += (int(S[i])-1)*(len(S)-i-1)*9
        else:
            flag = False
        i += 1
        while i < len(S) and S[i] == "0":
            i += 1
        if i < len(S) and flag:
            ans += (len(S)-i-1)*9
            ans += int(S[i])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
import math
def k1(n):
    if n < 10:
        ans = n
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = 9 * (len(n1) - 1) + n2
    return int(ans)

def k2(n):
    if n < 100:
        ans = n - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (81 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 3)) / 2) +  (n2 - 1) * k1(10 ** (len(n1) - 1) - 1) + k1(n - n2 * 10 ** (len(n1) - 1))
    return int(ans)

def k3(n):
    if n < 1000:
        ans = n - k2(n) - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (729 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 4)) / 6) + (n2 - 1) * k2(10 ** (len(n1) - 1) - 1) + k2(n - n2 * 10 ** (len(n1) - 1))
    return int(ans)

if k == 1:
    print(k1(n))
elif k == 2:
    print(k2(n))
else:
    print(k3(n))

Submission status: Accepted

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



def choose(n, k):
    if k == 1:
        return n
    if k == 2:
        return n * (n-1) // 2
    if k == 3:
        return n * (n-1) * (n-2) // 6
    #print(f'choosing... k is {k}!')

def nonzerodigs(n):
    ss = list(map(int, list(str(n))))
    ss = [s for s in ss if s != 0]
    return len(ss)


def count(n, k):
    #print(f'count({n}, {k})')
    if k == 0:
        return 1

    if n < 1000:
        cnt = 0
        for i in range(1, n+1):
            if nonzerodigs(i) == k:
                cnt += 1

        return cnt

    ns = list(map(int, list(str(n))))
    d = len(ns)
    top3 = ns[0] * 100 + ns[1] * 10 + ns[2]
    cnt = 0
    for i in range(top3):
        nn = nonzerodigs(i)
        if nn > k:
            continue
        kk = k - nn
        if kk == 0:
            cnt += 1
        else:
            cnt += choose(d-3, kk) * (9**kk)

    nn = nonzerodigs(top3)
    if nn > k:
        return cnt
    elif nn == k:
        cnt += 1
        return cnt
    elif nn < k:
        kk = k - nn
        if kk > 2:
            print("ERROR")
            return -1
        nnn = int("".join(map(str, ns[3:])))
        return cnt + count(nnn, kk)

print(count(n,k))

Submission status: Accepted

Solution code:
def nCk(n, k):
  return factorial(n)/factorial(n-k)/factorial(k)

from math import factorial
N = input()
K = int(input())
order = len(N)
diff = order - K 
if order < K:
  print(0)
else:
  s = int(N[0])
  #lower  = factorial(order-1)/factorial(diff-1)/ factorial(K) * (9**K)
  if order - 1 >= K:
    lower = nCk(order - 1, K) * (9**K)
  else:
    lower = 0
  total = lower
  for i in range(1, s):
  #  total += factorial(order-1)/factorial(diff)/ factorial(K-1) * (9**(K-1))
    total += nCk(order - 1, K - 1) * (9**(K-1))

  if K == 1:
    total += 1
  elif K == 2:
    under = int(N[1:])
    num = "0"*(order -1)
    for k in range(order - 1):
      for kk in range(1, 10):
        tmp = num[:k] + str(kk) + num[k+1:]
        if int(tmp) <= under:
          total += 1
  elif K == 3:
    under = int(N[1:])
    num = "0"*(order -1)
    for k in range(1, order - 1):
      for j in range(k):
        for kk in range(1, 10):
          for jj in range(1, 10):
            tmp = num[:j] + str(jj) + num[j+1:k] +str(kk) +  num[k+1:]
            if int(tmp) <= under:
              total += 1


  print(int(total))
  #pattern = factorial(order)/factorial(diff)/ factorial(K) * (9**K)

Submission status: Accepted

Solution code:
import numpy as np

def tmp(n,k):
    l = len(str(n))-1
    num = 0
    if(k == 1):
        num = 9 * l
        p = n // 10**l
        num += p
    elif(k == 2):
        for i in range(1,l):
            num += i * 81
        p = n // 10**l
        r = n % 10**l
        t = (n-r-1) % 10**(l)
        num += (p-1) * tmp(t,1) + tmp(r,1)
    elif(k == 3):
        for i in range(2,l):
            num += i * (i-1) / 2 * 729
        p = n // 10**l
        r = n % 10**l
        t = (n-r-1) % 10**(l)
        num += (p-1) * tmp(t,2) + tmp(r,2)
    return(num)



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


print(int(tmp(N,K)))

Submission status: Accepted

Solution code:
def comb(n,k):
  if k==0:
    return 1
  if k==1:
    return n
  if k==2:
    return n*(n-1)//2
  if k==3:
    return n*(n-1)*(n-2)//6
  return None
def cnt(n,k):
  if k==0:
    return 1
  if k>len(n):
    return 0
  return (comb(len(n)-1,k)*9**k
          +(int(n[0])-1)*comb(len(n)-1,k-1)*9**(k-1)
          +cnt(n[1:].lstrip('0'),k-1))
def main():
  n=input()
  k=int(input())
  print(cnt(n,k))
main()

Submission status: Accepted

Solution code:
def combination(n, k, mod=10**9+7):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % mod
    d = 1
    for x in range(1, k+1):
        d = (d * x) % mod
    comb *= pow(d, mod-2, mod)
    return comb % mod

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

x = [0] * 101
i = 0
NN = N
while NN > 0:
    x[i] = NN % 10
    NN = NN // 10
    i += 1

ans = 0
sum_non0 = 0
rK = K
for j in reversed(range(i)):
    if x[j] == 0:
        continue
    # 0 ~ 10^j
    _ans = combination(j, rK) * (9 ** rK)
    #print(j, _ans)
    if rK != 1:
        _ans += (x[j] - 1) * combination(j, rK-1) * (9 ** (rK - 1))
        #print(j, _ans)
    else:
        _ans += x[j]
        #print(j, _ans)

    ans += _ans
    rK -= 1
    if rK == 0:
        break

print(ans)

Submission status: Accepted

Solution code:
''' بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ '''
#codeforces
gi = lambda : list(map(int,input().split()))
s = input()
n, = gi()
ans = 0
mag = len(s) - 1
#corner cases:
if len(s) <= 7:
	s = int(s)
	for k in range(s + 1):
		if len(str(k)) - str(k).count("0") == n:
			ans += 1
	print(ans)
	exit()
while mag - n >= 0:
	a = 9
	b = 1
	c = 1
	if n > 2:
		c = 81 * ((mag - 1) * (mag - 2) // 2)
	elif n > 1:
		b = 9 * (mag - 1)
	ans += a * b * c
	#print(mag, a, b, c, ans)
	mag -= 1
mag = len(s)
a = int(s[0]) - 1
b, c = 1, 1
if n > 2:
	c = 81 * ((mag - 1) * (mag - 2) // 2)
elif n > 1:
	b = 9 * (mag - 1)
ans += a * b * c
a = b = c = 1
if n == 1:
	print(ans + 1)
	exit()
if n > 1:
	i = -1
	for k in range(1, len(s)):
		if s[k] != "0":
			i = k
			break;
	if i != -1:
		a = int(s[i]) - 1
		if n > 2:
			b = len(s) - i - 1
			b *= 9
		ans += a * b
		a = b = 1
		if n > 2:
			x = len(s) - i - 1
			a = 81 * (x * (x - 1)) // 2
		else:
			a = 9 * (len(s) - i - 1)
		ans += a
	if n > 2:
		a = b = c = 1
		j = -1
		for k in range(i + 1, len(s)):
			if s[k] != "0":
				j = k
				break;
		if j != -1:
			ans += 9 * (len(s) - j - 1) + int(s[j])
	else:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def comb(n, k):
    if n == 0 or k == 0:
        return 1
    ret = 1
    for i in range(k):
        ret *= (n - i)
        ret //= (i + 1)
    return ret

def rec(S, K):
    #print(S, K)
    N = len(S)
    if N == 0 or K == 0 or N < K:
        return 0
    h = int(S[0])
    c = comb(N - 1, K - 1)
    ret = (9 - h) * c * (9 ** (K - 1))
    if S[0] == '0':
        ret += rec(S[1:], K)
    else:
        ret += rec(S[1:], K - 1)
    #print(S, K, ret)
    return ret

def solve(S: str, K: int):
    N = len(S)
    if N < K:
        print(0)
        return 0
    ret = comb(N, K) * (9 ** K)
    ret -= rec(S, K)
    print(ret)
    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:
# does not contain more than K non 
# zero digits 
  
# This function returns the count of 
# required numbers from 0 to num 
def countInRangeUtil(pos, cnt, tight, num): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt <= K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x): 
    global dp, K, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  
# Driver Code 
if __name__ == "__main__": 
  
    # states - position, count, tight 
    dp = [] 
    M = 100
  
    # K is the number of non zero digits 
    K = 0
  
    L = 1
    R = int(input())
    K = int(input())
    a=countInRange(R)
    K=K-1
    b=countInRange(R)
    print(a-b)

Submission status: Accepted

Solution code:
from math import factorial
N=int(input())
K=int(input())
S=list(map(int,str(N)))

def C(n,r):
  if n>=r:
    return factorial(n)//factorial(r)//factorial(n-r)
  else:
    return 0

def D(i,j):
  return C(i,j)*(9**j)

ans=0
l=len(S)
for i in range(l):
  if S[i]!=0:
    ans+=(S[i]-1)*D(l-1,K-1)+D(l-1,K)
    l-=1
    K-=1
  else:
    l-=1
  if K==0:
    ans+=1
    break
    
print(ans)

Submission status: Accepted

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

r = 0
tp = n
while tp != 0:
    r += 1
    tp = tp//10

p = n//pow(10,r-1)

res = 0

if k == 1:
    res = (r-1)*9 + p
    print(res)

elif k == 2:
    if r <= 1:
        print(0)
        exit()
    if r >= 3:
        res = (r-1)*(r-2)*81//2
    
    res += (p-1)*9*(r-1)

    tmp = p*pow(10,r-1)
    for i in range(r-1):
        for j in range(1,10):
            if tmp + j*pow(10,i) <= n:
                res += 1
    
    print(res)
else:
    if r <= 2:
        print(0)
        exit()
    
    if r >= 4:
        res = pow(9,3)*(r-1)*(r-2)*(r-3)//6
    
    res += (p-1)*81*(r-1)*(r-2)//2

    tmp = p*pow(10,r-1)

    for i in range(r-1):
        for j in range(i+1,r-1):
            for w in range(1,10):
                for q in range(1,10):
                    if tmp + w*pow(10,i) + q*pow(10,j) <= n:
                        res += 1
    
    print(res)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def f1(ss):
	return (len(ss)-1)*9

def f2(ss):
	ll=len(ss)
	return (((ll-1)*(ll-2))//2)*9*9
	
def f3(ss):
	ll=len(ss)
	return (((ll-1)*(ll-2)*(ll-3))//6)*9*9*9
	
def fk1(ss):
	aa=int(ss[0])
	return aa+f1(ss)
	
def fk2(ss):
	aa=int(ss[0])
	ret=f2(ss)
	ret+=(aa-1)*f1(ss)
	for i, c in enumerate(ss):
		if i == 0:
			continue
		if int(c)>0:
			ret += fk1(ss[i:])
			break
	return ret
	
def fk3(ss):
	aa=int(ss[0])
	ret = f3(ss)
	ret += (aa-1)*f2(ss)
	for i, c in enumerate(ss):
		if i == 0:
			continue
		if int(c)>0:
			ret += fk2(ss[i:])
			break
	return ret	

def main():
	n = input()
	k = int(input())
	if k== 1:
		return fk1(n)
	elif k==2:
		return fk2(n)
	else:
		return fk3(n)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import math
def C(a,b):
    return math.factorial(a) // (math.factorial(b)*math.factorial(a-b))

def count(N, K):
    if K == 0:
        return 1
    if N == 0:
        return 0
    keta = int(math.log10(N)) + 1
    if keta < K:
        return 0
    elif keta == K:
        if K == 1:
            return N
        elif K == 2:
            return (N//10 - 1) * 9 + N % 10
        else:
            return (N//100 - 1) * 81 + ((N//10)%10 - 1) * 9 + N % 10
    else:
        keta1 = (N//(10**(keta-1)))%10
        ans = C(keta - 1, K) * (9**K)
        ans += (keta1 - 1) * C(keta-1, K-1) * (9**(K-1))
        ans += count(N-(keta1*(10**(keta-1))), K-1)
        return ans

N = int(input())
K = int(input())
print(count(N,K))

Submission status: Accepted

Solution code:
"""
E
"""
import sys
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


N=list(input())
N=list(map(int,N))
K=int(input())

L=len(N)
if L<K:
    print(0)
    sys.exit()
ans=0
if L>K:
    ans+=cmb(L-1,K)*(9**K)
ans+=(N[0]-1)*cmb(L-1,K-1)*(9**(K-1))


if K==1:
    ans=(L-1)*9+N[0]
    
elif K==2:
    H=[0]*L
    H[0]=N[0]
    for i in range(1,L):
        for j in range(1,10):
            H[i]=j
            if N>=H:
                ans+=1
        H[i]=0
    
else:
    H=[0]*L
    H[0]=N[0]
    for i in range(1,L-1):
        for k in range(1,10):
            H[i]=k
            for j in range(i+1,L):
                for l in range(1,10):
                    H[j]=l
                    if N>=H:
                        ans+=1
                H[j]=0
        H[i]=0
print(ans)

Submission status: Accepted

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


def f(n, d, k):
    if k == 0:
        return 1
    if d == 1:
        return int(n) if k == 1 else 0
    msb = int(n[0])
    if msb == 0:
        return f(n[1:], d - 1, k)
    return f(n[1:], d - 1, k - 1) + (msb - 1) * f('9' * (d - 1), d - 1, k - 1) + f('9' * (d - 1), d - 1, k)


print(f(N, len(N), K))

Submission status: Accepted

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

ln = len(N)

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

for i in range(1, ln + 1):
    for j in range(2):
        for k in range(4):
            num = int(N[i-1])
            if j:
                l_mx = 9
            else:
                l_mx = num

            for l in range(l_mx + 1):
                if l == 0:
                    dp[i][j or l < num][k] += dp[i-1][j][k]
                else:
                    if k > 0:
                        dp[i][j or l < num][k] += dp[i-1][j][k-1]

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

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
m = n
l = []
while m > 0:
    l.append(m%10)
    m //= 10

try:
  n_ = n-(l[-1]*10**(len(l)-1))
  m_ = n_
  l_ = []
  while m_ > 0:
      l_.append(m_%10)
      m_ //= 10

  n__ = n_-(l_[-1]*10**(len(l_)-1))
  m__ = n__
  l__ = []
  while m__ > 0:
      l__.append(m__%10)
      m__ //= 10
except:
  pass
      
def d1(lst):
  ans = 0
  for num,i in enumerate(lst):
    if num != (len(lst)-1):
      ans += 9
    else:
      ans += i
  return ans

def d2(lst,lst_):
  ans = 0
  for num,i in enumerate(lst):
    if num != (len(lst)-1):
      ans += 81*num
    else:
      ans += (i-1)*9*num+d1(lst_)
  return ans

def d3(lst,lst_,lst__):
  ans = 0
  for num,i in enumerate(lst):
    if num != (len(lst)-1):
      ans += 729*(num-1)*num//2
    else:
      ans += (i-1)*81*(num-1)*num//2+d2(lst_,lst__)
  return ans

if k ==  1:
  print(d1(l))
if k ==  2:
  print(d2(l,l_))
if k ==  3:
  print(d3(l,l_,l__))