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: Wrong Answer

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]
	# else:
	# 	for j in range(k+1):
	# 		dp1[i][j]=dp1[i-1][j-1]
	# 	dp0[i][0]=dp0[i-1][0]
	# 	for j in range(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]\
	else:
		conf=dp0
		notconf=dp1
		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(dp0[-1][-1]+dp1[-1][-1])

Submission status: Wrong Answer

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]
	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: Wrong Answer

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

#solve
def solve():
    n, k = IR(2)
    lenn = len(str(n))
    sn = str(n)
    ans = 1
    for i in range(k):
        if lenn > i and k - i > 0:
            ans += cmb(lenn - i - 1, k - i) * 9 ** (k - i)
            # print(ans)
            ans += cmb(lenn - i - 1, k - i - 1) * 9 ** (k - i - 1) * (int(sn[i]) - 1)
    print(int(ans))
    return


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

Submission status: Wrong Answer

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]
	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][-1]+dp1[-1][-1])

Submission status: Wrong Answer

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]
	else:
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(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][-1]+dp1[-1][-1])

Submission status: Wrong Answer

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]
	else:
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(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][-1]+dp1[-1][-1])

Submission status: Wrong Answer

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-1]
            dp1[i][j] = 9 * dp1[i-1][j-1] + dp1[i-1][j]
    print dp0[L-1][K]

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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-1] + dp1[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: Wrong Answer

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[0]
    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[i] > 0:
                dp0[i][j] = (digN[i] - 1) * dp1[i-1][j-1] + dp0[i-1][j-1] + dp1[i-1][j]
            else:
                dp0[i][j] = dp0[i-1][j-1] + dp1[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: Wrong Answer

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+=(len(l)-2)*9
            i=1
            while i<len(l):
                if l[i]!=0:
                    break
                i+=1
            if i<len(l):
                cnt+=(len(l)-i-1)*9
                cnt+=l[i]
        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: Wrong Answer

Solution code:
n=input()
l=[int(i) for i in n]
n=int(n)
k=int(input())

if n<100000:
    cnt=0
    for i in range(1,n+1):
        s=str(i)
        if len(s)-s.count('0')==k:
            cnt+=1
    print(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+=(len(l)-2)*9
        cnt+=l[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+=(len(l)-2)*(len(l)-3)//2*9*9
        cnt+=(l[1]-1)*(len(l)-2)*9
        cnt+=(len(l)-3)*9
        cnt+=l[2]
    print(cnt)

Submission status: Wrong Answer

Solution code:
n=input()
l=[int(i) for i in n]
n=int(n)
k=int(input())

if n<10000:
    cnt=0
    for i in range(1,n+1):
        s=str(i)
        if len(s)-s.count('0')==k:
            cnt+=1
    print(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+=(len(l)-2)*9
        cnt+=l[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+=(len(l)-2)*(len(l)-3)//2*9*9
        cnt+=(l[1]-1)*(len(l)-2)*9
        cnt+=(len(l)-3)*9
        cnt+=l[2]
    print(cnt)

Submission status: Wrong Answer

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] * 1
            else :
                dp[i][0][t] = dp[i-1][0][t] + dp[i-1][1][t] + dp[i-1][1][t-1] * 9
print(dp[-1][0][K]+dp[-1][1][K])

Submission status: Wrong Answer

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 - index
        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: Wrong Answer

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
while index < L:
    if int(M[index]):
        n = L - index - 1
        k = K - index
        digit = (int(M[index]) - 1)
        ans += comb(n, k, exact=True) * 9 ** k + \
               digit * comb(n, k - 1, exact=True) * 9 ** (k - 1)
    index += 1

print(ans + 1)

Submission status: Wrong Answer

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:
                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])

Submission status: Wrong Answer

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]

            if k == 1:
                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])

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

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

@lru_cache(None)
def rec(n, k):
    if k == 0:
        return 1
    if n < 10:
        if k == 1:
            return n
        else:
            return 0


    m,d = divmod(n,10)
    print(n, m, d)

    ret = 0
    ret += d * rec(m,k-1) # 最後の桁は1~dの数字。それより上は再帰
    ret += (9-d)*rec(m-1,k-1) # 最後の桁は(d+1)~9，N以下を守るため最後から2番目の桁から1引く
    ret += rec(m,k) # 最後の桁は0，それより上は再帰

    return ret

print(rec(N,K))

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
sN = str(N)
iN = list(map(int, sN[0:K]))
lN = len(sN)
sum = 0

if lN >= K:
  if K == 1:
      sum = iN[0] + (lN - 1) * 9
  elif K == 2:
      sum = iN[1] + (iN[0] - 1) * 9 + iN[0] * 9 * (lN - 2) + ((lN - 1) * (lN - 2) / 2) * 9 * 9
  elif K == 3:
      sum = iN[0] * iN[1] * (iN[2] + (lN - 3) * 9) + iN[0] * ((lN - 2) * (lN - 3) / 2) * 9 * 9 + ((lN - 1) * (lN - 2) * (lN - 3) / (3 * 2)) * 9 * 9 * 9

print(int(sum))

Submission status: Wrong Answer

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

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

    ans = func(N, K)

    print(ans)

def func(N, K):
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    ret += func('9'* l, K)

    # ret += (n - 1) * nCr(l-1, K - 2) * 9 ** (K - 1)
    # ret += nCr(l-1, K - 1) * 9 ** K 

    return ret
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

helper = {}


def fun(digit, remaining_non_zero, edge_case):
    if str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case) in helper.keys():
        return helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)]

    if remaining_non_zero < 0:
        return 0
    if digit == 0 and remaining_non_zero == 0:
        return 1
    if digit == 0 and remaining_non_zero >= 1:
        return 0

    if edge_case == True:
        ans = 0
        for i in range(nlist[len(nlist) - digit] + 1):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            elif i == nlist[len(nlist) - digit]:
                ans += fun(digit - 1, remaining_non_zero - 1, True)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)] = ans
        return ans
    if edge_case == False:
        ans = 0
        for i in range(10):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+ ',' + str(remaining_non_zero)+ ',' + str(edge_case)] = ans
        return ans

print(fun(len(nlist), k, True))

Submission status: Wrong Answer

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

helper = {}


def fun(digit, remaining_non_zero, edge_case):
    if str(digit)+str(remaining_non_zero)+str(edge_case) in helper.keys():
        return helper[str(digit)+str(remaining_non_zero)+str(edge_case)]

    if remaining_non_zero < 0:
        return 0
    if digit == 0 and remaining_non_zero == 0:
        return 1
    if digit == 0 and remaining_non_zero >= 1:
        return 0

    if edge_case == True:
        ans = 0
        for i in range(nlist[len(nlist) - digit] + 1):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            elif i == nlist[len(nlist) - digit]:
                ans += fun(digit - 1, remaining_non_zero - 1, True)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+str(remaining_non_zero)+str(edge_case)] = ans
        return ans
    if edge_case == False:
        ans = 0
        for i in range(10):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+str(remaining_non_zero)+str(edge_case)] = ans
        return ans

print(fun(len(nlist), k, True))

Submission status: Wrong Answer

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

helper = {}


def fun(digit, remaining_non_zero, edge_case):
    if edge_case:
        if str(digit)+str(remaining_non_zero)+'1' in helper.keys():
            return helper[str(digit)+str(remaining_non_zero)+'1']
    else:
        if str(digit)+str(remaining_non_zero)+'0' in helper.keys():
            return helper[str(digit)+str(remaining_non_zero)+'0']

    if remaining_non_zero < 0:
        return 0
    if digit == 0 and remaining_non_zero == 0:
        return 1
    if digit == 0 and remaining_non_zero >= 1:
        return 0

    if edge_case == True:
        ans = 0
        for i in range(nlist[len(nlist) - digit] + 1):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            elif i == nlist[len(nlist) - digit]:
                ans += fun(digit - 1, remaining_non_zero - 1, True)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+str(remaining_non_zero)+'1'] = ans
        return ans
    if edge_case == False:
        ans = 0
        for i in range(10):
            if i == 0:
                ans += fun(digit - 1, remaining_non_zero, False)
            else:
                ans += fun(digit - 1, remaining_non_zero - 1, False)
        helper[str(digit)+str(remaining_non_zero)+'0'] = ans
        return ans

print(fun(len(nlist), k, True))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
K=int(input())

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=max((dp[i][j]-1)*9+int(n[i+1]),0) if dp[i][j+1]==0 else dp[i][j]*9
    dp[i+1][K]+=dp[i][K]
    
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
K=int(input())

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=(dp[i][j]-1)*9+int(n[i+1]) if dp[i][j+1]==0 else dp[i][j]*9
    dp[i+1][K]+=dp[i][K]
    
print(dp[-1][-1])

Submission status: Wrong Answer

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

L = len(str(N))
N2 = list(str(N))
dp1 = [[0 for i in range(L+1)] for j in range(3+1)]
dp2 = [[0 for i in range(L+1)] for j in range(3+1)]
dp1[0]=[1]*(L+1)
temp = 0
for i in range(L-1):
    #print(temp)
    if (N2[i] != "0" and temp <= K-1):
        temp += 1
        dp2[min(temp,K)][i+1] += 1
    elif (N2[i] == "0" and dp2[min(temp,K)][i] == 1):
        dp2[min(temp,K)][i+1] += 1
#print(dp2)

dp1[1][1] = int(N2[0])-1
for i in range(1,K+1):
    for j in range(2,L+1):
        if (N2[j-1] != "0" and i == 1 ):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 2):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 3):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        else:
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]
#print(dp1)
print(dp1[K][-1]+dp2[K][-1])

Submission status: Wrong Answer

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

dp = [[[0 for a in range(k+1)] for b in range(2)] for c in range(l+5)]

dp[0][0][0] = 1
#print(dp)

for a in range(l) :
    for b in range(2) :
        for c in range(k+1) :
            for d in range(10) :
                na = a
                nb = b
                nc = c
                if b == 0 :
                    if d > int(n[a]) :
                        continue
                    if d < int(n[a]) :
                        nb = 1
                if c == k and d > 0 :
                    continue
                if d != 0 :
                    nc += 1
                #print(a,b,c,na,nb,nc)
                dp[na+1][nb][nc] += dp[a][b][c]


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

Submission status: Wrong Answer

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

L = len(str(N))
N2 = list(str(N))
dp1 = [[0 for i in range(L+1)] for j in range(3+1)]
dp2 = [[0 for i in range(L+1)] for j in range(3+1)]
dp1[0]=[1]*(L+1)
temp = 0
for i in range(L-1):
    #print(temp)
    if (N2[i] != "0" and temp <= K-1):
        temp += 1
        dp2[min(temp,K)][i+1] += 1
    elif N2[i] == "0":
        dp2[min(temp,K)][i+1] += 1

dp1[1][1] = int(N2[0])-1
for i in range(1,K+1):
    for j in range(2,L+1):
        if (N2[j-1] != "0" and i == 1 ):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 2):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 3):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        else:
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]
print(dp1[K][-1]+dp2[K][-1])

Submission status: Wrong Answer

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

L = len(str(N))
N2 = list(str(N))
dp1 = [[0 for i in range(L+1)] for j in range(3+1)]
dp2 = [[0 for i in range(L+1)] for j in range(3+1)]
dp1[0]=[1]*(L+1)
temp = 0
for i in range(L-1):
    #print(temp)
    if (N2[i] != "0" and temp <= K-1):
        temp += 1
        dp2[min(temp,K)][i+1] += 1
    elif N2[i] == "0":
        dp2[min(temp,K)][i+1] += 1
    print(dp2)

dp1[1][1] = int(N2[0])-1
for i in range(1,K+1):
    for j in range(2,L+1):
        if (N2[j-1] != "0" and i == 1 ):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 2):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 3):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        else:
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]
print(dp1)
print(dp1[K][-1]+dp2[K][-1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
K=int(input())

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=(dp[i][j]-1)*9+int(n[i+1]) if i==j-1 else dp[i][j]*9
    dp[i+1][K]+=dp[i][K]
    
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
K=int(input())

n=(str(N))
dp=[[0]*(K+1) for i in range(len(n))]
dp[0][0]=1
dp[0][1]=int(n[0])


for i in range(len(n)-1):
    dp[i+1][0]+=dp[i][0]
    dp[i+1][1]+=(dp[i][0])*9
    for j in range(1,K):
        dp[i+1][j]+=dp[i][j]
        dp[i+1][j+1]+=(dp[i][j]-1)*9+int(n[i+1]) if i==0 else dp[i][j]*9
    dp[i+1][K]+=dp[i][K]
    
print(dp[-1][-1])

Submission status: Wrong Answer

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

L = len(str(N))
N2 = list(str(N))
dp1 = [[0 for i in range(L+1)] for j in range(3+1)]
dp2 = [[0 for i in range(L+1)] for j in range(3+1)]
dp1[0]=[1]*(L+1)
temp = 0
for i in range(L):
    #print(temp)
    if (N2[i] != "0" and temp <= K-1):
        temp += 1
        dp2[min(temp,K)][i+1] += 1
    elif N2[i] == "0":
        dp2[min(temp,K)][i+1] += 1
#print(dp2)

dp1[1][1] = int(N2[0])-1
for i in range(1,K+1):
    for j in range(2,L+1):
        if (N2[j-1] != "0" and i == 1 ):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 2):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        elif (N2[j-1] != "0" and i == 3):
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]+dp2[i-1][j-1]*(int(N2[j-1])-1)+dp2[i][j-1]
        else:
            dp1[i][j] += dp1[i-1][j-1]*9+dp1[i][j-1]
#print(dp1)
print(dp1[K][-1]+dp2[K][-1])

Submission status: Wrong Answer

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

def c(n,k):
	if 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
def f(N, K):
	if N == 0:
		return 0
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit-1, K) * (9 ** K)
	a = 10**(digit-1)
	d = N // a
	ret += (d-1) * c(digit-1, K-1) * (9 ** (K-1))
	ret += f(N - d*a, K-1)

	return ret

print(f(N,K))

Submission status: Wrong Answer

Solution code:
import math
n=input()
k=int(input())
if len(n)>=3:
    x=int(n[0]+n[1]+n[2])
if len(n)>=2:
    y=int(n[0]+n[1])
z=int(n[0])

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

# k==1のもの数える
if k==1:
    print(z*len(n)+(9-z)*(len(n)-1))

elif k==2 and len(n)>=2:
    a=0
    for i in range(1,10):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            else:
                break

    v=combinations_count(len(n),2)
    if len(n)>=3:
        w=combinations_count(len(n)-1,2)
        w1=(9-int(n[1]))*(len(n)-2)
        print(a*v+(81-a)*w+w1)
    else:
        print(a*v)
        exit()

elif k==3 and len(n)>=3:
    a=0
    b=0
    c=0
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                r=int(str(i)+str(j)+str(k))
                if r<=x:
                    a+=1
                elif r>x and r<=x-int(n[2])+9:
                    b+=1
                elif r>x-int(n[2])+9 and r<(int(n[0])+1)*100:
                    c+=1


    v=combinations_count(len(n),3)
    if len(n)>=4:
        w=combinations_count(len(n)-1,3)
        w1=combinations_count(len(n)-1,2)*b
        w2 = combinations_count(len(n) - 2, 2)*c
        print(a*v+(729-a)*w+w1+w2)
    else:
        print(a*v)
        exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math
n=input()
k=int(input())
if len(n)>=3:
    x=int(n[0]+n[1]+n[2])
if len(n)>=2:
    y=int(n[0]+n[1])
z=int(n[0])

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

# k==1のもの数える
if k==1:
    print(z*len(n)+(9-z)*(len(n)-1))

elif k==2 and len(n)>=2:
    a=0
    for i in range(1,10):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            else:
                break

    v=combinations_count(len(n),2)
    if len(n)>=3:
        w=combinations_count(len(n)-1,2)
        w1=(9-int(n[1]))*(len(n)-2)
        print(a*v+(81-a)*w+w1)
    else:
        print(a*v)
        exit()

elif k==3 and len(n)>=3:
    a=0
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                if int(str(i)+str(j)+str(k))<=x:
                    a+=1

    v=combinations_count(len(n),3)
    if len(n)>=4:
        w=combinations_count(len(n)-1,3)
        if int(n[2])!=0:
            w1=combinations_count(len(n)-1,2)*(9-int(n[2]))
            w2 = combinations_count(len(n) - 2, 2) * (81 - (int(n[1]) * int(n[2])))
        else:
            w1=0
            w2 = combinations_count(len(n) - 2, 2) * (81 - (int(n[1])))
        print(a*v+(729-a)*w+w1+w2)
    else:
        print(a*v)
        exit()
else:
    print(0)