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 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)
    if len(digit) > 1:
        N_ = int("".join(map(str, digit[1:])))
    else:
        N_ = 0
    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)

Submission status: Accepted

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

def dp(N,K):
    keta = len(str(N))
    table = [[[0,0] for i in range(K+1)] for j in range(keta+1)]
    table[0][0][0]=1
    for i in range(keta):
        for j in range(K+1):
            for k in range(2):
                enable_num = int(str(N)[i]) if k==0 else 9
                for x in range(enable_num+1):
                    if x==0:
                        next_j = j
                    else:
                        next_j = j + 1
                    if next_j > K: continue
                    if k == 0 and x == enable_num:
                        next_k = 0
                    else:
                        next_k = 1
                    table[i+1][next_j][next_k]+=table[i][j][k]
    return table[keta][K][0] + table[keta][K][1]
print(dp(N,K))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32
from functools import lru_cache



def solve(N: int, K: int):
    @lru_cache(None)
    def f(n: int, k:int):
        if n < 10:
            if k == 0:
                # n <= 9 and k == 0のときは0個
                return 1
            elif k == 1:
                # n <= 9 and k == 1のときは、1-9の9個
                return n
            else:
                # n <= 9でk == 2以上の時は、解がない
                return 0

        return f(n//10, k-1)*(n%10) + f(n//10-1, k-1) *(9-n%10) + f(n//10, k)


    print(f(N, K))

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

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

def rec(n, k, smaller):
    n = n.lstrip('0')

    if k == 0:
        return 1

    if len(n) < k:
        return 0

    if k == 1:
        if len(n) == 1:
            return int(n)


    if smaller:
        return nCr(len(n), k) * 9 ** k


    ret = 0
    ret += rec(n[1:], k-1, False)
    ret += rec('9'*(len(n)-1), k-1, True) * (int(n[0]) - 1)
    ret += rec('9'*(len(n)-1), k, True)

    return ret
    
ans = rec(N, K, False)
print(ans)

Submission status: Accepted

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

dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
  for b in range(k + 1):
    for c in range(2):
      nd = int(s[a])
      for d in range(10):
        na, nb, nc = a + 1, b, c
        if d != 0:
          nb += 1
        if nb > k:
          break
        if nc == 0:
          if d < nd:
            nc  = 1
          if d > nd:
            break
        dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
  for b in range(k + 1):
    for c in range(2):
      nd = int(s[a])
      for d in range(10):
        na, nb, nc = a + 1, b, c
        if d != 0:
          nb += 1
        if nb > k:
          break
        if nc == 0:
          if d < nd:
            nc = 1
          if d > nd:
            break
        dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

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

for a in range(n):
  for b in range(k + 1):
    for c in range(2):
      nd = int(s[a])
      for d in range(10):
        na, nb, nc = a + 1, b, c
        if d != 0:
          nb += 1
        if nb > k:
          break
        if nc == 0:
          if d < nd:
            nc = 1
          if d > nd:
            break
        dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import numpy as np

nrow = input()
k = int(input())

l = len(nrow)

dp = np.zeros((l, 2, 4), int)
topmax = int(nrow[0])
dp[0, 0, 1] = 1  # =topmax
dp[0, 1, 0] = 1  # =0
dp[0, 1, 1] = topmax-1  # <topmax

for i in range(1, l):
  topmax = int(nrow[i])

  dp[i, 1, 0] = dp[i-1, 1, 0]  # =0
  for j in range(1,4):
    dp[i, 1, j] = dp[i-1, 1, j] + dp[i-1, 1, j-1] * 9  # =0,any

  if topmax == 0:
    for j in range(1, 4):
      dp[i, 0, j] = dp[i-1, 0, j]  #=0
  else:
    dp[i, 0, 2] = dp[i-1, 0, 1]  # =topmax,
    dp[i, 0, 3] = dp[i-1, 0, 2]  # =topmax,
    dp[i, 1, 1] += dp[i-1, 0, 1] # =0,<topmax
    dp[i, 1, 2] += dp[i-1, 0, 2]+dp[i-1, 0, 1] * (topmax-1)  # =0,<topmax
    dp[i, 1, 3] += dp[i-1, 0, 3]+dp[i-1, 0, 2] * (topmax-1)  # =0,<topmax

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

Submission status: Accepted

Solution code:
#ABC154-E Almost Everywhere Zero

#桁DP

"""
問題：
n以下の0以外の数字の数が丁度k個である整数の個数を求めよ。

解法：
桁DP
以下の条件があったら桁DPを疑うべし
・桁に関している
・制約が大きい
・整数nがある範囲を動くときの、〜〜〜の最大値を求めよ
・整数nがある範囲を動くときの、〜〜〜という条件を満たすものは何通りあるか←今回はコッチ

考え方：
桁DPでは上位桁から条件を絞っていって、下位桁にクエリを出すという再帰方法で解く。この時、何回もこの再帰をやっていると
下位桁が全く同じ条件になることが出現するので、それをメモ化、呼び出しして動的に解く。
そのためのdpテーブルは３次元で、各階層に対応するのは以下のようなデータ。

dp[i][j][k] = (上から)i桁まで見た,j個Kを使った,k=0:制約ありk=1:自由     の時の条件を満たす場合の個数(value)

問題により多少dpテーブルの内容や順番は異なるが、i桁目まで見た、と、自由度kについての制約は必ずテーブルの中に入る。
もうひとつ、今回で言えばjのテーブルは、kをいくつ使ったか、全桁の合計がD以下であるみたいな問題はいま合計はいくらか
みたいなデータになる。
"""

n = input() #桁DPの場合、nはstr型で取る
m = len(n)
K = int(input()) #DPテーブルのkとかぶって紛らわしいので、大文字にする

dp = [[[0]*2 for j in range(4)] for i in range(105)]
dp[0][0][0] = 1
for i in range(m): #m=桁数
    for j in range(4): #0以外の数はj回使っている
        for k in range(2): #制約,自由の2通り(制約がかかってから気にするんじゃなくて、
            #最初から全桁に制約がかかってるもんだと思って全部計算する)
            nd = int(n[i]) #その桁の数字(制約ありの時に使う)
            for d in range(10): #下位桁に対して10回(0~9まで)まわす
                ni = i+1 #下位桁に
                nj = j #0以外を使った回数はj回
                nk = k #制約か自由か
                if d != 0: nj += 1 #その桁を0だと仮定して場合、現在までの0の個数+=1
                if nj > K: continue #0の個数がKを超えていたら条件を満たさない
                if k == 0: #制約ありの場合
                    if d > nd:continue #その桁の制約を超えていたら飛ばす
                    if d < nd:nk = 1 #逆にd未満ならば、下位桁は自由になるので、k=1:自由にしてやる
                #この下位桁に対するforループを全て満たした時、dpテーブルを更新
                dp[ni][nj][nk] += dp[i][j][k]

ans = dp[m][K][0] + dp[m][K][1] #制約ありでもなしでも良いので、両方足す

print(ans)

Submission status: Accepted

Solution code:
import math
def combi(n,r):
    if r > n:return 0
    return math.factorial(n) // (math.factorial(n - r)*(math.factorial(r)))


def solve(i,k,smaller):
    #一番最後の桁まで調べたら終了
    if i == N:
        if k == 0:return 1
        else: return 0

    #途中であっても0以外の数字を使い切ったら終了
    if k == 0:return 1

    #Nより小さいことが確定すれば残りの桁数（N-i）のうち
    #k個所に0以外の数字（9**k通り）を使い，それ以外の桁の数字は0なので
    #C(n-i,n-i-k)=C(n-i,k)個所に0をはめる
    if smaller: return combi(N-i, k)*(9**k)
    else:
        #i桁目が0なら，smallerであるといえない
        if S[i] == '0':return solve(i+1,k,False)
        else:
            zero = solve(i+1, k, True)
            aida = solve(i+1, k-1, True) * (int(S[i])-1)
            icchi = solve(i+1, k-1, False)
            return zero + aida + icchi

#0出ない数字がちょうどＫ個であるようなN以下の整数を探索
S = input()
N = len(S)
K = int(input())
print((solve(0,K,False)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def cmb(n, k):
    # print(n,k)
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n)
    b = factorial(k)
    c = factorial(n - k)
    return a // b // c

def dfs(i, k, lenn, sn):
    if k == 0:
        return 1
    if i == lenn:
        return 0
    if sn[i] == "0":
        return dfs(i + 1, k, lenn, sn)
    return cmb(lenn - i - 1, k) * 9 ** k + cmb(lenn - i - 1, k - 1) * 9 ** (k - 1) * (int(sn[i]) - 1) + dfs(i + 1, k - 1, lenn, sn)

#solve
def solve():
    n, k = IR(2)
    lenn = len(str(n))
    sn = str(n)
    ans = dfs(0,k,lenn,sn)
    print(int(ans))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=input()
k=int(input())
keta=len(n)
#桁dp
#dp0 n以下確定
#dp1 未確定
#dp[桁][個数]
dp0=[[0]*(k+1) for _ in range(keta)]
dp1=[[0]*(k+1) for _ in range(keta)]
dp0[0][0]=1
dp0[0][1]=int(n[0])-1
dp1[0][1]=1
for i in range(1,keta):
	if n[i]=="0":
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp0[i-1][j-1]*9+dp0[i-1][j]
	else:
		for j in range(1,k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(int(n[i])-1)+dp0[i-1][j-1]*9+dp0[i-1][j]
print(dp0[-1][k]+dp1[-1][k])

Submission status: Accepted

Solution code:
n=input()
k=int(input())
keta=len(n)
#桁dp
#dp0 n以下確定
#dp1 未確定
#dp[桁][個数]
dp0=[[0]*(k+1) for _ in range(keta)]
dp1=[[0]*(k+1) for _ in range(keta)]
dp0[0][0]=1
dp0[0][1]=int(n[0])-1
dp1[0][1]=1
for i in range(1,keta):
	# if n[i]=="0":
	# 	for j in range(k+1):
	# 		dp1[i][j]=dp1[i-1][j]
	# 	dp0[i][0]=dp0[i-1][0]
	# 	for j in range(k+1):
	# 		dp0[i][j]=dp0[i-1][j-1]*9+dp0[i-1][j]
	if n[i]=="0":
		conf=dp0
		notconf=dp1
		for j in range(k+1):
			notconf[i][j]=notconf[i-1][j]
		conf[i][0]=conf[i-1][0]
		for j in range(1,k+1):
			conf[i][j]=9*conf[i-1][j-1]+conf[i-1][j]
	else:
		for j in range(1,k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(int(n[i])-1)+dp0[i-1][j-1]*9+dp0[i-1][j]
print(dp0[-1][k]+dp1[-1][k])

Submission status: Accepted

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

S = [ord(N[i]) - ord('0') for i in range(L)]

dp0 = [[0 for _ in range(K+1)] for _ in range(L)]
dp1 = [[0 for _ in range(K+1)] for _ in range(L)]

dp0[0][0] = 1
dp0[0][1] = S[0]-1
dp1[0][0] = 0
dp1[0][1] = 1

for i in range(1, L):
	for j in range(K+1):
		if j == 0:
			dp0[i][j] = dp0[i-1][j]
			dp1[i][j] = dp1[i-1][j]
		else:
			dp0[i][j] = dp0[i-1][j-1]*9 + dp0[i-1][j] 
			if S[i] > 0:
				dp0[i][j] = dp0[i][j] + dp1[i-1][j-1]*(S[i]-1) + dp1[i-1][j]
				
			dp1[i][j] = dp1[i-1][j-(S[i]>0)]
	
print(dp0[L-1][K] + dp1[L-1][K])

Submission status: Accepted

Solution code:
from functools import lru_cache
@lru_cache(None)
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:
n=input()
k=int(input())
L=len(n)
conf=[[0 for i in range(k+1)] for j in range(L)]
conf[0][1]=int(n[0])-1
conf[0][0]=1
notconf=[[0 for i in range(k+1)] for j in range(L)]
notconf[0][1]=1
for i in range(1,L):
    if n[i]=="0":
        for j in range(k+1):
            notconf[i][j]=notconf[i-1][j]
        conf[i][0]=conf[i-1][0]
        for j in range(1,k+1):
            conf[i][j]=9*conf[i-1][j-1]+conf[i-1][j]
    else:
        looking=int(n[i])
        for j in range(1,k+1):
            notconf[i][j]=notconf[i-1][j-1]
        conf[i][0]=conf[i-1][0]
        for j in range(1,k+1):
            conf[i][j]=notconf[i-1][j]+notconf[i-1][j-1]*(looking-1)+conf[i-1][j-1]*9+conf[i-1][j]
print(notconf[-1][k]+conf[-1][k])

Submission status: Accepted

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

"""
dp[i][j][k]
i: 決定した桁数
j: N以下確定
k: 0出ない数字がちょうどk個(k = 0,1,2,3)
   4個以上(k=4)
"""

def solve(a):
	a = str(a)
	L = len(a)
	dp = [[[0]*5 for i in range(2)] for j in range(L+1)]
	dp[0][0][0] = 1
	for i in range(L):
		D = int(a[i])
		for j in range(2):
			for k in range(5):
				for d in range(10 if j else D+1):
					if k>=4:
						dp[i+1][j or (d<D)][k] += dp[i][j][k]
					else:
						if d!=0:
							dp[i+1][j or (d<D)][k+1] += dp[i][j][k]
						else:
							dp[i+1][j or (d<D)][k] += dp[i][j][k]
	return dp[L][0][K] + dp[L][1][K]

print(solve(N))

Submission status: Accepted

Solution code:

def solve():
    N = raw_input()
    K = int(raw_input())
    L = len(N)
    # digN = []
    # rem = N
    # while (rem != 0):
    #     digN.append(rem%10)
    #     rem = rem / 10
    digN = [int(d) for d in N]
    dp0 = [[1 for i in range(K+1)] for i in range(L)]
    dp1 = [[1 for i in range(K+1)] for i in range(L)]
    dp0[0][0] = 1
    dp1[0][0] = 1
    dp0[0][1] = digN[L-1]
    dp1[0][1] = 9
    for i in range(2, K+1):
        dp0[0][i] = 0
        dp1[0][i] = 0
    for i in range(1, L):
        for j in range(1, K+1):
            if digN[L - 1 - i] > 0:
                dp0[i][j] = (digN[L - 1 - i] - 1) * dp1[i-1][j-1] + dp0[i-1][j-1] + dp1[i-1][j]
            else:
                dp0[i][j] = dp0[i-1][j]
            dp1[i][j] = 9 * dp1[i-1][j-1] + dp1[i-1][j]
    print dp0[L-1][K]

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

keta = len(N)

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

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

for i in range(1, keta + 1):
    for j in range(K + 1):
        if j > 0:
            dp[i][0][j] += dp[i-1][0][j-1] * (N[i-1] != '0')
            dp[i][1][j] += dp[i-1][0][j-1] * (max((int(N[i-1]) - 1),0)) + dp[i-1][1][j-1] * 9

        dp[i][0][j] += dp[i-1][0][j] * (N[i-1] == '0')
        dp[i][1][j] += dp[i-1][0][j] * (N[i-1] != '0') + dp[i-1][1][j]
        
ans = dp[keta][0][K] + dp[keta][1][K]
print(ans)

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:
"""
dp[i][j][k]
i桁で非零要素をj個含み, 
「k==0」→ Nのi桁目までと一致
「k==1」→ Nのi桁目までよりも小さい
"""

N = int(input())
K = int(input())
digit = len(str(N))
N_str = str(N)

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

dp[0][0][0] = 1
#配るDP
for i in range(digit): 
    for j in range(4): 
        for k in range(2):
            for d in range(10):
                ni = i+1; nj = j; nk = k
                nd = int(N_str[i])
                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[digit][K][1]+dp[digit][K][0]
#print(dp)
print(ans)

Submission status: Accepted

Solution code:
def f(n, k):
    if k == 0:
        return 1
    if k == 1 and n < 10:
        return n

    s = str(n)
    length = len(s)

    ans = g(length - 1, k)
    for i in range(1, int(s[0])):
        if 1 < k:
            ans += g(length - 1, k - 1)
        else:
            ans += 1
    if 1 < k:
        ans += f(n % 10 ** (length - 1), k - 1)
    elif k == 1:
        ans += 1
    return ans


def g(n, k):
    if n == 0:
        return 0
    if n < k:
        return 0
    if k == 1:
        return n * 9
    elif k == 2:
        return n * (n - 1) // 2 * 9 ** 2
    elif k == 3:
        return n * (n - 1) * (n - 2) // 6 * 9 ** 3


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

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
N = str(N)
dp = [[[0]*2 for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][1] = 1  # 初期化, まだ崩れていないという認識
# 遷移を考える
for i in range(len(N)):
    x = int(N[i])  # 上からi桁目を考える
    for j in range(K):
        # 崩れているものを増やしていく
        dp[i+1][j+1][0] += dp[i][j][0]*9  # 非ゼロを増やした
        dp[i+1][j][0] += dp[i][j][0]  # ゼロを使った
        # 崩れていないものについて
        if x > 0:
            dp[i+1][j][0] += dp[i][j][1]  # 0を使って崩す
            dp[i+1][j+1][0] += dp[i][j][1]*(x-1)  # x未満の数字を使って(jが増える)崩した場合
            dp[i+1][j+1][1] += dp[i][j][1]  # xをそのまま埋め込んで崩れていない状態を選んだ場合
        else:
            # 崩さない場合は、0を埋め込むしかないのでjは増えない
            dp[i+1][j][1] += dp[i][j][1]  # 0を埋め込む
    dp[i+1][K][0] += dp[i][K][0]
    dp[i+1][K][not x>0] += dp[i][K][1]
print(sum(dp[len(N)][K]))

Submission status: Accepted

Solution code:


ar = input()

k = int(input())

l = len(ar)


DP = [[[-1] * 2 for j in range(103)] for i in range(102)]


def dp(i, j, fl):
    if i == l:
        if j == k:
            return 1
        else:
            return 0

    if DP[i][j][fl] != -1:
        return DP[i][j][fl]

    res = 0

   # print(i,j,fl)
    if fl:
        for p in range(10):

            res += dp(i+1, j + (p != 0) , fl == 1)
    else:
        ko = ord(ar[i]) - ord('0')
        for p in range(ko + 1):

            res += dp(i + 1, j + (p != 0), p < ko)
    DP[i][j][fl] = res
    return res

print(dp(0, 0, 0))

Submission status: Accepted

Solution code:

"""dp1,2[i][j] 
i桁で0をj個含む数で, 
dp1→ Nの上からi桁目までを抽出した数より小さい
dp2→ Nの上からi桁目までを抽出した数に等しい
"""

N = int(input())
K = int(input())
digit = len(str(N))
N_str = str(N)

dp1 = [[0]*4 for _ in range(digit+1)]
dp2 = [[0]*4 for _ in range(digit+1)]

dp2[0][0] = 1

for i in range(1, digit+1):
    for j in range(4):
        if int(N_str[i-1]) != 0:
            if j >= 1:
                dp2[i][j] = dp2[i-1][j-1]
                dp1[i][j] = dp1[i-1][j]+9*dp1[i-1][j-1]+dp2[i-1][j]+dp2[i-1][j-1]*(int(N_str[i-1])-1)
            else:
                dp1[i][j] = dp1[i-1][j]+dp2[i-1][j]
        else:
            dp2[i][j] = dp2[i-1][j]
            if j >= 1:
                dp1[i][j] = dp1[i-1][j]+9*dp1[i-1][j-1]
            else:
                dp1[i][j] = dp1[i-1][j]

        #print(i, j, dp1[i][j], dp2[i][j])

ans = dp1[digit][K]+dp2[digit][K]

print(ans)

Submission status: Accepted

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

def f(n,k):
    l=[int(i) for i in str(n)]
    if n<100000:
        cnt=0
        for i in range(1,n+1):
            s=str(i)
            if len(s)-s.count('0')==k:
                cnt+=1
        return cnt
    else:
        if k==1:
            cnt=(len(l)-1)*9
            cnt+=l[0]
        elif k==2:
            cnt=(len(l)-1)*(len(l)-2)//2*9*9
            cnt+=(l[0]-1)*(len(l)-1)*9
            cnt+=f(n-10**(len(l)-1)*l[0],1)
        elif k==3:
            cnt=(len(l)-1)*(len(l)-2)*(len(l)-3)//6*9*9*9
            cnt+=(l[0]-1)*(len(l)-1)*(len(l)-2)//2*9*9
            cnt+=f(n-10**(len(l)-1)*l[0],2)
        return cnt
print(f(n,k))

Submission status: Accepted

Solution code:
N = [int(i) for i in str(input())]
m = len(N)
K = int(input())
dp = [[[0 for i in range(K + 1)],[0 for i in range(K + 1)]]   for i in range(m)]
#初期条件
dp[0][1][0] = 1
dp[0][0][1] = 1
dp[0][1][1] = N[0] - 1
for i in range(1,m):
    for t in range(0,min(i+2,K+1)):
        if N[i] != 0:
            if t == 0:
                dp[i][1][t] = dp[i-1][1][t]
            else:
                dp[i][0][t] = dp[i-1][0][t-1]
                dp[i][1][t] = dp[i-1][0][t] + dp[i-1][0][t-1] * (N[i]-1) + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
        else :
            if t == 0:
                dp[i][0][t] = dp[i-1][0][t]
                dp[i][1][t] = dp[i-1][1][t] 
            else :
                dp[i][0][t] = dp[i-1][0][t]
                dp[i][1][t] = dp[i-1][1][t] + dp[i-1][1][t-1] * 9
print(dp[-1][0][K]+dp[-1][1][K])

Submission status: Accepted

Solution code:
#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for k in range(min(i+1, K+1)):
            dp0, dp1 = dp[i], dp[i+1]

            dp1[1][k+1] += 9 * dp0[1][k]
            dp1[1][k]   +=     dp0[1][k]

            x, y = N[i], dp0[0][k]
            if x == 0:
                dp1[0][k] += y
            else:
                dp1[1][k] += y
                dp1[0][k+1] += y
                dp1[1][k+1] += (x-1) * y
        #print(dp1)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for k in range(i+1):
            dp0, dp1 = dp[i], dp[i+1]

            dp1[1][k+1] += 9 * dp0[1][k]
            dp1[1][k]   +=     dp0[1][k]

            x, y = N[i], dp0[0][k]
            if x == 0:
                dp1[0][k] += y
            else:
                dp1[1][k] += y
                dp1[0][k+1] += y
                dp1[1][k+1] += (x-1) * y
        #print(dp1)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for less in range(2):
            for k in range(i+1):
                for x in range(10 if less else N[i] + 1):
                    #print((i, less, k), x, (i+1, int(less or x < N[i]), k + (1 if x else 0)))
                    dp[i+1][less or x < N[i]][k + (1 if x else 0)] += dp[i][less][k]
        #print(dp[i+1])

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N=input() # 文字型
K=int(input())
m=len(N) # 桁数

# dp0[i][j]はi桁目までで、j個の0でない数があり、Nより小さいのが確定
# dp1[i][j]はi桁目までで、j個の0でない数があり、Nより小さいのが確定していない
dp0=[[0]*(m+1) for _ in range(m+1)]
dp1=[[0]*(m+1) for _ in range(m+1)]
dp1[0][0]=1
for i in range(1,m+1):
    dp0[i][0]=1

for i in range(m):
    for j in range(m):
        if N[i]=='0':
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]
            dp1[i+1][j+1]=dp1[i][j+1]
        else:
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]+ dp1[i][j]*(int(N[i])-1)+dp1[i][j+1]
            dp1[i+1][j+1]=dp1[i][j]
            
if m<K:
    print(0)
else:
    print(dp0[-1][K]+dp1[-1][K])

Submission status: Accepted

Solution code:
#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

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

    dp[0][0][0] = 1
    for i in range(size):
        for less in range(2):
            for k in range(size):
                for x in range(10 if less else N[i] + 1):
                    #print((i, less, k), x, (i+1, int(less or x < N[i]), k + (1 if x else 0)))
                    dp[i+1][less or x < N[i]][k + (1 if x else 0)] += dp[i][less][k]
        #print(dp[i+1])

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
K = int(input())
 
def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])
 
def keta2(n):
    if n < 10:
      return 0
    s = str(n)
    cnt = [0] * 101
    for i in range(2, 101):
        cnt[i] = 9 * 9 * (i - 1)
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta1(10 ** (len(s) - 1) - 1) + keta1(int(s[1:]))
    return res
 
def keta3(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(3, 101):
        cnt[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta2(10 ** (len(s) - 1) - 1) + keta2(int(s[1:]))
    return res
 
if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

Submission status: Accepted

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    if r == 1:
        return n
    elif r == 2:
        return n * (n-1) // 2
    else:
        return n * (n-1) * (n-2) // (3 * 2) 

def rec(i, k, isSmaller):
    if k == 0:
        return 1

    if i == N:
        return 0
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

Submission status: Accepted

Solution code:
from scipy.misc import comb

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

L = len(N)

if N.count("0") > L - K:
    integer = int(N)
    N = str(integer - integer % 10 - 1)

L = len(N)

if L < K or N[0] == "-":
    print(0)
    quit()

M = ["0"] * L
count = 0
for i in range(L):
    count += bool(int(N[i]))
    M[i] = N[i]
    if count == K:
        M = "".join(M)
        break

index = 0
ans = 0
count = 0
while index < L:
    if int(M[index]):
        count += 1
        n = L - index - 1
        k = K - count + 1
        digit = int(M[index]) - (count != K)
        ans += comb(n, k, exact=True) * 9 ** k + \
               digit * comb(n, k - 1, exact=True) * 9 ** (k - 1)
    index += 1

print(int(ans))

Submission status: Accepted

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


def combination(n,k):
    if n == 0:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return n
    elif k == 2:
        return n*(n-1)/2
    else:
        return n*(n-1)*(n-2)/6

#桁DP
# 計算量はi*k=klogN
def dp(i,k,is_small): #i桁目以降についてk個0以外の数が含まれる数の個数(is_smallはi桁目までに0~Nが確定しているかのフラグ)
    if i == L: #全ての桁が決まった時
        return 1 if k == 0 else 0
    if k == 0:
        return 1
    if is_small:
        return combination((L-i),k)*9**k
    else:
        if N[i] == '0': #先頭が0の場合は先頭0,間,一致に分割できないので別処理(is_smallがfalseなので,i桁目までは完全に一致している)
            return dp(i+1,k,False) 
        else:
            zero = dp(i+1,k,True) #先頭が0のパターン
            aida = dp(i+1,k-1,True) * (int(N[i])-1)#先頭が0以外かつnの最大桁数より小さいパターン
            icchi = dp(i+1,k-1,False) #先頭が同じパターン
            return zero + aida + icchi
        

L = len(N)
print(int(dp(0,K,False)))

Submission status: Accepted

Solution code:
N=input()
K=int(input())
m=len(N)
 
dp0=[[0]*(m+1) for _ in range(m+1)]
dp1=[[0]*(m+1) for _ in range(m+1)]
dp1[0][0]=1
for i in range(1,m+1):
    dp0[i][0]=1
    
for i in range(m):
    for j in range(m):
        if N[i]=='0':
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]
            dp1[i+1][j+1]=dp1[i][j+1]
        else:
            dp0[i+1][j+1]=dp0[i][j]*9 + dp0[i][j+1]+dp1[i][j]*(int(N[i])-1)+dp1[i][j+1]
            dp1[i+1][j+1]=dp1[i][j]
if m<K:
  print(0)
else:
  print(dp0[-1][K]+dp1[-1][K])

Submission status: Accepted

Solution code:
import sys
from io import StringIO

def resolve():
    s=input().strip()
    k=int(input().strip())

    dp = [[[0 for a in range(2)] for b in range(5)]for c in range(105)]

    #0 same 1 under
    dp[0][0][0]=1

    keta=1
    for a in s:
        for b in range(4):
            for c in range(2): #0 same 1 under
                n=int(a)
                for d in range(10):
                    if c==0 and d > n:
                        #out
                        continue

                    b2 = b
                    if d != 0:
                        b2 += 1
                    
                    c2=c
                    if c==0 and n != d:
                        c2 = 1

                    dp[keta][b2][c2]+=dp[keta-1][b][c]
        keta+=1

    ans = dp[len(s)][k][0] + dp[len(s)][k][1]

    print(ans)

    return

resolve()

Submission status: Accepted

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

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

for i in range(1,len(N)+1):
    for j in range(4):
        for k in range(2):
            if k == 0 and j != 0:
                if N[i-1] == "0":
                    dp[i][j][k] = dp[i-1][j-1][0] * 9 + dp[i-1][j][0]
                else:
                    dp[i][j][k] = dp[i-1][j-1][0] * 9 + dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j-1][1]*(int(N[i-1])-1)
            if k == 0 and j == 0:
                dp[i][j][k] = dp[i-1][j][0] + dp[i-1][j][1]

            if k == 1 and j != 0:
                if N[i-1] == "0":
                    dp[i][j][k] = dp[i-1][j][1]
                else:
                    dp[i][j][k] = dp[i-1][j-1][1]

print(dp[len(N)][K][0] + dp[len(N)][K][1])