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 = int(input())
K = int(input())
memo = {}

def F(N, K):
    """
    F(N, K) = (1以上N以下で0でない桁がちょうどK個なものの個数)
    Nを一の桁から見ていくことで再帰で求める
    （例）F(314,3) = F(31,2)*4 + F(30,2)*5 + F(31,3)
                      = {F(3,1) + F(2,1)*8 + F(3,2)} * 4
                            + {F(2,1)*9 + F(3,2)} * 5
                            + {F(3,2) + F(2,2)*8 + F(3,3)}
                      = ...
    """
    r = int(str(N)[-1])
    M = (N - r) // 10
    if K == 0 and N >= 0:
        return 1
    elif K == 0 and N <= -1:
        return 0
    elif N <= 0:
        return 0
    else:
        return F(M, K-1) * r + F(M-1, K-1) * (9-r) + F(M, K)

print(F(N, K))

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import lru_cache

N = input().strip()
K = int(input().strip())
lenN = len(N)

#memo = defaultdict(lambda :defaultdict(lambda :defaultdict(int)))
@lru_cache(maxsize=None)
def f(keta, flag, k):
    if keta == lenN-1:
        if k == K:
            return 1
        else:
            return 0
    #if keta in memo and flag in memo[keta] and k in memo[keta][flag]:
    #    return memo[keta][flag][k]
    nketa = keta + 1
    maxi = int(N[nketa]) if flag else 9
    res = 0
    for i in range(maxi+1):
        nflag = flag and (int(N[nketa]) == i)
        nk = k if i == 0 else k + 1
        if nk > K:
            continue
        res += f(nketa, nflag, nk)
    #memo[keta][flag][k] = res
    return res

print(f(-1, True, 0))

Submission status: Accepted

Solution code:
from collections import defaultdict

N = input().strip()
K = int(input().strip())
lenN = len(N)

memo = defaultdict(lambda :defaultdict(lambda :defaultdict(int)))
def f(keta, flag, k):
    if keta == lenN-1:
        if k == K:
            return 1
        else:
            return 0
    if keta in memo and flag in memo[keta] and k in memo[keta][flag]:
        return memo[keta][flag][k]
    nketa = keta + 1
    maxi = int(N[nketa]) if flag else 9
    res = 0
    for i in range(maxi+1):
        nflag = flag and (int(N[nketa]) == i)
        nk = k if i == 0 else k + 1
        if nk > K:
            continue
        res += f(nketa, nflag, nk)
    memo[keta][flag][k] = res
    return res

print(f(-1, True, 0))

Submission status: Accepted

Solution code:
import numpy as np

N = input().strip()
K = int(input().strip())
lenN = len(N)

dp = np.zeros((lenN+1, 2, 4))
dp[0][1][0] = 1
for keta in range(lenN):
    for flag in range(2):
        for k in range(K+1):
            for i in range(10):
                nk = k
                nflag = flag
                if flag:
                    if i > int(N[keta]):
                        continue
                    if i < int(N[keta]):
                        nflag = 0
                if i != 0:
                    nk = k + 1
                if nk > K:
                    continue
                dp[keta+1][nflag][nk]+=dp[keta][flag][k]

print(int(dp[lenN][0][K] + dp[lenN][1][K]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def combinations(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return combinations(n-1,r-1) + combinations(n-1,r)

def main():
    n = input().rstrip()
    k = int(input())
    if k == 1:
        print((int(n[0]) - 1) + 9 * (len(n) -  1) + 1)
    elif k == 2:
        a = (int(n[0]) - 1) * 9 * (len(n) - 1)
        b = int(combinations(len(n) - 1, 2) * 9*9)
        c = 0
        for i in range(1, len(n)):
            if n[i] != '0':
                c = int(n[i]) + 9 * (max(len(n) - i - 1, 0))
                break
        print(a + b + c)
    elif k == 3:
        a_a = 0
        a_b = 0
        a_c = 0
        for i in range(1, len(n)):
            if n[i] != '0':
                for j in range(i+1, len(n)):
                    if n[j] != '0':
                        a_a = int(n[j]) + 9 * (max(len(n) - j - 1, 0))
                        break
                a_b = (int(n[i]) - 1) * 9 * (max(len(n) - i - 1, 0))
                a_c = combinations(len(n) - i - 1, 2) * 9 * 9
                break
        b = (int(n[0]) - 1) * combinations(len(n) - 1, 2) * 9 * 9
        c = combinations(len(n) - 1, 3) * 9 * 9 * 9
        print((a_a + a_b + a_c) + b + c)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    s = list(input())
    n = len(s)
    large_k = int(input())
    # KeyInsight: 桁DP
    # dp[i][j][k]
    # i桁目、j個の非0、k:そこまでの桁がNと一致する(0), N未満(1)
    ## i, kは典型的な状態、jに気が付けるかどうか
    # See:
    # http://hiroto1979.hatenablog.jp/entry/2016/03/18/224631
    dp = [[[0 for k in range(2)] for j in range(4)] for i in range(105)]
    ## なぜ初期値が1になる?
    dp[0][0][0] = 1

    # See:
    # https://www.youtube.com/watch?v=JQmQjJd-sLA&feature=youtu.be
    # http://drken1215.hatenablog.com/entry/2019/02/04/013700
    # https://torus711.hatenablog.com/entry/20150423/1429794075
    for i in range(n):
        for j in range(4):
            for k in range(2):
                # 次の桁の数字
                nd = int(s[i])

                # 各桁で0〜9を試す
                for digit in range(10):
                    ni, nj, nk = i + 1, j, k

                    # 遷移ができるかどうかを判定
                    ## 遷移できない条件を列挙して、計算をしないようにする
                    # ある桁で、0以外の数字を使う
                    if digit != 0:
                        nj += 1

                    # 0でない数字がK個より大きいときは、遷移しない
                    if nj > large_k:
                        continue

                    # ある桁まで見たときに、Nと一致する
                    if k == 0:
                        # ある桁の数字より大きいときは、遷移しない
                        if digit > nd:
                            continue
                        # 小さいときは、Nと一致しない(=それ以降の桁にはどんな数字を入れてもよい)
                        elif digit < nd:
                            nk = 1

                    dp[ni][nj][nk] += dp[i][j][k]

    # N未満とNの合計
    print(dp[n][large_k][0] + dp[n][large_k][1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 1
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

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

Submission status: Accepted

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


def main():
    s = list(input())
    n = len(s)
    large_k = int(input())
    dp = [[[0 for k in range(2)] for j in range(4)] for i in range(105)]
    dp[0][0][0] = 1

    # See:
    # https://www.youtube.com/watch?v=JQmQjJd-sLA&feature=youtu.be
    for i in range(n):
        for j in range(4):
            for k in range(2):
                nd = int(s[i])

                for digit in range(10):
                    ni, nj, nk = i + 1, j, k

                    if digit != 0:
                        nj += 1
                    if nj > large_k:
                        continue
                    if k == 0:
                        if digit > nd:
                            continue
                        if digit < nd:
                            nk = 1

                    dp[ni][nj][nk] += dp[i][j][k]

    print(dp[n][large_k][0] + dp[n][large_k][1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:



N = input()
K = int(input())
L = len(N)
"""
dp[i][j][k]：Nを頭からi桁まで見たとき、残りの使える0以外の個数がj個で、そこまでの値がNのi-1桁目までより小さい/同じ（小さいとk=1）時のi桁目までのとりうる個数
"""
dp = [[[0 for _ in range(2)] for _ in range(K+1)] for _ in range(L+1)]
dp[0][K][0] = 1

for i in range(L):
    digit = int(N[i])
    for num_rest_non_zero in range(K+1):
        for flag_less in range(2):
            """
            ・先頭はN[0]以下の値で決める
            ・もし現時点でNより小さいなら、次のi桁目は0以外の数字を使える個数に余裕があれば、
            i桁目に1~9まで使うこともできるし、0を使うこともできる
            ・既に0以外を使える個数がなくなって（使い切って）いれば、0をあてるしかない
            ・i-1桁目までがNと一致している（flag_less = 0）であれば、nのi桁目以下の値からしか選べない
            """

            # 先頭はN[0]以下の値しか選べない
            if i == 0:
                d = digit
            elif num_rest_non_zero == 0:
                d = 0
            elif flag_less == 1:
                d = 9
            else:
                d = digit

            for num in range(d+1):
                
                if flag_less == 0 and num == digit:
                    flag_less_nxt = 0
                else:
                    flag_less_nxt = 1

                # 0以外を使う場合
                if num != 0:
                    dp[i+1][num_rest_non_zero-1][flag_less_nxt] += dp[i][num_rest_non_zero][flag_less]
                else:
                    # i桁目に0をあてるので残数が減らない
                    dp[i+1][num_rest_non_zero][flag_less_nxt] += dp[i][num_rest_non_zero][flag_less]


print(sum(dp[L][0]))
#print(dp)

Submission status: Accepted

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

# dp[i][j][k]
# i : 桁数
# j : 非0を使った数
# k : そこまでの桁がs（指定された最大値）と一致しているか？、0なら一致してない、1なら一致してる
dp = [[[0 for i in range(2)] for j in range(4)] for k in range(105)]

# i = 0は、与えられた整数の一つ左の桁（上位の桁）に０があると仮定した時に
# そのパターンは１つしかない状態を持たない（i=0, j=0, k=1）ため初期値を設定している
dp[0][0][1] = 1

# debug_msg = "dp[{}][{}][{}] = {}"
for i in range(n):
  for j in range(4):
    for k in range(2):
      # sのi桁目を取得
      nd = int(s[i])
      # 各桁について0~9のパターンを考える
      for d in range(10):
        ni = i + 1
        nj = j
        nk = k
        if (d != 0): nj += 1
        if (nj > K): continue
        if (k == 1):
          if (d > nd): continue
          if (d < nd): nk = 0
        dp[ni][nj][nk] += dp[i][j][k]
        # print(debug_msg.format(ni, nj, nk, dp[ni][nj][nk]))

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

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#main

@lru_cache(maxsize=None)#メモ化デコレータ
def f(num,k):
    if(num==0 and k==0):return 1
    elif(num<=0 or k<0):return 0
    else:
        r=num-(num//10)*10
        m=num//10
        return f(m,k-1)*r+f(m-1,k-1)*(9-r)+f(m,k)
s=int(input())
k=int(input())
print(f(s,k))

Submission status: Accepted

Solution code:
n = input().strip()
k = int(input().strip())
le = len(n)
dp = [[[0] * 2 for _ in range(5)] for _ in range(101)]
dp[0][0][0] = 1

for i in range(le):
    for cnt in range(4):
        for smaller in range(2):
            fig = int(n[i])
            for d in range(10):
                tmp1 = i + 1
                tmp2 = cnt
                tmp3 = smaller
                if d != 0:
                    tmp2 += 1
                if k < cnt:
                    continue
                if smaller == 0:
                    if fig < d:
                        continue
                    elif d < fig:
                        tmp3 = 1
                dp[tmp1][tmp2][tmp3] += dp[i][cnt][smaller]
print(dp[le][k][0] + dp[le][k][1])

Submission status: Accepted

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

#output
def K_is_one(n):
    p = len(str(n))
    q = int(str(n)[0])
    return q + 9*(p-1)

def K_is_two(n):
    p = len(str(n))
    q = int(str(n)[0])
    if p == 1:
        return 0
    elif p == 2:
        return n - K_is_one(n)
    else:
        r = int(str(n)[1:])
        temp = 0
        for i in range(1, p-1):
            temp += 9*K_is_one(int("9"*i))
        temp += (q-1) * K_is_one(int("9"*(p-1))) + K_is_one(r)
        return temp

def K_is_three(n):
    p = len(str(n))
    q = int(str(n)[0])
    if p == 1:
        return 0
    elif p == 2:
        return 0
    else:
        r = int(str(n)[1:])
        temp = 0
        for i in range(1, p-1):
            temp += 9*K_is_two(int("9"*i))
        temp += (q-1) * K_is_two(int("9"*(p-1))) + K_is_two(r)
        return temp

if K == 1:
    print(K_is_one(N))
elif K == 2:
    print(K_is_two(N))
else:
    print(K_is_three(N))

Submission status: Accepted

Solution code:
#coding:utf-8

N = input()
K = int(input())
dp = [[[0 for _ in range(K+2)] for _ in range(2)] for _ in range(len(N) + 1)]
# 桁数、未満フラグ、状態数
dp[0][0][0] = 1

for i in range(len(N)):
    for smaller in range(2):
        for k in range(K+1):
            # 三つ目のインデックスに条件が入る
            for x in range(10 if smaller == 1 else int(N[i]) + 1):
                dp[i + 1][smaller == 1 or x < int(N[i])][k + 1 if x != 0 else k] += dp[i][smaller][k]
print(dp[len(N)][0][K] + dp[len(N)][1][K])

Submission status: Accepted

Solution code:
#coding:utf-8

N = input()
K = int(input())
dp = [[[0 for _ in range(K+2)] for _ in range(2)] for _ in range(len(N) + 1)]
# 桁数、０以外が出た回数、未満フラグ
dp[0][0][0] = 1

for i in range(len(N)):
    for smaller in range(2):
        for k in range(K+1):
            for x in range(10 if smaller == 1 else int(N[i]) + 1):
                dp[i + 1][smaller == 1 or x < int(N[i])][k + 1 if x != 0 else k] += dp[i][smaller][k]
print(dp[len(N)][0][K] + dp[len(N)][1][K])

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    K=I()
    N=len(S)
    dp = [[[0]*2 for _ in range(K+1)]for _ in range(N+1)] #dp[i][count_not_zero][less]
    dp[0][0][0] = 1
    for i in range(N):
        for count_not_zero in range(K+1):
            for less in range(2):
                if less:
                    upper = 10
                else:
                    upper = int(S[i])+1
                for j in range(upper):
                    try:
                        dp[i+1][count_not_zero + (j!=0)][less or (j<int(S[i]))] += dp[i][count_not_zero][less]
                    except:
                        pass
    print(sum(dp[-1][K]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 7)

# 桁DP
# 非再帰

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

# dp[n桁目まで決まってる][Non-Zeroの個数][Nと一致? 0:一致している 1:一致していない]
dp = [[[0] * 2 for _ in range(4)] for _ in range(N + 1)]

# n=0 桁目の値は、0として、それはKの値には関係なく、Nと一致している
dp[0][0][0] = 1

# i,j,kのうち、小さい方から埋めていく
for i in range(N):
    for j in range(4):
        for k in range(2):
            # 今決めようとしているの桁の値
            d = int(S[i])

            # 次の桁の値のループ(0-9)
            for nextd in range(10):
                # 次の桁を決めたあとのj,k
                nextj = j
                nextk = k

                # 次の桁がNon-Zero
                if nextd != 0:
                    nextj += 1
                # K個を超えたらいらない
                if nextj > K:
                    continue

                # 前の桁までNと一致していた場合
                # 使える数に制限あり
                if k == 0:
                    if d < nextd:
                        continue
                    elif nextd < d:
                        nextk = 1

                        # 前までの個数と同じ分の場合の数
                dp[i + 1][nextj][nextk] += 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())
L = len(str(N))
dp1 = [[0 for _ in range(K+1)] for _ in range(L+1)]
dp2 = [[0 for _ in range(K+1)] for _ in range(L+1)]
count = 0
for i in range(L+1):
    dp1[i][0] = 0
count = 0
for i, c in enumerate(str(N)):
    c = int(c)
    if i == 0:
        dp1[i+1][0] = 1
        dp1[i+1][1] = c-1
        dp2[i+1][1] = 1
        count = 1
        continue

    for j in range(0, K+1):
        if c == 0:
            dp2[i+1][j] += dp2[i][j]
        else:
            if j != K:
                dp2[i+1][j+1] += dp2[i][j]
    for j in range(0, K+1):
        if c != 0:
            dp1[i+1][j] += dp2[i][j]
        dp1[i+1][j] += dp1[i][j]


        if j != K:
            if count >= K:
                dp1[i+1][j+1] += dp2[i][j] * 9
                dp1[i+1][j+1] += dp1[i][j] * 9
            else:
                dp1[i+1][j+1] += dp2[i][j]*max(0, (c-1))
                dp1[i+1][j+1] += dp1[i][j]*9
    #print(dp1)
    #print(dp2)
print(dp1[-1][-1] + dp2[-1][-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 12 17:17:55 2020

@author: matsui
"""
def check(N,K):
    ans=0
    for i in range(N+1):
        c=0
        for s in str(i):
            if int(s)!=0: c+=1
        if c==K: ans+=1
    return ans

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

ans=0
if K==1:
    ans=int(N[0])+(L-1)*9
           
if K==2:
    dp=[0]*(L+1)
    for i in range(2,L):
        dp[i]=9*9*(i-1)
          
    dp[L]=(int(N[0])-1)*9*(L-1)
    
    for i in range(1,L):
        if int(N[i])!=0:
            dp[L]+=int(N[i])+9*(L-i-1)
            break
     
    ans=sum(dp)
    
if K==3:
    dp=[0]*(L+1)
    for i in range(3,L):
        dp[i]=9*(dp[i-1]/9+9*9*(i-2))
        
        
    dp[L]=(int(N[0])-1)*(dp[L-1]/9+9*9*(L-2))
    
    for i in range(1,L):
        if int(N[i])!=0:
            dp[L]+=(int(N[i])-1)*9*(L-i-1)+9*9*(L-i-1)*(L-i-2)/2
            break
        
    for j in range(i+1,L):
        if int(N[j])!=0:
            dp[L]+=int(N[j])+9*(L-j-1)
            break
        
    
    
           
    ans=sum(dp)
    
print(int(ans))
#print(check(int(N),K))

Submission status: Accepted

Solution code:
# 桁DPの練習にきました

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

dp = {}


def rec(i, smaller, count):
    if (i, smaller, count) in dp:
        return dp[(i, smaller, count)]
    if i == len(n):
        dp[(i, smaller, count)] = 1 if count == k else 0
        return dp[(i, smaller, count)]
    ret = 0
    upper = 10 if smaller else int(n[i]) + 1
    for j in range(upper):
        ret += rec(
            i + 1,
            True if smaller or j < int(n[i]) else False,
            count + 1 if 0 < j else count,
        )
    dp[(i, smaller, count)] = ret
    return ret


print(rec(0, False, 0))

Submission status: Accepted

Solution code:
n=input()
l=len(n)
K=int(input())
dp=[[[0]*2 for i in range(4)]for j in range(105)]
dp[0][0][0]=1
for i in range(l):
    for j in range(4):
        for k in range(2):
            nd=int(n[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 nd>d:
                        nk=1
                    if nd<d:
                        continue
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[l][K][1]+dp[l][K][0])

Submission status: Accepted

Solution code:
"""
# 0じゃない数字がちょうどK個
dp[i][k][s] 
上からi桁目までみて、
0じゃない数字がk個。
上i桁が一致していたら0,違っていたら1
"""
S = input()
K = int(input())
m = len(S) #桁数

dp = [[[0]*2 for j in range(5)] for i in range(110)]

# 何も決めていない状態で,1以上を使ったのが0で、0桁目まで一致している
dp[0][0][0] = 1
for i in range(m):
    for j in range(4):
        for k in range(2):
            # Sの今の桁 n_digit
            digit = int(S[i])
            i_next = i + 1            
            # 次の桁(0から9)に対して遷移を考える
            for d in range(10):
                # j : 0の数について
                if d == 0: 
                    j_next = j
                else: 
                    j_next = j + 1
                if j_next > K: 
                    #0じゃない数がKを超えたら遷移しない
                    continue
                # k : 最大を取るか問題について
                if k == 0:
                    if d > digit: 
                        continue #Nを超える
                    elif d == digit: 
                        k_next = 0 #一致
                    else: 
                        k_next = 1
                else:
                    k_next = 1 # 変わることはない
                # 今の状態から0~9の遷移先
                dp[i_next][j_next][k_next] += dp[i][j][k]

ans = sum(dp[m][K])
print(ans)

Submission status: Accepted

Solution code:
n = input()
K = int(input())
dp = [[[0]*(2) for _ in range(4)] for _ in range(105)]

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

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

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

Submission status: Accepted

Solution code:
import sys
import socket

hostname = socket.gethostname()

if hostname in ['F451C', 'N551J']:
    sys.stdin = open('e1.in')


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


def read_str_list():
    return input().split()


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


def read_str():
    return input()

def solve(N, K):
  s = list(reversed(str(N)))
  a = [i for i in range(len(s)) if s[i] != '0']
  c = [int(s[i]) for i in range(len(s)) if s[i] != '0']

  # print(a)
  # print(c)
  res = 0
  if K == 1:
    for p in range(100):
      if p == a[-1]:
        res += c[-1]
      if p < a[-1]:
        res += 9

  if K == 2:
    for p in range(100):
      for q in range(p):
        if p < a[-1]:
          res += 9 * 9
        if p == a[-1]:
          if len(a) >= 2:
            if q < a[-2]:
              res += c[-1] * 9
            if q == a[-2]:
              res += (c[-1] - 1) * 9 + c[-2]
            if q > a[-2]:
              res += (c[-1] - 1) * 9
          if len(a) == 1:
            res += (c[-1] - 1) * 9

  if K == 3:
    for p in range(100):
      for q in range(p):
        for r in range(q):
          if p < a[-1]:
            res += 9 * 9 * 9
          if p == a[-1]:
            if len(a) >= 3:
              if q < a[-2]:
                res += c[-1] * 9 * 9
              if q == a[-2]:
                if r < a[-3]:
                  res += (c[-1] - 1) * 9 * 9
                  res += 1 * (c[-2] - 1) * 9
                  res += 1 * 1 * 9
                if r == a[-3]:
                  res += (c[-1] - 1) * 9 * 9
                  res += 1 * (c[-2] - 1) * 9
                  res += 1* 1 * c[-3]
                if r > a[-3]:
                  res += (c[-1] - 1) * 9 * 9
                  res += 1 * (c[-2] - 1) * 9
                  
              if q > a[-2]:
                res += (c[-1] - 1) * 9 * 9
            if len(a) == 2:
              if q < a[-2]:
                res += c[-1] * 9 * 9
              if q == a[-2]:
                res += (c[-1] - 1) * 9 * 9
                res += 1 * (c[-2] - 1) * 9
              if q > a[-2]:
                res += (c[-1] - 1) * 9 * 9
            if len(a) == 1:
              res += (c[-1] - 1) * 9 * 9


  return res


def solve_correct_but_slow(N, K):
  res = 0
  for i in range(1, N+1):
    s = str(i)
    nonzero = len(s) - s.count('0')
    if nonzero == K:
      res += 1
  return res


def find_mismatch():
  N = 1
  while True:
    for K in range(1, 4):
      expected = solve_correct_but_slow(N, K)
      output = solve(N, K)


      if output == expected:
        # print('   N, K, expected, output:', end=' ')
        # print(N, K, expected, output)
        continue

      print()
      print('N, K, expected, output:', end=' ')
      print(N, K, expected, output)
      return
    N += 1




def main():
    N = read_int()
    K = read_int()
    res = solve(N, K)
    print(res)

# find_mismatch()
main()

Submission status: Accepted

Solution code:
def comb(a, b):
    ans = 1
    for i in range(b):
        ans *= (a - i)
    for i in range(2, b + 1):
        ans //= i
    return ans

def solve_k1(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    ans += 9 * (len_N - 1)
    ans += int(N[0])
    return ans

def solve_k2(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    if len_N < 2:
        return 0
    ans = comb((len_N - 1), 2) * 9 ** 2 + (int(N[0]) - 1) * ((len_N - 1) * 9) + solve_k1(int(N[1:]))
    return ans

def solve_k3(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    if len_N < 3:
        return 0
    ans = comb(len_N - 1, 3) * 9 ** 3 + (int(N[0]) - 1) * comb(len_N - 1, 2) * 9 ** 2 + solve_k2(int(N[1:]))
    return ans

N = int(input())
K = int(input())
ans = 0
if K == 1:
    ans = solve_k1(N)
elif K == 2:
    ans = solve_k2(N)
else:
    ans = solve_k3(N)
print(ans)

Submission status: Accepted

Solution code:
import math
def check1(N):
    if N == 0:
        return 0
    n = int(math.log10(N))
    return 9*n+(N//(10**n))
def check2(N):
    if N == 0:
        return 0
    n = int(math.log10(N))
    return n*(n-1)/2*81+(N//(10**n)-1)*n*9+check1(N%(10**n))
def check3(N):
    if N == 0:
        return 0
    n = int(math.log10(N))
    summ = 0
    if n >= 3:
        for i in range(n):
            summ += i*(i-1)/2
    return summ*729+(N//(10**n)-1)*n*(n-1)/2*81+check2(N%(10**n))
def main():
    N = int(input())
    K = int(input())
    if K == 1:
        print(int(check1(N)))
    elif K == 2:
        print(int(check2(N)))
    elif K == 3:
        print(int(check3(N)))
        
main()

Submission status: Accepted

Solution code:
#maspyさんのやつ

from functools import lru_cache

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

@lru_cache(None)
def f(n, k):
    assert n >= 0 #例外処理
    if n < 10:
        if k == 0:
            return 1 #0しかない数 = 0
        elif k == 1:
            return n #k = 1ならn個分存在している
        return 0 #k >= 2のときは、0を返す
    
    q, r = divmod(n, 10)
    res = 0
    
    if k >= 1:
        #1の位が0でないとき
        res += f(q, k-1) * r
        res += f(q-1, k-1) * (9 - r)
    #１の位が0
    res += f(q, k)
    return res

print(f(n, k))

Submission status: Accepted

Solution code:
def solve2():
    N = raw_input()
    K = int(raw_input())
    L = len(N)
    digN = [int(d) for d in N]
    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):
        for j in range(K+1):
            for k in range(2):
                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 > digN[i]:
                            continue
                        if d < digN[i]:
                            nk = 1
                    dp[ni][nj][nk] += dp[i][j][k]
    print dp[L][K][0] + dp[L][K][1]

if __name__ == '__main__':
    solve2()

Submission status: Accepted

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

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

def COUNT(N,K):
    digit = list(map(int, str(N)))
    M = len(digit)
    C = count(digit[0], M, K)
    N_ = N % pow(10, M-1)
    return C, N_
    

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

C = 0
while (N>0) and (K>0):
    c, N = COUNT(N, K)
    C+= c
    K-= 1

print(C)