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())
lenn=len(n)
dp=[[[0]*2 for i in range(k+1)] for j in range(lenn)]
dp[0][1][1]+=int(n[0])-1
dp[0][0][1]+=1
dp[0][1][0]+=1
for i in range(1,lenn):
  keta=int(n[i])
  for j in range(k):
    dp[i][j+1][1]+=dp[i-1][j][1]*9
    dp[i][j][1]+=dp[i-1][j][1]
    if keta>0:
      dp[i][j+1][1]+=dp[i-1][j][0]*(keta-1)
      dp[i][j+1][0]+=dp[i-1][j][0]
      dp[i][j][1]+=dp[i-1][j][0]
    else:
      dp[i][j][0]+=dp[i-1][j][0]
  dp[i][k][1]+=dp[i-1][k][1]
  if keta>0:
    dp[i][k][1]+=dp[i-1][k][0]
  else:
    dp[i][k][0]+=dp[i-1][k][0]
print(dp[lenn-1][k][1]+dp[lenn-1][k][0])

Submission status: Accepted

Solution code:
n = input()
k = int(input())
l = len(n)
dp0 = [[0 for _ in range(k+1)] for i in range(l+1)]
dp1 = [[0 for _ in range(k+1)] for i in range(l+1)]
dp0[0][0] = 1
for i in range(l):
  t = int(n[i])
  for j in range(k+1):
    if j == 0:
      dp0[i+1][j] = 0 if t != 0 else dp0[i][j]
      dp1[i+1][j] = dp1[i][j]
      if t != 0:
        dp1[i+1][j] += dp0[i][j]
    else:
      if t != 0:
        dp0[i+1][j] =  dp0[i][j-1]
      else:
        dp0[i+1][j] = dp0[i][j]
      dp1[i+1][j] = dp1[i][j] + dp1[i][j-1]*9
      if t != 0:
        dp1[i+1][j] += dp0[i][j]
      dp1[i+1][j] += dp0[i][j-1]*max(t-1, 0)
print(dp0[l][k] + dp1[l][k])

Submission status: Accepted

Solution code:
N=input()
K=int(input())
M=len(N)
dp=[[[0]*(K+1) for i in (0,1)] for j in range(M+1)]
dp[0][0][0]=1

for i in range(M):
   for smaller in (0,1):
      for no_zero_number in range(K+1):
         for x in range(10):
            #print("############")
            #print("i:",i)
            #print("smaller:",bool(smaller))
            #print("no_zero:",no_zero_number)
            #print("x:",x)
            if smaller==0 and x>int(N[i]):
               continue
            if x==0:
               dp[i+1][smaller or x<int(N[i])][no_zero_number]+=dp[i][smaller][no_zero_number]
            else:
               if no_zero_number+1>K:
                  continue
               else:
                  dp[i+1][smaller or x<int(N[i])][no_zero_number+1]+=dp[i][smaller][no_zero_number]
            #print(dp)
#print(dp)
print(dp[M][1][K]+dp[M][0][K])

Submission status: Accepted

Solution code:
def f(s, t, k):
 n = len(s)
 if k > n: return 0
 a = max(t, int(s[0]))
 if a == 0: return f(s[1:], t, k)
 if k == 1: return a + (n - 1) * 9
 z = 0
 if k - 1 <= n: z += f(s[1:], 9, k)
 z += (a - 1) * f(s[1:], 9, k - 1)
 z += f(s[1:], t, k - 1)
 return z

s = input()
k = int(input())
print(f(s, 0, k))

Submission status: Accepted

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

X = str(N+1)

dp = [[[0] * (K+1) for _ in range(2)] for _ in range(len(X)+1)]
#dp[i桁目][未満フラグ、0ならばそこまでの桁はNと同じ。1ならばすでにN以下が確定][k個の非ゼロを使う]
dp[0][0][0] = 1

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


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

Submission status: Accepted

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


def main(d, k):
    if d == L:
        if k == 0:
            return 1
        else:
            return 0
    if N[d] == "0":
        return main(d + 1, k)
    if (L - d) < k:
        return 0
    if k == 0:
        return 1
    return main1(d+1, k)+main1(d+1, k-1)*(int(N[d])-1)+main(d+1, k-1)


lmain1 = [[-1 for j in range(K+1)] for i in range(L+1)]


def main1(d, k):
    if d == L:
        if k == 0:
            return 1
        else:
            return 0
    if k == 0:
        return 1
    if lmain1[d][k] != -1:
        return lmain1[d][k]
    ret = main1(d+1, k-1)*9+main1(d+1, k)
    lmain1[d][k] = ret
    return ret


print(main(0, K))

Submission status: Accepted

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

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

dp[0][0][0]=1
for i in range(m):
  keta=int(n[i])
  for j in range(3):
    dp[i+1][j+1][1]+=9*dp[i][j][1]
    dp[i+1][j][1]+=dp[i][j][1]
    
    if keta>0:
      dp[i+1][j+1][1]+=dp[i][j][0]*(keta-1)
      dp[i+1][j][1]+=dp[i][j][0]
      dp[i+1][j+1][0]+=dp[i][j][0]
    else:
      dp[i+1][j][0]+=dp[i][j][0]
      
  dp[i+1][3][1]+=dp[i][3][1]
  dp[i+1][3][keta>0]+=dp[i][3][0]
print(dp[m][k][0]+dp[m][k][1])

Submission status: Accepted

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

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

di = int(N[0])
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = di-1

for i in range(1, digit):
    dp[i][1][0] = 1
    for k in range(1, K+1):
        di = int(N[i])
        if di == 0:
            dp[i][0][k] = dp[i-1][0][k]
            dp[i][1][k] = dp[i-1][1][k] + dp[i-1][1][k-1]*9
        else:
            dp[i][0][k] = dp[i - 1][0][k - 1]
            dp[i][1][k] = dp[i-1][0][k-1]*(di-1)+dp[i-1][0][k]\
                      +dp[i-1][1][k]+dp[i-1][1][k-1]*9


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

Submission status: Accepted

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

dp = [[[0]*(2) for i in range(k+1)] for j in range(len(str(n))+1)]

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

for i in range(len(str(n))):
    for j in range(k+1):
        for m in range(2):
            nd = int(str(n)[i])
            for l in range(10):
                ni = i+1
                nj = j
                nm = m
                if l != 0:
                    nj += 1
                if nj > k:
                    continue
                if nm == 0:
                    if  l > nd:
                        continue
                    elif l < nd:
                        nm = 1
                dp[ni][nj][nm] += dp[i][j][m]
print(dp[len(str(n))][k][0]+dp[len(str(n))][k][1])

Submission status: Accepted

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

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

cd = int(N[0])
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = cd-1

for i in range(1, digit):
    for k in range(K+1):
        cd = int(N[i])
        if k == 0:
            dp[i][1][0] = 1
        else:
            if cd == 0:
                dp[i][0][k] = dp[i-1][0][k]
                dp[i][1][k] = dp[i-1][1][k] + dp[i-1][1][k-1]*9
            else:
                dp[i][0][k] = dp[i - 1][0][k - 1]
                dp[i][1][k] = dp[i-1][0][k-1]*(cd-1)+dp[i-1][0][k]\
                          +dp[i-1][1][k]+dp[i-1][1][k-1]*9


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

Submission status: Accepted

Solution code:
# ref: https://atcoder.jp/contests/abc154/submissions/9991364

from functools import lru_cache

#0以上N以下の整数で、0でない数字がちょうどK個あるものの個数
@lru_cache(None)
def F(N, K):
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        else:
            return 0
    
    q,r = divmod(N,10)

    ans = 0
    if K >= 1:
        # 1の位が0ではない
        ans += F(q, K-1) * r
        ans += F(q-1, K-1) * (9-r)
    # 1の位が0
    ans += F(q, K)
    
    return ans

def main():
    N = int(input())
    K = int(input())

    print(F(N,K))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = input()
L = len(N)
K = int(input())
dp = [[[0 for k in range(2)]for j in range(K+1)]for i in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
    p = int(N[i])
    ni = i+1
    for j in range(K+1):
        for k in range(2):
            for d in range(10):
                nk = k
                nj = j
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if nk == 0:
                    if d > p:
                        continue
                    if d < p:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
print(dp[L][K][0]+dp[L][K][1])

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    K = int(f_i.readline())
    S = str(N)
    
    
    import numpy as np
    # dp[digit][below flag][number of non-0]
    dp = np.zeros((len(S) + 1, 2, K + 1), dtype=int)
    dp[0][0][0] = 1
    digits = (int(c) for c in S)
    
    for i, d in enumerate(digits):
        for j in (0, 1):
            for k in range(K):
                if j:
                    dp[i+1][j][k+1] += dp[i][j][k] * 9
                    dp[i+1][j][k] += dp[i][j][k]
                else:
                    if d:
                        dp[i+1][1][k+1] += dp[i][j][k] * (d - 1)
                        dp[i+1][j][k+1] += dp[i][j][k]
                        dp[i+1][1][k] += dp[i][j][k]
                    else:
                        dp[i+1][j][k] += dp[i][j][k]
                    
    ans = np.sum(dp[:, :, K])
    
    print(ans)

solve()

Submission status: Accepted

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

from math import factorial

str_n = str(N)
len_n = len(str(str_n))

def conb(n, r):
    return factorial(n)//factorial(r)//factorial(n-r)
    
def get_num(top, k_val, depth):
    if k_val==0:
        return 1
    elif k_val>(len_n-depth+1):
        return 0
    elif top:
        if int(str_n[depth - 1])==0:
            return get_num(top, k_val, depth + 1)
        else:
            b1 = get_num(top, k_val - 1, depth + 1)
            b2 = (int(str_n[depth-1])-1) * get_num(False, k_val-1, depth+1)
            b3 = get_num(False, k_val, depth + 1)
            return b1+b2+b3
    else:
        return 9**(k_val) * conb(len_n - depth + 1, k_val)
    
    
a1 = get_num(True, K-1, 2)
a2 = (int(str_n[0])-1)*get_num(False, K-1, 2)
a3 = get_num(False, K, 2)

#print(a1, a2, a3)
print(a1+a2+a3)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve_1(N):
    N_str = str(N)
    ans = 0
    for i, ch in enumerate(N_str):
        if i == 0:
            ans += int(ch)
        else:
            ans += 9
    return ans

def solve_2(N):
    N_str = str(N)

    # N = 70543 だとする

    # {1..6}XXXX:
    # XXXXのうち1箇所が1..9のどれか、他はすべて0
    ans = (int(N_str[0]) - 1) * 9 * (len(N_str) - 1)

    # 7XXXX:
    # XXXXの前から順に見ていく
    # ありえるパターンは 7{1..9}000, 70{1..9}00, 700{1..9}0, 7000{1..9}
    # 前から順に考えていく
    # 7{1..9}000 に関しては、1..9のどれも入れない。 +0通り
    # 70{1..9}00 に関しては、1..5のどれかが入れる。 +5通り
    # 700{1..9}0 に関しては、1..9の全部が入れる。この桁よりも前に非0の桁があったため。+9通り
    # 7000{1..9} に関しては、1..9の全部が入れる。 +9通り
    flag = False
    for ch in N_str[1:]:
        if flag:
            ans += 9
        else:
            ans += int(ch)
            if ch != '0':
                flag = True

    # XXXX:
    # 4箇所どこにも1..9の全部が入れる
    for i in range(1, len(N_str) - 1):
        ans += 81 * i

    return ans

def solve_slow_2(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 2
    return ans

# for n in range(1, 10000):
#     mine = solve_2(n)
#     gt = solve_slow_2(n)
#     if mine != gt:
#         print("error! n, mine, gt = ", n, mine, gt)
#         sys.exit(0)
#     else:
#         print(n, "ok")


def solve_3(N):
    N_str = str(N)
    size = len(N_str)

    # N = 70543 だとする

    # {1..6}XXXX:
    # XXXXのうち2箇所が1..9のどれか、他はすべて0
    ans = (int(N_str[0]) - 1) * (((size - 1) * (size - 2)) // 2) * 81

    # 7XXXX:
    # "2つだけ非0でXXXXより小さい数"を数えればよい。solve_2を使うと解ける
    if size > 1:
        ans += solve_2(int(N_str[1:]))

    # X:
    # XX:
    # XXX:
    # XXXX:
    # の場合をループで順番に加算
    # 例えばXXXXの場合、
    # 最初の桁は{1..9}, 残り3桁のうちの2つが{1..9}なので
    # 場合の数は9 * 9 * 9 * 3C2
    for size in range(1, len(N_str)):
        ans += 9 * 9 * 9 * (size - 1) * (size - 2) // 2

    return ans

def solve_slow_3(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 3
    return ans


# for n in range(1, 10000):
#     mine = solve_3(n)
#     gt = solve_slow_3(n)
#     if mine != gt:
#         print("error! n, mine, gt = ", n, mine, gt)
#         sys.exit(0)
#     else:
#         print(n, "ok")
        

def solve(N, K):
    if K == 1:
        return solve_1(N)
    elif K == 2:
        return solve_2(N)
    else:
        return solve_3(N)


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

print(solve(N, K))

Submission status: Accepted

Solution code:
import os
import sys
from functools import lru_cache

from scipy.misc import comb

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = [int(sys.stdin.buffer.readline()) for _ in range(2)]
N = str(N)


@lru_cache(maxsize=None)
def solve(d, k):
    # 下d桁でk個選ぶ
    if d <= 0:
        return 0
    if k == 0:
        return 1
    n = int(N[-d])
    if d == 1:
        if k == 0:
            return 1
        elif k == 1:
            return n
        else:
            return 0
    if n == 0:
        return solve(d - 1, k)
    ret = 0
    # n を選ぶ
    ret += solve(d - 1, k - 1)
    # n より小さい数を選ぶ
    ret += comb(d - 1, k - 1, exact=True) * (n - 1) * 9 ** (k - 1)
    # 0 を選ぶ
    ret += comb(d - 1, k, exact=True) * 9 ** k
    return ret


ans = solve(len(N), K)
print(ans)

Submission status: Accepted

Solution code:
import math

def com(n, r):
  if r < 0 and r > n:
    return 0
  
  if r == 1:
    return n
  elif r == 2:
    return n * (n-1) / 2
  else:
    return n * (n-1) * (n-2) / 6

def pow(n, k):
  res = 1
  for i in range(k):
    res *= n

  return res

def solve(i, k, smaller):
  global P
  global N

  if i == P:
    if k == 0:
      return 1
    else:
      return 0

  if k == 0:
    return 1

  if smaller:
    return com(P-i, k) * pow(9, k)
  else:
    if (N[i] == '0'):
      return solve(i+1, k, False)
    else:      
      a = solve(i+1, k, True)
      b = solve(i+1, k-1, True) * (int(N[i]) - 1)
      c = solve(i+1, k-1, False)
      return a + b + c
    
N = input()
K = input()

P = len(N)

print(math.floor(solve(0, int(K), False)))

Submission status: Accepted

Solution code:
import sys


def main():
    n = int(sys.stdin.readline().strip())
    k = int(sys.stdin.readline().strip())

    digits = 0
    nc = n
    while nc:
        nc //= 10
        digits += 1

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

    for i in range(digits):
        digit = (n // (10 ** (digits - 1 - i))) % 10
        ndp = [[0] * (k+2) for _ in range(2)]
        for j in range(k+1):
            ndp[1][j] += dp[1][j]  # 0
            ndp[1][j+1] += dp[1][j] * 9

            if digit == 0:
                ndp[0][j] += dp[0][j]
            else:
                ndp[1][j] += dp[0][j]  # 0
                ndp[1][j+1] += dp[0][j] * (digit-1)  # less
                ndp[0][j+1] += dp[0][j]  # same
        dp = ndp
    print(dp[1][k] + dp[0][k])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def K1(n):
    ans = 0
    d = len(str(n))
    ans += int(str(n)[0])
    ans += 9 * (d-1)
    return ans


def K2(n):
    d = len(str(n))
    ans = 9**2*(d-2)*(d-1)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K1(int(str(n)[1:]))
    return ans


def K3(n):
    d = len(str(n))
    ans = 0
    for i in range(2,d-1):
        ans += i*(i-1)//2
    ans *= 9**3
    ans += (int(str(n)[0]) - 1) * 9**2 * (d-1)*(d-2) // 2
    ans += K2(int(str(n)[1:]))
    return ans


def main():
    N = int(input())
    K = int(input())

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

    if K == 2:
        if N < 10:
            print(0)
            exit()
        print(K2(N))

    if K == 3:
        if N < 100:
            print(0)
            exit()
        print(K3(N))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def factorial(n):
    a = 1
    for i in range(1, n + 1):
        a *= i
    return a

def nCr(n,r):
    if r > n:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def normal(d, k):
    #print("normal d,k ", d, k)
    return nCr(d, k) * (9**k)

def main():
    tmp = input()
    N = [int(c) for c in tmp]
    D = len(N)
    K = int(input())
    #print(D, K)

    x = 0
    ans1, ans2, ans3, ans4, ans5, ans6 = 0, 0, 0, 0, 0, 0
    if K == 1:
        ans1 = normal(D-1, K)
        ans2 = N[0]
    elif K == 2:
        ans1 = normal(D-1, K)
        ans2 = (N[0] - 1) * normal(D-1, K-1)
        x = 1
        found = False
        for i in range(x, D):
            if N[i] != 0:
                x = i
                found = True
                break
        if found:
            if x == D - 1:
                ans4 = N[x]
            else:
                ans3 = normal(D-(x+1), K-1)
                ans4 = N[x]
    elif K == 3:
        ans1 = normal(D-1, K)
        ans2 = (N[0] - 1) * normal(D-1, K-1)
        x = 1
        found = False
        for i in range(x, D):
            if N[i] != 0:
                x = i
                found = True
                break
        if found:
            if x == D - 1:
                pass
            else:
                ans3 = normal(D-(x+1), K-1)
                ans4 = (N[x] - 1) * normal(D-(x+1), K-2)
                x = x + 1
                found = False
                for i in range(x, D):
                    if N[i] != 0:
                        x = i
                        found = True
                        break
                if found:
                    if x == D - 1:
                        ans6 = N[x]
                    else:
                        ans5 = normal(D-(x+1), K-2)
                        ans6 = N[x]

    #print("ans1", ans1)
    #print("ans2", ans2)
    #print("ans3", ans3)
    #print("ans4", ans4)
    #print("ans5", ans5)
    #print("ans6", ans6)

    ans = ans1+ans2+ans3+ans4+ans5+ans6
    #print("ans", ans)
    print(ans)

main()

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
if i == n-1:
    if k == 0:
        ans += 1
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

Submission status: Accepted

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

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

for d in n:
    ndp = [[0] * (k + 2) for _ in range(2)]
    for i in range(k + 1):
        ndp[1][i] += dp[1][i]
        ndp[1][i + 1] += dp[1][i] * 9
        if d == '0':
            ndp[0][i] += dp[0][i]
        else:
            ndp[1][i] += dp[0][i]
            ndp[1][i + 1] += dp[0][i] * (int(d) - 1)
            ndp[0][i + 1] += dp[0][i]
    dp = ndp
print(dp[0][k] + dp[1][k])

Submission status: Accepted

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

L = list(map(int, list(str(N))))
M = len(L)
DP = [[[0] * 2 for _ in range(K + 1)] for _ in range(M)]

DP[0][1] = [L[0] - 1, 1]
DP[0][0][0] = 1

for i in range(1, M):
  DP[i][0][0] = DP[i - 1][0][0]
  for j in range(1, K + 1):
    if L[i] != 0:
      DP[i][j][0] = DP[i - 1][j][0]
      DP[i][j][0] += DP[i - 1][j][1]
      DP[i][j][0] += DP[i - 1][j - 1][0] * 9
      DP[i][j][0] += DP[i - 1][j - 1][1] * (L[i] - 1)
      DP[i][j][1] = DP[i - 1][j - 1][1]
    else:
      DP[i][j][0] = DP[i - 1][j][0]
      DP[i][j][0] += DP[i - 1][j - 1][0] * 9
      DP[i][j][1] = DP[i - 1][j][1]

ans = DP[-1][-1][0] + DP[-1][-1][1]
ans = max(0, ans)
print(ans)

Submission status: Accepted

Solution code:
import math as m

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

def f(n,k):
    l = len(str(n))
    if l < k:
        ans = 0
    elif k == 0:
        ans = 1
    elif l == k:
        t = 10 ** (k-1)
        ans = (n//t-1) * f(t-1, k-1) + f(n%t,k-1)
    else:
        ans =  m.factorial(l-1) // m.factorial(k) // m.factorial(l-1-k) * (9 ** k)
        t = n % (10**(l-1))
        ans += f(t,k-1) + f(10**(l-1)-1,k-1)* (n// (10**(l-1))-1)
    return ans

ans = f(n,k)

print(ans)

Submission status: Accepted

Solution code:
import math

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

def f(n,k):
    l = len(str(n))
    if l < k:
        ans = 0
    elif k == 1:
        ans = 9 * (l-1)
        ans += n//(10**(l-1))
    elif l == k:
        t = 10 ** (k-1)
        ans = (n//t-1) * f(t-1, k-1) + f(n%t,k-1)
    else:
        ans =  math.factorial(l-1) // math.factorial(k) // math.factorial(l-1-k) * (9 ** k)
        t = n % (10**(l-1))
        ans += f(t,k-1) + f(10**(l-1)-1,k-1)* (n// (10**(l-1))-1)
    return ans

ans = f(n,k)

print(ans)

Submission status: Accepted

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

digits = len(n)

dp_le = [[0 for j in range(k+1)] for i in range(digits)]
dp_lt = [[0 for j in range(k+1)] for i in range(digits)]

dp_le[0][0] = 0
dp_le[0][1] = 1
dp_lt[0][0] = 1
dp_lt[0][1] = n[0]-1

for i in range(1, digits):
    for j in range(k+1):
        if n[i] == 0:
            dp_le[i][j] = dp_le[i-1][j]
            dp_lt[i][j] = dp_lt[i-1][j]
            if j > 0:
                dp_lt[i][j] += dp_lt[i-1][j-1]*9
        else:
            dp_lt[i][j] = dp_lt[i-1][j] + dp_le[i-1][j]
            if j > 0:
                dp_le[i][j] += dp_le[i-1][j-1]
                dp_lt[i][j] += dp_lt[i-1][j-1]*9 + dp_le[i-1][j-1] * (n[i] - 1)

print(dp_le[digits-1][k] + dp_lt[digits-1][k])

Submission status: Accepted

Solution code:
S = input().strip()
N = len(S)
K = int(input())
dp = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp[0][K] = 1
dp2[0][K] = 1
for i in range(N):
    for j in range(K+1):
        dp[i+1][j] = dp[i][j]
        if j != K: dp[i+1][j] += dp[i][j+1] * 9
    dd = int(S[N-i-1])
    for j in range(K+1):
        if dd == 0:
            dp2[i+1][j] = dp2[i][j]
        else:
            if j != K:
                dp2[i+1][j] = dp[i][j] + dp[i][j+1]*(dd-1) + dp2[i][j+1]
            else:
                dp2[i+1][j] = dp[i][j]
print(dp2[N][0])

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(n+5)]
 
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:  # 0以外が一個増える
                    nj += 1
                if nj > K:  # これ以上0以外使えないとき
                    continue
                if k == 0:  # そこまでの桁はNと一致しているとき
                    if d > nd:  # Nを超えてしまう
                        continue
                    if d < nd:  # N以下確定である
                        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:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

MOD = 10**9 + 7

def cone(n):
    if n == 0:
        return 0
    else:
        return n

def ctwo(n):
    if n <= 1:
        return 0
    else:
        return(n * (n-1)) // 2

def ketaall(keta, m):
    if m == 0:
        return 1
    if m == 1:
        return keta * 9
    else:
        return ctwo(keta) * 81


def main():
    n = getN()
    n = str(n)
    keta = len(n) - 1
    m = getN()
    if m == 1:
        res = 0
        print(int(int(n[0]) + 9 * keta))
        return

    res = (int(n[0]) - 1)*  ketaall(keta, m -1)
    # print(res, n[0], n, keta)
    for k in range(int(keta)):
        res += 9 * ketaall(k, m-1)
        # print(res)

    m -= 1
    # print("====================")
    for s in n[1:]:
        if s == "0":
            pass
        else:
            res += ketaall(keta - 1, m)
            # print(res)
            res += (int(s) - 1) * ketaall(keta-1, m-1)
            # print(res)
            m -= 1

        keta -= 1
        # print(res, m)
        if m == 0:
            res += 1
            break

    print(res)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
K = INT()

dp0 = list2d(N+1, 107, 0)
dp1 = list2d(N+1, 107, 0)
dp0[0][0] = 1
for i in range(N):
    num = int(S[i])
    for j in range(107):
        for k in range(10):
            nxt = j+1 if k != 0 else j
            if nxt == 107:
                continue
            if k < num:
                dp1[i+1][nxt] += dp0[i][j]
                dp1[i+1][nxt] += dp1[i][j]
            elif k == num:
                dp0[i+1][nxt] += dp0[i][j]
                dp1[i+1][nxt] += dp1[i][j]
            else:
                dp1[i+1][nxt] += dp1[i][j]
ans = dp0[N][K] + dp1[N][K]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

N = input()
K = int(input())
lN = len(N)

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,2):
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += (int(N[0])-1)*9*9
                    ans += (int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += (int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += (int(N[0])-1)*9*9
    print(ans)

Submission status: Accepted

Solution code:
import itertools

N = input()
K = int(input())
lN = len(N)

if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 >= v[1]:
                ans += (int(N[0])-1)*9 + int(N[v[1]])
            else:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s >= v[2]:
                    ans += (int(N[0])-1)*9*9
                    ans += max(0,int(N[v[1]])-1)*9
                    ans += int(N[v[2]])
                else:
                    ans += (int(N[0])-1)*9*9
                    ans += int(N[v[1]])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
            else:
                ans += (int(N[0])-1)*9*9

    print(ans)