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 collections import Counter
N=input()
K=int(input())
km = len(N)
res = 0
if int(N)<=1000:
    for i in range(int(N)):
        c = Counter(str(i+1))
        if len(str(i+1)) - c['0']==K:
            res += 1
    print(res)
    exit()
d = [[0]*3 for _ in range(100001)]
for i in range(100000):
    d[i+1] = d[i][:]
    c = Counter(str(i+1))
    k=len(str(i+1)) - c['0']
    if k<=3:
        d[i+1][k-1] += 1
def rec(n,k):
    re = 0
    if int(n)<100000:
        re = 0
        return d[int(n)][k-1]
    if k==1:
        n = str(int(n))
        return 9*(len(n)-1)+int(n[0])
    t = ''.join(['9']*(len(n)-1))
    t2 = t
    w = (int(n[0])-1)
    if n[0] == '0':
        t2 = n[1:]
        w = 0
    return rec(t2, k) + w*rec(t2, k-1) + rec(str(int(n[1:])), k-1)
print(rec(N,K))

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
A = 0
if N <= 100000:
    for i in range(1,N+1):
        c = str(i)
        d = len(c) - c.count('0')
#    print(i,c,d,len(c),c.count('0'))
        if d == K:
            A += 1
else:
    keta = len(str(N))
    if K ==1:
        A = 9*(keta-1)
    if K ==2:
        A = 9*9*(keta-1)*(keta-2)//2
    if K ==3:
        A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
    nc = 1
#    print(N,K,keta,A)
    while nc <= 3 and keta >=1:
        # abcd... -> 1000000 - a0000000
        T = N//(10**(keta-1))%10
#        print(T,nc)
        if T == 0:
            keta -=1
        else:
            if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
              A = A + (T)
            if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
                A = A + int((T-1)*9*(keta-1))
            if (nc==2 and K==2) or (nc==3 and K==3):
                A = A + 9*(keta-1)
            if (nc==1 and K ==3):
                A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
            if (nc==2 and K==3):
                A = A + int(9*9*(keta-1)*(keta-2)/2)
            nc +=1
            keta -=1
#        print(A)
        
print(A)

Submission status: Accepted

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

S=input()
K=II()
DP=[[[0]*len(S) for _ in range(K+1)] for _ in range(2)]

for i in range(int(S[0])+1):
    if i < int(S[0]) and i > 0:
        DP[1][1][0] += 1
    elif i == 0:
        DP[1][0][0] = 1
    else:
        DP[0][1][0] = 1

for i in range(1, len(S)):
    n = int(S[i])
    DP[1][0][i] = DP[1][0][i-1]
    for j in range(K):
        DP[1][j+1][i] = (
            # 0の場合
            DP[1][j+1][i-1] +
            # 0以外の場合
            9*DP[1][j][i-1])
        if n != 0:
            DP[1][j+1][i] += (n-1)*DP[0][j][i-1]
            DP[0][j+1][i] = DP[0][j][i-1]

    for j in range(K+1):
        if n != 0:
            DP[1][j][i] += DP[0][j][i-1]
        else:
            DP[0][j][i] = DP[0][j][i-1]

print(DP[1][K][len(S)-1] + DP[0][K][len(S)-1])

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools

# ひとつ入力
n = int(input())
# ひとつ入力
k = int(input())

a=n
p=0
nn=[]
while a>0:
    p+=1
    r=a%10
    nn.insert(0,r)
    a=a//10
#print(p)


dp0=np.zeros((p+1,k+2),dtype="int64")
dp1=np.zeros((p+1,k+2),dtype="int64")
#print(dp0,dp1)
dp1[0][0]=1
for i in range(p):
    for j in range(k+1):
        dp0[i+1][j]    += dp0[i][j] + dp1[i][j] * (nn[i]>0)
        dp0[i+1][j+1]  += dp0[i][j] * 9 + dp1[i][j] * max(nn[i]-1,0)
        dp1[i+1][j]    += dp1[i][j] * (nn[i]==0)
        dp1[i+1][j+1]  += dp1[i][j] * (nn[i]!=0)
        

answer=dp0[p][k]+dp1[p][k]
#print(nn)
#print(dp0,dp1)
print(answer)

Submission status: Accepted

Solution code:
N = input().strip()
n = len(N)
A = [0 for _ in range(n)]
A[0]=1
for i in range(1,n):
    if N[i]=="0":
        A[i] = A[i-1]
    else:
        A[i] = A[i-1]+1
K = int(input())
if K>n:
    print(0)
else:
    dp = [[[0 for _ in range(n+1)] for _ in range(2)] for _ in range(n+1)]
    dp[0][0][0] = 1
    for i in range(1,n+1):
        for k in range(n+1):
            if k==A[i-1]:
                dp[i][0][k] = 1
                break
    for i in range(1,n+1):
        for k in range(n+1):
            dp[i][1][k] = dp[i-1][1][k]
            if int(N[i-1])>0:
                dp[i][1][k] += dp[i-1][0][k]
            if k>=1:
                dp[i][1][k] += dp[i-1][1][k-1]*9
                if i==1 and k-1==0 and int(N[i-1])>=2:
                    dp[i][1][k] += dp[i-1][0][k-1]*(int(N[i-1])-1)
                elif i>=2 and k-1==A[i-2] and int(N[i-1])>=2:
                    dp[i][1][k] += dp[i-1][0][k-1]*(int(N[i-1])-1)
    print(dp[n][0][K]+dp[n][1][K])

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**3)

import math

n = 0
k = 0

def format_input(filename = None):
	global n
	global k
	if filename == None:
		n = list(map(int, input().split())).pop()
		k = list(map(int, input().split())).pop()

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 10**100)
		k = rng(1, 3)

@lru_cache(maxsize=None)
def comb_rec(n, k, digits):
	if digits < k - 1:
		return 0
	if k == 0:
		return 1
	if digits == 0:
		return n
	top = n // 10 ** digits
	if top == 0:
		combination = comb_rec(n, k, digits - 1)
	elif top == 1:
		combination = comb_rec(n - 10 ** digits, k - 1, digits - 1)
		combination += comb_rec(10 ** digits - 1, k, digits - 1)
	else:
		combination = comb_rec(n - top * 10 ** digits, k - 1, digits - 1)
		combination += (top - 1) * comb_rec(10 ** digits - 1, k - 1, digits - 1)
		combination += comb_rec(10 ** digits - 1, k, digits - 1)
	return combination


def get_answer():
	digits = math.floor(math.log10(n))
	answer = comb_rec(n, k, digits)
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

Solution code:
''' Hey stalker :) '''
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    n = list(input())
    k = get_int()
    ln = len(n)
    ans = 0
    def solve(nz, ind, locked = False):
        if nz == 0: return 1
        if ind>=ln: return 0
        num = int(n[ind])
        ans = 0
        for index in range(ind,ln):
            if locked and ind==index:
                if nz==1: ans += 1
                else:
                    for i in range(index+1, ln):
                        if int(n[i])>0:
                            ans += solve(nz-1, i, True)
                            break
                ans += solve(nz-1, index+1)*(num-1)
            else: ans += solve(nz-1, index+1)*9
            #print(index, ans)
        #print(nz, ind, locked, ans)
        return ans

    ans = solve(k,0, True)
    print(ans)


''' Pythonista fLite 1.1 '''
import sys
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right
#from functools import reduce
import math
#input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()
#[main() for _ in range(int(input()))]
print(*out, sep='\n')

Submission status: Accepted

Solution code:
strN = input()
N = int(strN)
K = int(input())
ans = 0
lenN = len(strN)
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    if lenN >= 2:
        index = 1
        while (index < lenN):
            if int(strN[index]) != 0:
                ans += 9 * (lenN - 1 - index)
                ans += int(strN[index])
                break
            index += 1
        ans += (int(strN[0]) - 1) * 9*(lenN-1)

        ans += 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)


elif K == 3:
    if lenN >= 3:
        index = 1
        index_2 = 0
        while (index < lenN and index_2 == 0):
            if int(strN[index]) != 0:
                ans += (int(strN[index]) - 1) * 9 * (lenN - 1 - index)
                ans += 9*9*(((lenN - 1-index) * (lenN - 2-index)) // 2)
                index_2 += index+1
                while (index_2 < lenN):
                    if int(strN[index_2]) != 0:
                        ans += int(strN[index_2])
                        ans += 9*(lenN-1-index_2)
                        break
                    index_2 += 1
            index += 1
        #ans += 9 * 9 * (((lenN - 2) * (lenN - 3)) // 2)
        ans += (int(strN[0]) - 1) * 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)
        ans += 9*9*9*(((lenN-1)*(lenN-2)*(lenN-3))//6)
        # for h in range(1, lenN - 2):
        #    ans += 9 * 9 * 9*(((lenN-1-h)*(lenN-2-h))//2)
print(ans)

Submission status: Accepted

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

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])

def keta2(n):
    if n < 10:
      return 0
    s = str(n)
    cnt = [0] * 101
    for i in range(2, 101):
        cnt[i] = 9 * 9 * (i - 1)
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta1(10 ** (len(s) - 1) - 1) + keta1(int(s[1:]))
    return res

def keta3(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(3, 101):
        cnt[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta2(10 ** (len(s) - 1) - 1) + keta2(int(s[1:]))
    return res

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

Submission status: Accepted

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

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(l)]

dp[0][1][0] = int(n[0])-1
dp[0][1][1] = 1

for i in range(1, l):

    dp[i][1][0] = dp[i-1][1][0] + 9
    dp[i][2][0] = dp[i-1][2][0] + 9 * dp[i-1][1][0]
    dp[i][3][0] = dp[i-1][3][0] + 9 * dp[i-1][2][0]

    if int(n[i]) == 0:
        dp[i][1][1] = dp[i-1][1][1]

    elif dp[i-1][1][1] == 1:
        dp[i][2][1] = 1
        dp[i][2][0] += int(n[i])-1
        dp[i][1][0] += 1

    elif dp[i-1][2][1] == 1:
        dp[i][3][1] = 1
        dp[i][3][0] += int(n[i])-1
        dp[i][2][0] += 1

    elif dp[i-1][3][1] == 1:
        dp[i][3][0] += 1

print(sum(dp[-1][k]))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

def g(m, k):
    if k == 0:
        return 1
    if k == 1:
        return m * 9
    if k == 2:
        return m * (m-1) // 2 * 81
    if k == 3:
        return m * (m-1) * (m-2) // 6 * 729

@lru_cache(maxsize=None)
def f(n, k):
    if n == 0 and k:
        return 0
    if k == 0:
        return 1
    S = str(n)
    t = int(S[0])
    m = len(S)
    return f(int("0" + S[1:]), k-1) + ((t-1) * g(m-1, k-1) if t else 0) + g(m-1, k)

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

Submission status: Accepted

Solution code:
def e_almost_everywhere_zero():
    def digit_dp(n):  # n は文字列で与える
        """n 以下の非負整数で、0でない数字がちょうど K 個あるような数の個数"""
        digit = len(n)

        # dp[i][j][k]: i 桁目まで見たとき、N 未満が確定しているなら j = 1、
        # していないなら j = 0 とし、0 でない桁が k 個ある
        dp = [[[0] * (K + 2) for j in range(2)] for i in range(digit + 1)]
        dp[0][0][0] = 1
        for i in range(digit):
            for j in range(2):
                for k in range(K + 1):
                    lim = 9 if j == 1 else ord(n[i]) - ord('0')
                    for d in range(lim + 1):
                        # 0 でない桁が K + 1 個以上ある場合を同一視する
                        t = k + int(d != 0)
                        if t >= K + 1:
                            t = K + 1
                        dp[i + 1][j or (d < lim)][t] += dp[i][j][k]
        return sum(dp[digit][j][K] for j in range(2))

    N = input()
    K = int(input())
    return digit_dp(N)

print(e_almost_everywhere_zero())

Submission status: Accepted

Solution code:
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[0])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[0])-1)
    print(counter)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            dp[("T",i,k)]+=dp[("T",i-1,k)]
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) #k桁目の数字pが0<p<xなのは、x-1通り
                dp[("T",i,k)]+=dp[("F",i-1,k)]  #k桁目の数字pが0の場合は1通り
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 #k桁目の数字p=xの場合はゼロでない数字が1個増える
            else: #k桁の目の数字xが0の場合
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]

Submission status: Accepted

Solution code:
from functools import lru_cache
N = int(input())
K = int(input())

@lru_cache(None)
def f(N, K):
    if K == 0: return 1
    if N < 10:
        if K == 1: return N
        return 0
    q, r = divmod(N, 10)
    ret = 0
    ret += f(q, K-1) * r
    ret += f(q-1, K-1) * (9-r)
    ret += f(q, K)
    return ret

print(f(N, K))

Submission status: Accepted

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


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


def partical(L, K, M):  # L:対象の数の長さ K:0以外の個数 M:最大位の数値
    res = 0
    # 最大位の一つ前の位まで
    if L - K > 1:
        res += combinations_count(L - 1, K) * (9 ** K)
    # 最大位の直近の位まで
    if L > 1 and K > 1:
        res += (M - 1) * combinations_count(L - 1, K - 1) * (9 ** (K - 1))
    # 最大位計算の場合
    if K == 1:
        res += M
    return res


def calcLM(target):
    L = len(str(target))
    M = int(str(target)[0])
    return (L, M)


while k > 0:
    L, M = calcLM(n)
    ans += partical(L, k, M)
    n = n - int(str(n)[0]) * (10 ** (len(str(n))-1))
    k = k - 1

print(ans)

Submission status: Accepted

Solution code:
N = input()
lN = len(N)
n0 = int(N[0])
K = int(input())

# dp[i][k][is_tight] : 
# 上からi桁目まで確定させたときに、0でない桁がk個あり、
# is_tight = 0 -> N未満になることが確定している (=> 次の桁からは自由に選べる)
# is_tight = 0 -> Nと等しくなる可能性がある (=> 次の桁でNを超えないように注意する必要がある)
dp = [[[0, 0] for k in range(K+1)] for i in range(lN)]
# 始めの桁で、'0'を選択するとN未満が確定するため、[1, 0]
dp[0][0] = [1, 0]
# 始めの桁で、'0'以外を選択する場合、Nの最高位の数との関係で下記のように決まる
dp[0][1] = [n0-1, 1]

for i, n in enumerate(N[1:], 1):
  dp[i][0] = [1, 0] # その桁まで全ての桁で'0'を選び続けた場合は、[1, 0]
  if n == '0': # その桁が'0'の場合の遷移
    for k in range(1, K+1):
      dp[i][k][0] = dp[i-1][k][0] + dp[i-1][k-1][0]*9
      dp[i][k][1] = dp[i-1][k][1]
  
  else: # その桁が'0'以外の場合の遷移
    for k in range(1, K+1):
      dp[i][k][0] = sum(dp[i-1][k]) + dp[i-1][k-1][0]*9 + dp[i-1][k-1][1]*(int(n)-1)
      dp[i][k][1] = dp[i-1][k-1][1]


print(sum(dp[-1][K]))

Submission status: Accepted

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

ans = 0


def k1(n):
    str1_n = str(n)
    keta1 = len(str1_n)
    cnt = 9 * (keta1 - 1) + int(str1_n[0])
    return cnt


def k2(n):
    str2_n = str(n)
    keta2 = len(str2_n)
    cnt = 81 * (keta2 - 1) * (keta2 - 2) // 2
    cnt += (int(str2_n[0]) - 1) * k1(10 ** (keta2 - 1) - 1)
    cnt += k1(n - (int(str2_n[0]) * 10 ** (keta2 - 1)))
    return cnt


def k3(n):
    str3_n = str(n)
    keta3 = len(str3_n)
    t = 0
    for i in range(keta3-2):
        t += (i+1)*i//2
    cnt = 729 * t
    cnt += (int(str3_n[0]) - 1) * k2(10 ** (keta3 - 1) - 1)
    cnt += k2(n - (int(str3_n[0]) * 10 ** (keta3 - 1)))
    return cnt


if k == 1:
    ans = k1(n)

if k == 2:
    ans = k2(n)

if k == 3:
    ans = k3(n)

print(ans)

Submission status: Accepted

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, K):
    N = int(N)
    @lru_cache(maxsize=None)
    def f(n, k):
        if k == 0:
            return 1
        m = n % 10
        l = n // 10
        if l == 0 and k == 1:
            return m
        elif l == 0:
            return 0
        return f(l, k-1)*m + f(l-1, k-1)*(9-m) + f(l, k)


    return f(N, K)


def f(N, K):
    M = len(N)
    N = int(N)
    ans = 0
    for i in range(N+1):
        n = str(i).count('0')
        if len(str(i)) - n == K:
            ans += 1
            # print(i)
    return ans

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

    # print(f(N, K))

    # for _ in range(1000):
    #     N = str(random.randint(1, 100))
    #     K = random.randint(1, 3)
    #     # print(N)
    #     # print(K)
    #     a = slv(N, K)
    #     b = f(N, K)
    #     if a != b:
    #         print(N)
    #         print(K)
    #         print(a, b)
    #         assert a == b



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
s=len(list(str(n)))
if k==1:
    ans=(s-1)*9
    for i in range(9):
        if n>=(10**(s-1))*(i+1):
            ans+=1
elif k==2:
    ans=9*9*(s-1)*(s-2)//2
    for i in range(9):
        for j in range(s-1):
            for p in range(9):
                if n>=(10**(s-1))*(i+1)+(10**j)*(p+1):
                    ans+=1
else:
    ans=9*81*(s-1)*(s-2)*(s-3)//6
    f=int(list(str(n))[0])
    ans+=(f-1)*81*(s-1)*(s-2)//2
    for p in range(s-1):
        for q in range(s-1):
            if p<q:
                for t in range(1,10):
                    for u in range(1,10):
                        if n>=(10**(s-1))*f+(10**p)*t+(10**q)*u:
                            ans+=1
print(ans)

Submission status: Accepted

Solution code:
def f(k, n):
    n_str = str(n)
    digit = len(n_str)
    head = int(n_str[0])
    rest = int(n_str[1:]) if digit > 1 else 0

    if k == 1:
        return 9*(digit-1) + head
    if k == 2:
        if n <= 10:
            return 0
        else:
            return 9 * (digit-1) * (head-1) + f(1,rest) + f(2, 10**(digit-1)-1)
    if k == 3:
        if n < 111:
            return 0
        else:
            return 9**2 * (digit-1)*(digit-2)//2 * (head-1) + f(2,rest) + f(3, 10**(digit-1)-1)


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

print(f(k,n))

Submission status: Accepted

Solution code:
import math

def comb(n, r):
	if n <= r:
		return 1
	else:
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def perm(n, r):
	if n <= r:
		return math.factorial(n)
	else:
		return math.factorial(n) // (math.factorial(n - r))
	
N = int(input())
K = int(input())
N_str = str(N)
N_keta = len(N_str)
N_f = int(N_str[0])

def K1(a):
	a_str = str(a)
	a_keta = len(a_str)
	a_f = int(a_str[0])
	return a_f + (a_keta-1)*9

def K2(a):
	a_str = str(a)
	a_keta = len(a_str)
	a_f = int(a_str[0])
	if a_keta < 2:
		return 0
	else:
		a_under1 = int(a_str[1:])
		a_list = [9*9*i for i in range(1, a_keta-1)]
		return (a_f-1)*9*(a_keta-1) + K1(a_under1) + sum(a_list)

if K == 1:	
	print(K1(N))

elif K == 2:
	print(K2(N))

elif K == 3:
	if N_keta < 3:
		print(0)
	else:
		N_under1 = int(N_str[1:])
		N_list = [9*9*9*comb(i, 2) for i in range(2, N_keta-1)]
		print(K2(N_under1) + (N_f-1)*9*9*comb(N_keta-1, 2) + sum(N_list))

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

dp1 = [[0]*4 for _ in range(m+1)] #等しい
dp2 = [[0]*4 for _ in range(m+1)] #未満
dp1[0][0] = 1
for i in range(m):
    x = int(n[i])
    for j in range(10):
        if j == x:
            if j == 0:
                for k in range(4):
                    dp1[i+1][k] += dp1[i][k]
                    dp2[i+1][k] += dp2[i][k]
            else:
                for k in range(3):
                    dp1[i+1][k+1] += dp1[i][k]
                    dp2[i+1][k+1] += dp2[i][k]
        elif j < x:
            if j == 0:
                for k in range(4):
                    dp2[i+1][k] += dp1[i][k]
                    dp2[i+1][k] += dp2[i][k]
            else:
                for k in range(3):
                    dp2[i+1][k+1] += dp1[i][k]
                    dp2[i+1][k+1] += dp2[i][k]
        else:
            for k in range(3):
                dp2[i+1][k+1] += dp2[i][k]
ans = dp1[m][K] + dp2[m][K]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def main():
    n = [int(x) for x in input()]
    K = int(input())
    dp = np.zeros((len(n)+1, 2, 5), dtype=int)

    if len(n) < K:
        print(0)
        return

    dp[0, 0, 0] = 1

    for i in range(len(n)):
        for k in range(K+1):
            # use 0
            if n[i] == 0:
                dp[i+1, 0, k] += dp[i, 0, k]
                dp[i+1, 1, k] += dp[i, 1, k]
            else:
                dp[i+1, 1, k] += dp[i, 0, k] + dp[i, 1, k]
            # use 1~9
            for x in range(1, 10):
                if x < n[i]:
                    # always smaller
                    dp[i+1, 1, k+1] += dp[i, 0, k] + dp[i, 1, k]
                elif x == n[i]:
                    dp[i+1, 0, k+1] += dp[i, 0, k]
                    dp[i+1, 1, k+1] += dp[i, 1, k]
                else:
                    dp[i+1, 1, k+1] += dp[i, 1, k]
    print(dp[len(n), 0, K] + dp[len(n), 1, K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} #階乗
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) #組み合わせ

def aaa(n,k):
    r = len(str(n))-1
    st = str(n)
    ans = 0
    if k==1 and r>=0:
        ans += 9**1 * comb(r, 1) \
               + int(st[0])
    else:
        ans += 9**k * comb(r, k) \
               + (int(st[0])-1) * 9**(k-1) * comb(r, k-1) \
               + aaa(n%(10**r), k-1)
    return ans

n = int(input())
k = int(input())
ans = aaa(n,k)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
ans = 0
if k == 1:
    if n < 10:
        ans = n
    else:
        l = len(str(n))
        ans += 9 * (l - 1)
        ans += int(str(n)[0])
elif k == 2:
    if n < 11:
        ans = 0
    else:
        l = len(str(n))
        for i in range(2, l):
            ans += 9 * 9 * (i - 1)
        f = int(str(n)[0])
        ans += (f - 1) * 9 * (l - 1)
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        else:
            num = l - 1
            f = 0
        ans += f
        ans += 9 * (l - num - 1)
else:
    if n < 111:
        ans = 0
    else:
        l = len(str(n))
        # 54321
        # 1桁下まで 10000未満
        ans += 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6

        # 最高位の桁1小さいとこまで 50000未満
        f = int(str(n)[0])
        ans += (f - 1) * 9 * 9 * (l - 1) * (l - 2) // 2

        # 最高位の桁一致 54000未満
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        else:
            num = l - 1
        ans += (f - 1) * (l - num - 1) * 9  # その桁が0でない
        ans += 9 * 9 * (l - num - 1) * (l - num - 2) // 2  # その桁が0である

        # 54000台
        for i in range(num + 1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        else:
            num = l - 1
            f = 0
        ans += (l - num - 1) * 9
        ans += f
print(ans)

Submission status: Accepted

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


def main(d, k):
    if (L - d) < k:
        return 0
    if N[d] == "0":
        return main(d + 1, k)
    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())
R = len(str(n))
r = R - 1
q = 0
num = [0] * 4
index = [0] * 4
s = str(n)
for i in range(R):
    if s[i] != "0":
        num[q] = int(s[i])
        index[q] = i
        q += 1
    if q == 4:
        break

if k == 1:
    ans = 9 * r + num[0]
elif k == 2:
    ans = 81 * r * (r-1) // 2
    if num[1] != 0:
        pass
    else:
        num[0] -= 1
        num[1] = 9
        index[1] = 1
    ans += 9 * (R - 1) * (num[0] - 1) + num[1] + 9 * (R - index[1] - 1)
elif k == 3:
    ans = 243 * r * (r-1) * (r-2) // 2
    if num[2] != 0:
        pass
    elif num[1] != 0:
        num[1] -= 1
        index[2] = index[1] + 1
        num[2] = 9
    else:
        num[0] -= 1
        index = [0, 1, 2]
        num[1], num[2] = 9, 9
    ans += 81 * (R-1)*(R-2)*(num[0]-1)//2 + 9 * (R - index[1] - 1) * (num[1] - 1)
    ans += 81 * (R-index[1]-1)*(R-index[1]-2) // 2
    ans += 9 * (R - index[2] - 1) + num[2]
print(ans)

Submission status: Accepted

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

    def main(d, k):
        if (L - d) < k:
            return 0
        if N[d] == "0":
            return main(d + 1, k)
        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:
import sys
sys.setrecursionlimit(100000)

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} #階乗
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) #組み合わせ

def aaa(n,k):
    r = len(str(n))-1
    st = str(n)
    ans = 0
    if k==1 and r>=0:
        ans += 9*r \
               + int(st[0])
    elif k==2 and r>=1:
        ans += 9**2 * comb(r, 2) \
               + (int(st[0])-1) * 9**1 * comb(r, 1) \
               + aaa(n%(10**r), k-1)
    elif k==3 and r>=2:
        ans += comb(r, 3)*9**3\
               +comb(r, 2)*9**2*(int(st[0])-1)\
               +aaa(n%(10**r), k-1)
    return ans

n = int(input())
k = int(input())
ans = aaa(n,k)
print(ans)

Submission status: Accepted

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

def f(N,k):
    if not N:
        return 0
    N = str(int(N))
    a = (len(N)-1)
    na = int(N[0])
    if k == 1:
        return str(9*a+na)
    if k == 2:
        return str(9**2*a*(a-1)//2 + (na-1)*int(f('9'*a,1)) + int(f(N[1:],1)))
    if k == 3:
        return str(9**3*a*(a-1)*(a-2)//6 + (na-1)*int(f('9'*a,2)) + int(f(N[1:],2)))

def solve():
    N = input()
    K = int(input())
    return f(N,K)
    
if __name__ == '__main__':
    print(solve())