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 main():
    N = input()
    len_N = len(N)
    K = int(input())
    dp = [[[0] * 2 for _ in range(K + 5)] for _ in range(len_N + 5)]
    dp[0][0][0] = 1
    for i in range(len_N):
        tmp = int(N[i])
        for j in range(K+1):
            # l : 1 => N より小さいことが確定 
            for l in range(2):
                for x in range(10):
                    if l == 0:
                        if x > tmp:
                            continue
                        elif x == tmp:
                            if x == 0:
                                dp[i+1][j][0] += dp[i][j][0]
                            else:
                                dp[i+1][j+1][0] += dp[i][j][0]
                        else:
                            if x == 0:
                                dp[i+1][j][1] += dp[i][j][0]
                            else:
                                dp[i+1][j+1][1] += dp[i][j][0]
                    if l == 1:
                        if x == 0:
                            dp[i+1][j][1] += dp[i][j][1]
                        else:
                            dp[i+1][j+1][1] += dp[i][j][1]
    
    print(dp[len_N][K][0] + dp[len_N][K][1])


        




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

n = list(map(int, list(input())))
k = int(input())
l = len(n)
dp0 = [[0]*(k+1) for _ in range(l+1)] #小さいの確定
dp1 = [[0]*(k+1) for _ in range(l+1)]

for i in range(1, l+1):
    dp0[i][0] = 1

dp1[0][0] = 1

for i in range(l):
    for j in range(k):

        if n[i] > 0:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1] + dp1[i][j+1] + (n[i]-1)*dp1[i][j]
            dp1[i + 1][j + 1] = dp1[i][j]
        else:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1]
            dp1[i + 1][j + 1] = dp1[i][j + 1]



# print(dp1[l][k])
print(dp0[l][k] + dp1[l][k])

Submission status: Accepted

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

def solve(N, K):
    l = len(N)
    dp = [[[0] * (10) for i 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 k in range(K+1):
                for d in range(10):
                    if j == 0 and d > D: break
                    dp[i+1][j or (d < D)][k if d == 0 else k+1] += dp[i][j][k]
    
    return dp[l][0][K] + dp[l][1][K]

print(solve(N,K))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = input()
N = len(n)
k = int(input())
dp = [[[0] * 2 for j in range(k + 1)] for i in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(k + 1):
        d = int(n[i])
        
        # i 桁目に "0" を配置したとき
        if d > 0:
            dp[i + 1][j][1] += dp[i][j][0]
        else:
            dp[i + 1][j][0] += dp[i][j][0]
        dp[i + 1][j][1] += dp[i][j][1]

        # i 桁目に "1", ..., "9" を配置したとき
        if j < k:
            if d > 0:
                dp[i + 1][j + 1][0] += dp[i][j][0]
                dp[i + 1][j + 1][1] += dp[i][j][0] * (d - 1)
            dp[i + 1][j + 1][1] += dp[i][j][1] * 9

print(dp[N][k][0] + dp[N][k][1])

Submission status: Accepted

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

l = len(str(n))

s = [0] + list(map(int,str(n))) #n=100の場合[0,1,0,0]みたいな感じ

if k > l:#n=10(l=2)でk=3とかだと該当する整数は存在しない
  print(0)
  exit()

dp = [[[0]*2 for _ in range(k+1)] for _ in range(l+1)]
#[0,0]を要素にもつ, k+1行l+1列の行列
#print(dp)

#dp[][][] の意味はdp[桁][k][0かどうかフラグ]


dp[0][0][1] = 1 #0行0列要素1
#print(dp)

for dig in range(l): #桁
  for i in range(k+1): 
    dp[dig+1][i][0] += dp[dig][i][0]
    dp[dig+1][i][1 if s[dig+1] == 0 else 0] += dp[dig][i][1]
    #sは先頭0, 桁ごとに分けたNのリスト e.g. N=123 -> [0,1,2,3]
    
    if i < k:
      dp[dig+1][i+1][0] += dp[dig][i][0] * 9
      if s[dig+1] > 0:
      	dp[dig+1][i+1][1] += dp[dig][i][1]
      	dp[dig+1][i+1][0] += dp[dig][i][1] * (s[dig+1]-1)

print(dp[l][k][0]+dp[l][k][1])

Submission status: Accepted

Solution code:
n, k = int(input()), int(input())
l = len(str(n))
s = [0] + list(map(int, str(n)))
if k > l: print(0); exit()

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

for dig in range(l):
    for i in range(k+1):
        dp[dig+1][i][0] += dp[dig][i][0]
        dp[dig+1][i][1 if s[dig+1] == 0 else 0] += dp[dig][i][1]
        if i < k:
            dp[dig+1][i+1][0] += dp[dig][i][0] * 9
            if s[dig+1] > 0:
                dp[dig+1][i+1][1] += dp[dig][i][1]
                dp[dig+1][i+1][0] += dp[dig][i][1] * (s[dig+1]-1)

print(dp[l][k][0] + dp[l][k][1])

Submission status: Accepted

Solution code:
from collections import deque
n = input()
a = [int(i) for i in list(n)]
k = int(input())
n = len(n)
ans = 0

if k > n:
    ans = 0
elif k == 1:
    # n 桁目に非負整数
    ans += a[0]
    # n 桁目以外に非負整数
    ans += (n - 1)*9
elif k == 2:
    # 上と同様
    for i in range(1, n):
        if a[i] != 0:
            j = i
            break
    else:
        j = n - 1
    ans += a[j] + (n - j - 1)*9
    # n 桁目の最大ではない非負整数と n-1 桁目以降に 1 つ非負整数
    ans += (a[0] - 1)*(n - 1)*9
    # n-1 桁目以降の中から 2 つ非負整数
    ans += (n - 1)*(n - 2)*9*9//2
else:
    # 上と同様
    j, l= -1, n - 1
    for i in range(1, n):
        if a[i] != 0:
            if j == -1:
                j = i
            else:
                l = i
                break
    if j != -1 and j != n - 1:
        ans += a[l] + (n - l - 1)*9 + (a[j] - 1)*(n - j - 1)*9 + (n - j - 1)*(n - j - 2)*9*9//2
    # n 桁目の最大でない非負整数と n-1 桁目以降に 2 つ非負整数
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    # n-1 桁目以降から 3 つ非負整数
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

Submission status: Accepted

Solution code:
#154_E
n = input()
s = len(n)
x = int(input())

#dp[i][flg][cnt] ... i桁目まで、未満フラグ、0以外の数
dp = [[[0 for _ in range(4)] for _ in range(2)] for _ in range(s+1)]
dp[0][0][0] = 1

for i in range(1, s+1):
    for k in [0, 1, 2, 3]:
        if n[i-1] == '0':
            dp[i][0][k] += dp[i-1][0][k]
        else:
            dp[i][1][k] += dp[i-1][0][k]
            if k > 0:
                dp[i][0][k] += dp[i-1][0][k-1]
                dp[i][1][k] += dp[i-1][0][k-1] * (int(n[i-1]) - 1)
        
        dp[i][1][k] += dp[i-1][1][k]
        if k > 0:
            dp[i][1][k] += dp[i-1][1][k-1] * 9
   
print(dp[s][0][x] + dp[s][1][x])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
s = str(n)
K = int(input())
l = len(str(n))

# dp[loose/tight][count][length]
dp = [[[0] * l for _ in range(K + 2)] for _ in range(2)]
for i, item in enumerate(s):
    val = int(item)
    # Initialize
    if i == 0:
        dp[0][0][i] = 1
        for j in range(1, 10):
            if j < val:
                dp[0][1][i] += 1
            if j == val:
                dp[1][1][i] += 1
        continue
    for j in range(10):
        is_not_zero = j != 0
        if val == j:
            for k in range(K+1):
                dp[0][k+is_not_zero][i] += dp[0][k][i-1]
                dp[1][k+is_not_zero][i] += dp[1][k][i-1]
        elif j < val:
            for k in range(K+1):
                dp[0][k+is_not_zero][i] += dp[0][k][i-1] + dp[1][k][i-1]
        else:
            for k in range(K+1):
                dp[0][k+is_not_zero][i] += dp[0][k][i-1]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
s = str(n)
K = int(input())
l = len(str(n))

# dp[loose/tight][count][length]
dp = [[[0] * l for _ in range(K + 1)] for _ in range(2)]
for i, item in enumerate(s):
    val = int(item)
    # Initialize
    if i == 0:
        dp[0][0][i] = 1
        for j in range(1, 10):
            if j < val:
                dp[0][1][i] += 1
            if j == val:
                dp[1][1][i] += 1
        continue
    # Use 0
    if val == 0:
        for k in range(K+1):
            dp[0][k][i] += dp[0][k][i-1]
            dp[1][k][i] += dp[1][k][i-1]
    else:
        for k in range(K+1):
            dp[0][k][i] += dp[0][k][i-1] + dp[1][k][i-1]
    for j in range(1, 10):
        if val == j:
            for k in range(K):
                dp[0][k+1][i] += dp[0][k][i-1]
                dp[1][k+1][i] += dp[1][k][i-1]
        elif j < val:
            for k in range(K):
                dp[0][k+1][i] += dp[0][k][i-1] + dp[1][k][i-1]
        else:
            for k in range(K):
                dp[0][k+1][i] += dp[0][k][i-1]

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

Submission status: Accepted

Solution code:
n=input()
l=len(n)
k=int(input())
def f(n,k):
  l=len(n)
  if l<k:return 0
  if n[0]=="0":return f(n[1:],k)
  if k==1:
    ans=((l-1)*9)+int(n[0])
  if k==2:
    ans=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
    ans+=f(n[1:],k-1)
  if k==3:
    ans=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
    ans+=f(n[1:],k-1)
  return ans
print(f(n,k))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = [int(i) for i in STR()]
k = INT()
l = len(n)
dp = [[[0, 0] for _ in range(l)] for _ in range(k + 1)] #dp[i個の0以外][j桁目まで][0:未満 1:未決定]
dp[0][0][0] = 1 #0
dp[1][0][1] = 1 #n[0]
dp[1][0][0] = n[0] - 1 #1からn[0] - 1
for j in range(1, l):
    dp[0][j][0] = dp[0][j - 1][0] #全部0

    for i in range(1, k + 1):
        dp[i][j][0] += dp[i - 1][j - 1][0] * 9 #0以外i-1個に0以外を
        dp[i][j][0] += dp[i - 1][j - 1][1] * (n[j] - 1) if n[j] > 0 else 0 #0以外i個の未満未決定にn[j]未満の数を
        dp[i][j][0] += dp[i][j - 1][0] #0以外i個かつ未満に0を
        dp[i][j][0] += dp[i][j - 1][1] if n[j] > 0 else 0 #0以外i個かつ未満未決定に0を

        dp[i][j][1] += dp[i][j - 1][1] if n[j] == 0 else 0 #0以外i個の未満未決定にn[j]を
        dp[i][j][1] += dp[i - 1][j - 1][1] if n[j] > 0 else 0 #0以外i-1個の未満未決定にn[j]を
print(sum(dp[k][l - 1]))

Submission status: Accepted

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

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

for i in range(N):
    for j in range(K+1):
        for k in range(2):
            cd=int(s[i])
            for nd in range(10):
                ni=i+1
                nj=j
                nk=k
                if nd!=0:nj+=1
                if nj>K:continue
                if k==0:
                    if nd>cd:continue
                    if nd<cd:nk=1
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[N][K][0]+dp[N][K][1])

Submission status: Accepted

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

L = len(N)

# dp[i][j][k]
# i: 決定した桁数(上から)
# j: 0の個数
# k: N未満確定フラグ
dp = [[[0] * 2 for _ in range(5)] for _ in range(110)]

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

# 配るDP
for i in range(L):
    S = int(N[i])
    for j in range(K+1):
        for k in range(2):
            # d: 次の桁
            for d in range((9 if k else S) + 1):
                dp[i+1][j + (d != 0)][k | (d < S)] += dp[i][j][k]

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

Submission status: Accepted

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

s = str(N)
n = len(s)

dp = [[[0]*2 for i in range(4)] for j in range(105)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni = i+1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if k == 0:
                    if d > nd:
                        continue
                    elif d < nd:
                        nk = 1
                    else:
                        pass
                if nj <= 3:
                    dp[ni][nj][nk] += dp[i][j][k]
#print(dp)
print(dp[n][K][0]+dp[n][K][1])

Submission status: Accepted

Solution code:
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*(K+2) 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(K+1):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    # print(i, j, lim, d, j or d < lim)
                    dp[i+1][j or d < lim][k + (d != 0)] += dp[i][j][k]
    print((dp[N][0][K]+dp[N][1][K]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def search(d, cnt, isLess):
    if d == len(N):
        return cnt == K

    a = int(N[d])

    if isLess:
        return search(d + 1, cnt + 1, isLess) * 9 + search(d + 1, cnt, isLess)

    ret = 0
    for i in range(a + 1):
        ret += search(d + 1, cnt + (i != 0), i < a)
    return ret

print(search(0, 0, False))

Submission status: Accepted

Solution code:
import numpy as np

dp = np.zeros((105,4,2),dtype=np.int32)

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

dp[0][0][0] = 1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni = i + 1
                nj = j 
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
ans = dp[n][K][0] + dp[n][K][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
n = str(N)
l = len(n)
dp0 = [[0 for _ in range(K+1)]  for _ in range(l+1)]
dp1 = [[0 for _ in range(K+1)]  for _ in range(l+1)]
dp0[0][0] = 1

for i in range(l):
    x = int(n[i])
    for j in range(K):
        dp1[i+1][j+1] += dp1[i][j]*9
        dp1[i+1][j] += dp1[i][j]
        if x > 0:
            dp1[i+1][j] += dp0[i][j]
            dp1[i+1][j+1] += dp0[i][j]*(x-1)
            dp0[i+1][j+1] += dp0[i][j]
        else:
            dp0[i+1][j] += dp0[i][j]
    dp1[i+1][K] += dp1[i][K]
    if x > 0:
        dp1[i+1][K] += dp0[i][K]
    else:
        dp0[i+1][K] += dp0[i][K]
print(dp0[-1][-1]+dp1[-1][-1])

Submission status: Accepted

Solution code:
N = [int(x) for x in input()]
K = int(input())
dp = [[[0]*2 for j in range(K+1)] for i in range(len(N)+1)]
dp[0][0][1] = 1
for i in range(len(N)):
    dp[i+1][0][0] = 1
    if N[i] == 0:
        for k in range(1, K+1):
            dp[i+1][k][0] = dp[i][k][0]+dp[i][k-1][0]*9
            dp[i+1][k][1] = dp[i][k][1]
    else:
        for k in range(1, K+1):
            dp[i+1][k][0] = dp[i][k][0]+dp[i][k-1][0]*9+dp[i][k-1][1]*(N[i]-1)+dp[i][k][1]
        for k in range(K-1, -1, -1):
            if dp[i][k][1]:
                dp[i+1][k+1][1] = dp[i][k][1]
                break
print(dp[len(N)][K][0]+dp[len(N)][K][1])

Submission status: Accepted

Solution code:
from itertools import combinations, product
from math import factorial

def nCr(n, r):
  return int(factorial(n) / factorial(n - r) / factorial(r))

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else nCr(size - 1, k) * (9 ** k)
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 10))
else:
  first = int(str(n)[0])
  count += 0 if k > size else (first - 1) * nCr(size - 1, k - 1) * (9 ** (k - 1))
  for digits in combinations(range(size - 1), k - 1):
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n % (10 ** (size - 1))
      for nums in product(range(1, 10), repeat = k - 1)
    )
print(count)

Submission status: Accepted

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

# dp[i桁まで][非0個数][未満フラグ]
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:
N = input()
K = int(input())

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n2 = N[j:le]
    
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Accepted

Solution code:
n = list(map(int,list(input())))
k = int(input())
l = len(n)
count = 0 # 0でない数字がnに何度出てきたか
lst = [[0]*(k+1) for _ in range(l+1)] #nより小さい
for i in range(l):
    if count < k:
        if n[i] != 0:
            lst[i+1][count] += 1
            lst[i+1][count+1] += n[i]-1
    if count == k:
        if n[i] != 0:
            lst[i+1][count] += 1
    for j in range(k):
        lst[i+1][j] += lst[i][j]
        lst[i+1][j+1] += 9*lst[i][j]
    lst[i+1][k] += lst[i][k]
    if n[i] != 0:
        count += 1
if count == k:
    print(lst[l][k]+1)
else:
    print(lst[l][k])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
l = len(n)
dp = [[[0]*(k+1) for i in range(2)] for j in range(l+1)]
d = []
for i in range(l):
    d.append(int(n[i]))
dp[1][0][0] = 0
dp[1][0][1] = 1
dp[1][1][0] = 1
dp[1][1][1] = d[0]-1

for i in range(l):
    for small in range(2):
        for j in range(k+1):
            if j==k:
                if small==0 and d[i]==0:
                    dp[i+1][small][j] += dp[i][small][j]
                else:
                    dp[i+1][1][j] += dp[i][small][j]
            else:
                a = 10 if small else d[i]+1
                for x in range(a):
                    z=j if x==0 else j+1
                    dp[i+1][small or x<d[i]][z] += dp[i][small][j]


print(dp[l][0][k]+dp[l][1][k])

Submission status: Accepted

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = input()
    p = int(input())
    l = len(n)

    n_0 = int(str(n)[0])

    dp = [[[0] * 2 for _ in range(p + 2)] for __ in range(l)]
    dp[0][0][0] = 0
    dp[0][0][1] = 1
    dp[0][1][0] = 1
    dp[0][1][1] = (n_0 - 1)

    for i in range(l - 1):
        a = int(n[i + 1])
        if a != 0:
            for j in range(p + 1):
                dp[i + 1][j + 1][0] += dp[i][j][0]
                dp[i + 1][j + 1][1] += 9 * dp[i][j][1] + (a - 1) * dp[i][j][0]
                dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
        else:
            for j in range(p + 1):
                dp[i + 1][j + 1][1] += 9 * dp[i][j][1]
                dp[i + 1][j][0] += dp[i][j][0]
                dp[i + 1][j][1] += dp[i][j][1]

    print(dp[l - 1][p][0] + dp[l - 1][p][1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# E - Almost Everywhere Zero
n=int(input())
K=int(input())
s=str(n)
n=len(s)
ans=0

dp=[[[0]*2 for j in range(K+1)] for i in range(n+1)]
dp[0][0][0]=1
for i in range(n):
    for j in range(K+1):
        for k in range(2):
            # if i>=n:continue
            nd=int(s[i])
            for d in range(10):
                ni=i+1
                nj=j
                nk=k
                if d!=0:nj+=1
                if nj>K:continue
                # k=0:nより小さいことが確定していない
                # k=1:nより小さいことが確定している
                if k==0:
                    # 次の桁が超えるとNG
                    if d>nd:continue
                    if d<nd:nk+=1
                dp[ni][nj][nk]+=dp[i][j][k]

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

Submission status: Accepted

Solution code:
def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + mondai(d, 1)
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = int(mondai(n, k))
    
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N = list(map(int, input()))
K = int(input())

nlen = len(N)
ans = 0
if K <= nlen:
    cmb = [9] * nlen
    for n in N:
        if n != 0:
            cmb[0] = n - 1
            for x in combinations(cmb, K):
                y = x[0]
                for z in x[1:]:
                    y *= z
                ans += y
            if K == 1:
                ans += 1
                break
            K -= 1
        cmb.pop()
print(ans)

Submission status: Accepted

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

l=len(N)
dp0=[[1,0,0,0] for _ in range(l+1)]
dp1=[[0,0,0,0] for _ in range(l+1)]

d=int(N)//10**(l-1)
dp0[0][1],dp1[0][1]=d-1,1

for i,c in enumerate(list(N)[1:]):
  d=int(c)
  for j in range(1,4):
    dp0[i+1][j]=dp0[i][j]+9*dp0[i][j-1]+(dp1[i][j] if d>0 else 0)+((d-1)*dp1[i][j-1] if d>1 else 0)
    dp1[i+1][j]=dp1[i][j-1] if d>0 else dp1[i][j]

print(dp0[l-1][K]+dp1[l-1][K])

Submission status: Accepted

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


def solve(N: "List[int]", K: int):
    print(dfs(N, False, 0, K, 0))


def dfs(N: "List[int]", f: bool, num: int, K: int, idx: int):
    if num == K:
        return 1
    if K - num > len(N) - idx:
        return 0
    else:
        if f:
            return dfs(N, True, num, K, idx + 1) + dfs(N, True, num + 1, K, idx + 1) * 9
        else:
            s = 0
            for i in range(N[idx] + 1):
                if i == N[idx]:
                    if i == 0:
                        s += dfs(N, False, num, K, idx + 1)
                    else:
                        s += dfs(N, False, num + 1, K, idx + 1)
                else:
                    if i == 0:
                        s += dfs(N, True, num, K, idx + 1)
                    else:
                        s += dfs(N, True, num + 1, K, idx + 1)
            return s


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = list(map(int, next(tokens)))  # type: List[int]
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
n=int(input())
k=int(input())
s=str(n)
l=len(s)
dp0=[[0 for j in range(k+1)] for i in range(l)]
dp1=[[0 for j in range(k+1)] for i in range(l)]

x=int(s[0])
dp0[0][1]=x-1
dp0[0][0]=1
dp1[0][1]=1
for i in range(1,l):
    x=int(s[i])
    dp0[i][0]=1

    for j in range(1,k+1):
        dp0[i][j]+=dp0[i-1][j-1]*9+dp0[i-1][j]
        if x>0:
            dp0[i][j]+=dp1[i-1][j-1]*(x-1)+dp1[i-1][j]
            dp1[i][j]=dp1[i-1][j-1]
        else:
            dp1[i][j]=dp1[i-1][j]

print(dp0[l-1][k]+dp1[l-1][k])

Submission status: Accepted

Solution code:
from sys import stdin

N = stdin.readline().rstrip()
K = int(stdin.readline().rstrip())

N = N[::-1]

dp = [[0] * len(N) for i in range(3)]

dp[0][0] = int(N[0])

for i in range(1, len(N)):
    if N[i] == '0':
        dp[0][i] = dp[0][i - 1]
    else:
        dp[0][i] = int(N[i]) + 9 * i

for i in range(1, len(N)):
    if N[i] == '0':
        dp[1][i] = dp[1][i - 1]
    else:
        dp[1][i] = dp[0][i - 1] + 9 * 9 * i * (i - 1)  // 2 + 9 * i * (int(N[i]) - 1)

for i in range(2, len(N)):
    if N[i] == '0':
        dp[2][i] = dp[2][i - 1]
    else:
        dp[2][i] = dp[1][i - 1] + 9 * 9 * 9 * i * (i - 1) * (i - 2) // 6 + 9 * 9 * i * (i - 1) // 2 * (int(N[i]) - 1)

print(dp[K - 1][len(N) - 1])

Submission status: Accepted

Solution code:
n=input()
K=int(input())
m=len(n)

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:DP[i][flag or k<num][j] +=DP[i-1][flag][j-1]

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

Submission status: Accepted

Solution code:
import math
import sys

comb=[0,0,0,1,3,6,10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950]
n=int(input())
k=int(input())
s=str(n)
L=len(s)

ans=0
if n<k:
    ans=0

elif k==1:
    for i in range(L):
        for a in range(1,10):
            if a*(10**i)<=n:
                ans+=1

elif k==2:
    for i in range(1,L):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=n: ans+=1


elif k==3 and L<4:
    for a in range(1,10):
        for b in range(1,10):
            for c in range(1,10):
                if a*100+b*10+c<=n: ans+=1

elif k==3 and L>=4:
    ans=sum(comb[:L])*9**3
    ans+=comb[L]* 81 * (int(s[0])-1)

    m=int(s[1:])
    for i in range(1,L-1):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=m: ans+=1

print(ans)

Submission status: Accepted

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

a = 1
b = [0] * (K + 1)
b[0] = 1
b[1] = int(N[0]) - 1

for c in N[1:]:
    t = int(c)
    for i in range(K - 1, -1, -1):
        b[i + 1] += b[i] * 9
    if t != 0:
        if a + 1 <= K:
            b[a + 1] += t - 1
        if a <= K:
            b[a] += 1
        a += 1

if a == K:
    print(b[K] + 1)
else:
    print(b[K])

Submission status: Accepted

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

a = [0] * (K + 1)
b = [0] * (K + 1)

t = int(N[0])

a = 1
b[0] = 1
b[1] = t - 1

for c in N[1:]:
    t = int(c)
    for i in range(K - 1, -1, -1):
        b[i + 1] += b[i] * 9
    if t != 0:
        if t != 1 and a + 1 <= K:
            b[a + 1] += t - 1
        if a <= K:
            b[a] += 1
        a += 1

if a == K:
    print(b[K] + 1)
else:
    print(b[K])

Submission status: Accepted

Solution code:
s = input()
K = int(input())
N = len(s)
dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(105)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(4):
        for k in range(2):
            nd = ord(s[i]) - ord('0')
            for d in range(10):
                ni, nj, nk = i + 1, j, k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
ans = dp[N][K][0] + dp[N][K][1]
print(ans)

Submission status: Accepted

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

for i in range(1, n+1):
    l = int(N[i-1])
    for k in range(K+1):
        dp[i][1][k] += dp[i-1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i-1][0][k]
        else:
            dp[i][0][k] += dp[i-1][0][k]
        if k-1 >= 0:
            dp[i][1][k] += dp[i-1][1][k-1]*9
            if l != 0:
                dp[i][0][k] += dp[i-1][0][k-1]
                dp[i][1][k] += dp[i-1][0][k-1]*(l-1)
                
print (dp[n][0][K]+dp[n][1][K])