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()
k=int(input())
dp=[[(k+1)*[0]for _ in range(2)]for _ in range(len(n))]
#dp[i][flag][j]...i文字目までみて0以外がj個あるパターン数
#flag...True(n[])
dp[0][0][0]=1
dp[0][1][1]=1
dp[0][0][1]=int(n[0])-1
for i in range(1,len(n)):
  for j in range(k+1):dp[i][1][j]=dp[i-1][1][j]
  if n[i]!="0":dp[i][1]=[0]+dp[i][1][:k]
  for j in range(k+1):dp[i][0][j]=dp[i-1][0][j]
  for j in range(k):
    dp[i][0][j+1]+=dp[i-1][0][j]*9
    if n[i]!="0":
      dp[i][0][j+1]+=dp[i-1][1][j]*(int(n[i])-1)
      dp[i][0][j+1]+=dp[i-1][1][j+1]
print(dp[-1][0][-1]+dp[-1][1][-1])
#for i in dp:print(*i)

Submission status: Accepted

Solution code:

from functools import reduce
import operator
product = lambda it: reduce(operator.mul,it,1)

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

comb = lambda n, k: product(range(n-k+1,n+1))//product(range(1,k+1))

def rec(i, k):
    if k == 0:
        return 1
    if len(N) < k + i:
        return 0
    return (max(0,int(N[i])-1)*(9**(k-1))*comb(len(N)-i-1, k-1) +
            (rec(i+1,k) if N[i] == '0' else rec(i+1,k-1) + (9**k)*comb(len(N)-i-1, k)))

print(rec(0,K))

Submission status: Accepted

Solution code:
# 桁DP
n = int(input())
k = int(input())

def solve(num, k_):
    # 左から桁DP
    # dp[i-th number][is_max][how many not 0]
    n = len(str(num)) + 1
    dp = [[[0 for _ in range(k_+2)] for _ in range(2)] for _ in range(n)]
    dp[0][0][0] = 1

    for i in range(n-1):
        D = int(str(num)[i])
        for j in range(2):
            for k in range(k_+1):
                for d in range(10 if j else D+1):
                    if d == 0:
                        dp[i+1][j or (d < D)][k] += dp[i][j][k]
                    else:
                        dp[i+1][j or (d < D)][k+1] += dp[i][j][k]
    return dp[-1][0][k_] + dp[-1][1][k_]

print(solve(n, k))

Submission status: Accepted

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

memo = [
    collections.defaultdict(int),
    collections.defaultdict(int),
    collections.defaultdict(int),
    collections.defaultdict(int)
]


def rec(n, k):
    if k == 0:
        return 1
    elif n < 10:
        if k == 1:
            return n
        else:
            return 0
    elif n in memo[k]:
        return memo[k][n]
    digit = len(str(n))
    top = (n // (10**(digit - 1))) * 10**(digit - 1)
    residue = n - top
    hoge = rec(top - 1, k) + rec(residue, k - 1)
    memo[k][n] = hoge
    return hoge


print(rec(N, K))

Submission status: Accepted

Solution code:
n = input()
k = int(input())
l = len(n)
dp = [[[0 for i in range(2)] for t in range(3+1)] for j in range(l+1)]
dp[0][0][0] = 1
for i in range(1,l+1):
  for j in range(k+1):
    x = int(n[i-1])
    if x != 0:
      for m in range(1,3+1):
        dp[i][m][0] = dp[i-1][m-1][0]
    else:
      for m in range(3+1):
        dp[i][m][0] = dp[i-1][m][0]
    dp[i][0][1] = dp[i-1][0][0]+dp[i-1][0][1]
    dp[i][1][1] = dp[i-1][0][1]*9+dp[i-1][1][1]+dp[i-1][0][0]*(max(0,x-1))+dp[i-1][1][0]*(x>0)
    dp[i][2][1] = dp[i-1][1][1]*9+dp[i-1][2][1]+dp[i-1][1][0]*(max(0,x-1))+dp[i-1][2][0]*(x>0)
    dp[i][3][1] = dp[i-1][2][1]*9+dp[i-1][3][1]+dp[i-1][2][0]*(max(0,x-1))+dp[i-1][3][0]*(x>0)
print(dp[l][k][0]+dp[l][k][1])

Submission status: Accepted

Solution code:

N = input()

K = int(input())

lis =  [ [ [0,0] for i in range(K+1) ] for j in range(len(N) + 1) ]

#桁/0以外が出た個数/密着フラグ

lis[0][0][0] = 1

for i in range(len(N)):

    nketa = int(N[i])

    for num in range(K):

        for flag in range(2):


            if num == 0 and flag == 0:

                lis[i+1][num+1][0] += lis[i][num][flag]
                lis[i+1][num+1][1] += (nketa - 1) * lis[i][num][flag]
                lis[i+1][num][1] += lis[i][num][flag]

            if num != K and flag == 0:

                if nketa == 0:
                    lis[i+1][num][0] += lis[i][num][flag]
                else:
                    lis[i+1][num+1][0] += lis[i][num][flag]
                    lis[i+1][num][1] += lis[i][num][flag]
                    lis[i+1][num+1][1] += lis[i][num][flag] * (nketa - 1)
                

            if num != K and flag == 1:

                lis[i+1][num+1][1] += 9 * lis[i][num][flag]
                lis[i+1][num][1] += lis[i][num][flag]

ans = 0

#print (lis)

for i in range(len(N) + 1):

    for j in range(2):

        ans += lis[i][K][j]

print (ans //2 )

Submission status: Accepted

Solution code:
class S:
    def solve(self, n, k):
        self.n = n
        return self.dfs(0, k, False)
    def dfs(self, x, y, free=False):
        if y == 0:
            return 1
        if x >= len(self.n):
            return 0
        if free:
            return 9 * self.dfs(x + 1, y - 1, free) + self.dfs(x + 1, y, free)
        else:
            t = int(self.n[x])
            r = 0
            if t > 0:
                r += 1 * self.dfs(x + 1, y - 1, False)
                r += (t - 1) * self.dfs(x + 1, y - 1, True)
            r += self.dfs(x + 1, y, t > 0)
            return r


n = raw_input()
k = input()
print S().solve(n, k)

Submission status: Accepted

Solution code:
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            if n[i] != '0':
                dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

Submission status: Accepted

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

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

def rec(n,k):
    res = 0
    if k < 0:
        return res
    if k==0:
        res = 1
        return res
    if len(n)<k:
        return res
    if n[0] != '0':
        res += rec(n[1:],k-1)
        res += (int(n[0])-1)*comb(len(n)-1,k-1)*9**(k-1)
        res += comb(len(n)-1,k)*9**k
    else:
        res += rec(n[1:],k)
    return res

print(rec(N,K))

Submission status: Accepted

Solution code:
from itertools import combinations

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


if k == 1:
	print(9 * (len(s)-1) + int(s[0]))

elif k == 2:
	if len(s) == 1:
		print(0)
	elif len(s) == 2:
		print(n - 9 - n//10)
	else:
		ans = 81 * (l-1) * (l-2) // 2
		for i in range(1, 10):
			for x in range(l-1):
				for j in range(1, 10):
					if i * (10**(l-1)) + j * (10**x) <= n:
						ans += 1
		print(ans)

else:
	if len(s) < 3:
		print(0)
	elif len(s) == 3:
		ans = 0
		for i in range(100, n+1):
			if "0" not in list(str(i)):
				ans += 1
		print(ans)
	else:
		ans = 729 * (l-1) * (l-2) * (l-3) // 6
		ans += (int(s[0])-1) * (l-1) * (l-2) * 81 // 2
		for x, y in combinations(range(l-1), 2):
			for z in range(81):
				j, k = (z//9) + 1, (z%9) + 1
				if int(s[0]) * (10**(l-1)) + j * (10**x) + k * (10**y) <= n:
					ans += 1
		print(ans)

Submission status: Accepted

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

def fact(x):
  r = 1
  while x>0:
    r *= x
    x -= 1
  return r

def comb(x, y):
  if y>x:
    return 0
  return fact(x)/fact(y)/fact(x-y)

N = str(N+1)
def f(d, k):
  if k==0:
    if d>=len(N) or int(N[d:])==0:
      return 0
    else:
      return 1
  while d<len(N) and N[d]=="0":
    d += 1
  if d>=len(N):
    return 0
  return (
    comb(len(N)-d-1, k)*9**k +
    (int(N[d])-1)*comb(len(N)-d-1, k-1)*9**(k-1) +
    f(d+1, k-1))

print f(0, K)

Submission status: Accepted

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

def f(N,K):
    if K==0: return 1
    if N=="": return 0
    N=str(int(N))
    if N==0 : return 0
    l = len(N)
    n0 = int(N[0])
    return f(N[1:],K-1) + f("9"*(l-1),K-1)*(n0-1) + f("9"*(l-1),K)

print(f(N,K))

Submission status: Accepted

Solution code:
import sys
sys.stdin.readline

def main():
    N, K = input(), int(input())
    S = "0"*(100-len(N))+N
    DP = [[[0] * 2 for _ in range(K+2)] for _ in range(101)]
    DP[0][0][0] = 1
    for i in range(100):
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0] * (S[i] == "0")
            DP[i+1][j+1][0] += DP[i][j][0] * (S[i] != "0")
            DP[i+1][j][1] += DP[i][j][1] + DP[i][j][0] * (int(S[i]) > 0)
            DP[i+1][j+1][1] += DP[i][j][1] * 9 + DP[i][j][0] * max(0, int(S[i])-1)
    print(sum(DP[-1][K]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*(4) for j in range(2)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            for k in range(4):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    if k + (d != 0) > 3:
                        continue
                    dp[i+1][j or d < lim][k + (d != 0)] += dp[i][j][k]
    ans = 0
    for j in range(2):
        ans += dp[N][j][K]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

N, K = map(int,read().split())

@lru_cache(None)
def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        # 1の位が nonzero
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    # 1の位が zero
    ret += F(q, K)
    return ret

# F(100, 1), F(25, 2), F(314159, 2)

print(F(N, K))

Submission status: Accepted

Solution code:
N = input()
l = len(N)
K = int(input())
dp = [[[0]*2 for i in range(K+1)] for j in range(l)]
dp[0][0][0] = 1
dp[0][1][0] = int(N[0])-1
dp[0][1][1] = 1
for i in range(l-1):
    for j in range(K+1):
        for d in range(10):
            if d == 0:
                dp[i+1][j][0] += dp[i][j][0]
                if N[i+1] == '0':
                    dp[i+1][j][1] += dp[i][j][1]
                else:
                    dp[i+1][j][0] += dp[i][j][1]
            else:
                if j==K:
                    continue
                dp[i+1][j+1][0] += dp[i][j][0]
                if int(N[i+1])>d:
                    dp[i+1][j+1][0] += dp[i][j][1]
                elif int(N[i+1])==d:
                    dp[i+1][j+1][1] += dp[i][j][1]
print(dp[-1][-1][0]+dp[-1][-1][1])

Submission status: Accepted

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

mod = 10**9 + 7
l = 2*10**2

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    if y < 0 or y > x:
        return 0
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod

ans = 0
k = kk
for i in range(len(n)):
    s = int(n[i])
    z = len(n)-i-1
    # print(s,z)
    if s >= 1 and k >= 0:
        ans += C(z, k) * (9**k) + C(z, k-1) * (9**(k-1)) * (s-1)
        k -= 1
    # print("ans",ans)
if n.count("0") == len(n)-kk:
    ans += 1
print(int(ans))

Submission status: Accepted

Solution code:
n=input()
k=int(input())
dp=[[[0]*(k+1)for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0]=1
for i in range(1,len(n)+1):
    for j in range(int(n[i-1])):
        if j==0:
            for h in range(k+1):
                dp[i][1][h]+=dp[i-1][0][h]
        else:
            for h in range(k):
                dp[i][1][h+1]+=dp[i-1][0][h]
    for j in range(10):
        if j==0:
            for h in range(k+1):
                dp[i][1][h]+=dp[i-1][1][h]
        else:
            for h in range(k):
                dp[i][1][h+1]+=dp[i-1][1][h]
    if int(n[i-1])==0:
        for h in range(k+1):
            dp[i][0][h]+=dp[i-1][0][h]
    else:
        for h in range(k):
            dp[i][0][h+1]+=dp[i-1][0][h]
print(dp[-1][0][-1]+dp[-1][1][-1])

Submission status: Accepted

Solution code:
def main():
    N=[int(x) for x in list(input())]
    k=int(input())
    digit=len(N)
    if k>digit:
        return 0
    DP=[[[0]*(digit+1) for _ in range(2)] for _ in range(digit+1)] #DP[上からd桁][less][0の個数]
    DP[0][0][0]=1
    for d in range(digit):
        for less in range(2):
            for num in range(digit):
                limit=9 if less else N[d]
                for l in range(limit+1):
                    DP[d+1][less or l<limit][num+(l==0)]+=DP[d][less][num]
    return DP[-1][0][digit-k]+DP[-1][1][digit-k]
    #print(DP)
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
n = input()
k = int(input())
keta = len(n)
ans = 0


dp = [[[0] * 2 for i in range(4)] for i in range(keta + 1)]
dp[0][0][0] = 1

for i in range(keta):
    # 同じ -> 同じ
    if n[i] == "0":
        for j in range(4):
            dp[i + 1][j][0] += dp[i][j][0]
    else:
        for j in range(3):
            dp[i + 1][j + 1][0] += dp[i][j][0]
    
    # 同じ -> 違う
    for ii in range(int(n[i])):
        if ii == 0:
            for j in range(4):
                dp[i + 1][j][1] += dp[i][j][0]
        else:
            for j in range(3):
                dp[i + 1][j + 1][1] += dp[i][j][0]
    # 違う -> 違う
    for ii in range(10):
        if ii == 0:
            for j in range(4):
                dp[i + 1][j][1] += dp[i][j][1]
        else:
            for j in range(3):
                dp[i + 1][j + 1][1] += dp[i][j][1]
print(sum(dp[keta][k]))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = str(ni() + 1)
m = len(n)
k = ni()


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

def p(x, k):
    y = 1
    for i in range(k):
        y *= x
    return y

e = 0
ans = 0
for i in range(m):
    d = ord(n[i]) - ord("0")
    if i == 0:
        if d > 1:
            ans += (d-1)*C(m-1, k-1)*p(9,k-1)
    else:
        ans += 9*C(m-1-i, k-1)*p(9,k-1)
        if d > 0:
            ans += (d-1)*C(m-1-i, k-1-e)*p(9,k-1-e)
            ans += C(m-1-i, k-e)*p(9,k-e)
    if d > 0:
        e += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ns()
k = ni()
dp = [[[0]*2 for _ in range(k+1)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    x = int(n[i])
    for j in range(k):
        dp[i+1][j+1][1] += dp[i][j][1]*9
        dp[i+1][j][1] += dp[i][j][1]
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)
            dp[i+1][j+1][0] += dp[i][j][0]
        else:
            dp[i+1][j][0] += dp[i][j][0]
    dp[i+1][k][1] += dp[i][k][1]
    dp[i+1][k][x>0] += dp[i][k][0]
print(sum(dp[len(n)][k]))

Submission status: Accepted

Solution code:
from functools import lru_cache
n = list(map(int, list(input())))
k = int(input())

@lru_cache(10**9)
def rec(keta, cnt, tight):
    if cnt > k:
        return 0
    if keta==len(n):
        if cnt==k:
            return 1
        else:
            return 0
    ret = 0
    for i in range(10):
        if tight and i > n[keta]:
            break
        ret += rec(keta+1, cnt+int(i!=0), tight and i==n[keta])
    return ret

ans = rec(0,0, True)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = list(map(int, input()))
    K = I()
    l = len(n)
    if l < K:
        print(0)
        return
    dp = [[[0 for k in range(l+1)] for j in range(2)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(2):
            for k in range(l):
                x = 9 if j else n[i]
                for d in range(x+1):
                    nk = k+(d!=0)
                    nj = j or d < n[i]
                    if nk <= l:
                        dp[ni][nj][nk] += dp[i][j][k]
    
    print(dp[l][0][K]+dp[l][1][K])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def examA():
    S, T = LSI()
    A, B = LI()
    U = SI()
    if S==U:
        print(A-1,B)
    else:
        print(A,B-1)
    return

def examB():
    S = SI()
    N = len(S)
    ans = ""
    for i in range(N):
        ans += "x"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] += 1
        if d[a]>=2:
            print("NO")
            return
    print("YES")
    return

def examD():
    N, K = LI()
    P = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    ans = 0
    for i in range(N-K+1):
        cur = S[i+K]-S[i]
        ans = max(ans,cur)
    print(ans)
    return

def examE():
    def ketadp(a,K):
        n = len(a)
        C = [i for i in range(K+1)]
        dp = defaultdict(int)
        dp[0, 0, 0] = 1
        for i, less, k in itertools.product(range(n), (0, 1), C):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                if d==0:
                    dp[i + 1, less_, k] += dp[i, less, k]
                elif k<K:
                    dp[i + 1, less_, k+1] += dp[i, less, k]

        ans = sum(dp[n, less, K] for less in (0, 1))
        return ans
    N = SI()
    K = I()
    ans = ketadp(N,K)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

Solution code:
def solve(i, k, lesser, zero):
	global s, dp

	if k < 0:
		return 0

	if i == len(s):
		return 1 if k == 0 and not zero else 0

	if dp[i][k][lesser][zero] != -1:
		return dp[i][k][lesser][zero]

	if lesser:
		dp[i][k][lesser][zero] = solve(i + 1, k, True, zero)

		for d in range(1, 10):
			dp[i][k][lesser][zero] += solve(i + 1, k - 1, True, False)
	else:
		dp[i][k][lesser][zero] = solve(i + 1, k, 0 < s[i], zero)
		
		for d in range(1, s[i] + 1):
			dp[i][k][lesser][zero] += solve(i + 1, k - 1, d < s[i], False)

	return dp[i][k][lesser][zero]

def main():
	global s, dp

	s = list(input())
	k = int(input())

	for i in range(len(s)):
		s[i] = ord(s[i]) - ord('0')

	dp = [[[[-1, -1], [-1, -1]] for j in range(k + 1)] for i in range(len(s) + 1)]

	print(solve(0, k, False, True))

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read


#n, *a = [int(i) for i in read().split()]

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

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

for c in n:
    ndp = [[0]*k for _ in range(2)]
    ni = int(c)
    for is_less in range(2):
        for num in range(k):
            for d in range(10 if is_less else ni+1):
                if d == 0:
                    ndp[is_less or d < ni][num] += dp[is_less][num]
                elif num < k-1:
                    ndp[is_less or d < ni][num+1] += dp[is_less][num]

    dp = ndp


#print(dp)
print(sum(i[-1] for i in dp))

Submission status: Accepted

Solution code:
N = input()
K = int(input())
L = len(N)
dp = [[[0]*4 for _ in range(2)] for _ in range(L+1)]
dp[0][0][0] = 1

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

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)
K = int(input())
def nCk(n, k):
    ans = 1
    for i in range(1, k+1):
        ans *= (n-i+1)
        ans //= i
    return ans

ans = 1
for i in range(K):
    ans += (int(S[i])-1)*9**(K-1-i)*nCk(N-1-i, K-1-i) + 9**(K-i)*nCk(N-1-i, K-i)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import bisect
import math

# \n
def input():
    return sys.stdin.readline().rstrip()

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


def main():
    N=input()
    n=int(N)
    k= int(input())
    l = len(N)
    ans=0


    count =1
    for i in range(l):
        a = int(N[i])
        if a!=0:
            ans+=count * combinations_count(l-i-1,k-1) * max(a-1,0)*(9**(k-1)) #0でもaでもない場合
            if l-i-1>=k:
                ans += combinations_count(l-i-1,k) *(9**k) # 0 の場合
            k -=1
        if k==0:
            break


    print(ans+count)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k == 0: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ            
        else k -1 >= 0:
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]

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

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k -1 >= 0:
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: #すべての数が0ではない場合
            if l != 0: #i桁目 1～9
                #dp[i][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + dp[i - 1][0][k] # i桁目　N未満　すべてが0　→　0のみ　1コ
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k] #  # i桁目　Nと一致　すべてが0　→　該当なし　0コ
                dp[i][1][k] = dp[i - 1][1][k] # =1

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

N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k -1 >= 0:
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100)

n = input()
k = int(input())
m = {}


def doit(n, k):
    if len(n) == 0:
        return k == 0
    d = int(n[0])
    if (n, k) not in m:
        ret = 0
        for i in range(d + 1):
            if i == d:
                ret += doit(n[1:], k - 1 if i > 0 else k)
            else:
                ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
        m[(n, k)] = ret
    return m[(n, k)]


print(doit(n, k))

Submission status: Runtime Error

Solution code:
# 314159, 2,
# 0[xxxxx] 5C2 * 9*9 = 810
# 1[xxxxx] 5C1 * 9 = 45
# 2[xxxxx] 5C1 * 9 = 45
# 3[xxxxx] わからん!
# 31[0000] = 1
# 30[xxxx] = 4C1 * 9 合わせて937

# 9999, 3,
# 0[xxx] 3C3 * 9*9*9 = 729
# [yxxx] y=8, x=3C2 * 9*9 = 8 * 243
# 9[xxx] = 3C2 * 9*9 = 243

# 94599, 3,
# 0[xxxx] 4C3 * 9*9*9 = 4 * 729
# 1[xxxx] x=4C2 * 9*9 = 6 * 81
# ...
# 8[xxxx] x=4C2 * 9*9 = 6 * 81
# 94[x]00 = 5
# 940[xx] 2C1 * 9
# 93[xxx] 3C1 * 9
str_n = input()
n = int(str_n)
k = int(input())

head = n
while head >= 10:
  head //= 10
def choice(p, q):
  if p == q:
    return 1
  res = 1
  for i in range(q):
    res = (res * p)
    p -= 1
  for i in range(q):
    res = res // (i+1)
  return res

ans = choice(len(str_n)-1, k) * (9 ** k)
for i in range(1, head):
  ans += choice(len(str_n)-1, k-1) * (9 ** (k-1))
if k == 3:
  ans += int(str_n[2])  # 99x0000
  ans += choice(len(str_n) - 3, 1) * 9  # 990xxx
  ans += (int(str_n[1])-1) * choice(len(str_n) - 2, 1) * 9  # 9[1:8]xxxx
  ans += choice(len(str_n) - 2, 2) * 9*9  # 90xxxxx
if k == 2:
  ans += int(str_n[1])
  ans += choice(len(str_n) - 2, 1) * 9
if k == 1:
  ans += int(str_n[0])

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
if N<=10**6:
  ans=0
  for i in range(1,N+1):
    a=str(i)
    if len(a)-list(a).count("0")==K:
      ans+=1
  print(ans)
  exit()
L=list(map(int,list(str(N))))
ans=0
L=list(map(int,list(str(N))))
for i in range(N,N+1001):
  L=list(map(int,list(str(i))))
  s=L[:3]
  if s[0]!=0 and s[1]!=0 and s[2]!=0:
    go=i
    break
for i in range(N+1,go+1):
  a=str(i)
  if len(a)-list(a).count("0")==K:
    ans-=1
if K==1:#おけ
  print((len(str(N))-1)*9+int(str(N)[0]))
elif K==2:#おけ
  N=go
  for i in range(len(L)-1):
    ans+=(9*(int(str(N)[0])-1))
    for j in range(i+1,len(L)):
      if i==0:
        if j==1:
          ans+=int(str(N)[1])
        else:
          ans+=9
      else:
        ans+=81
  print(ans)
else:
  N=go
  le=len(L)
  for i in range(le-2):
    for j in range(i+1,le-1):
      for k in range(j+1,le):
        if i==0:
          ans+=81*(int(str(N)[0])-1)
          if j==1:
            ans+=9*(int(str(N)[1])-1)
            if k==2:
              ans+=int(str(N)[2])
            else:
              ans+=9
          else:
            ans+=81
        else:
          ans+=729
  print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
if N<=10**6:
  ans=0
  for i in range(1,N+1):
    a=str(i)
    if len(a)-list(a).count("0")==K:
      ans+=1
  print(ans)
  exit()
if K==1:#おけ
  ans=0
  print((len(str(N))-1)*9+int(str(N)[0]))
elif K==2:#おけ
  ans=0
  L=list(map(int,list(str(N))))
  for i in range(len(L)-1):
    ans+=(9*(int(str(N)[0])-1))
    for j in range(i+1,len(L)):
      if i==0:
        if j==1:
          ans+=int(str(N)[1])
        else:
          ans+=9
      else:
        ans+=81
  print(ans)
else:
  qwq

Submission status: Runtime Error

Solution code:
import math


def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume *= (n - i + 1)
        deno *= (i)
    return nume//deno


def solve(N, K):
    if K == 0:
        return 1
    keta = math.floor(math.log(N, 10)) + 1
    x = N//pow(10, keta-1)
    ret = 0
    if K > keta:
        return 0
    # ptn1: 最大の桁は0
    if keta != K:
        ret += comb(keta - 1, K) * (9 ** K)
    # ptn2: 最大の桁はNのその桁の値未満
    ret += (x-1)*comb(keta-1, K-1)*pow(9, K-1)
    # ptn3: 最大の桁はNのその桁の値
    ret += solve(N % pow(10, keta-1), K - 1)
    return ret


N = int(input())
K = int(input())
ans = solve(N, K)
print(ans)

Submission status: Runtime Error

Solution code:
import math


def comb(n, r):
    if r == 0:
        return 1
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume *= (n - i + 1)
        deno *= (i)
    return nume//deno

def solve(N, K):
    if K == 0:
        return 1
    keta = math.floor(math.log(N, 10)) + 1
    x = N//pow(10, keta-1)
    ret = 0
    if K > keta:
        return 0
    # ptn1: 最大の桁は0
    if keta != K:
        ret += comb(keta - 1, K) * (9 ** K)
    # ptn2: 最大の桁はNのその桁の値未満
    ret += (x-1)*comb(keta-1, K-1)*pow(9, K-1)
    # ptn3: 最大の桁はNのその桁の値
    ret += solve(N % pow(10, keta-1), K - 1)
    return ret


N = int(input())
K = int(input())
ans = solve(N, K)
print(ans)