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:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    list_N = list(map(int,list(input())))
    len_N = len(list_N)
    list_N = [0] + list_N

    K = II()
    dp0 = []
    dp1 = []
    for i in range(len_N+1):
        dp0.append([0]*(K+1))
        dp1.append([0]*(K+1))
    for i in range(1,len_N+1):
        dp0[i][0] = 1
    dp0[1][1] = max(list_N[1]-1,0)
    dp1[1][1] = 1
    for i in range(2,len_N+1):
        dp1[i][0] = dp1[i-1][0]
        for j in range(1,K+1):
            dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j] + dp1[i-1][j-1] * (list_N[i]-1) + dp1[i-1][j]
            dp1[i][j] = dp1[i-1][j-1]
    print(dp0[len_N][K]+dp1[len_N][K])
    dbg(dp0[len_N][K],dp1[len_N][K])






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    list_N = list(map(int,list(input())))
    len_N = len(list_N)
    list_N = [0] + list_N
    dbg(list_N)
    K = II()
    dp0 = []
    dp1 = []
    for i in range(len_N+1):
        dp0.append([0]*(K+1))
        dp1.append([0]*(K+1))
    for i in range(1,len_N+1):
        dp0[i][0] = 1
    dp0[1][1] = max(list_N[1]-1,0)
    dp1[1][1] = 1
    for i in range(2,len_N+1):
        for j in range(1,K+1):
            dp0[i][j] = dp0[i-1][j-1] * 9 + dp0[i-1][j]
            dp1[i][j] = dp1[i-1][j-1] * list_N[i] + dp1[i-1][j]
    print(dp0[len_N][K]+dp1[len_N][K])
    dbg(dp0[len_N][K],dp1[len_N][K])






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

S = input()
K = int(input())

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(101)]

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

def rec(i, k, is_same):
    if dp[i][k][is_same] != 0:
        return dp[i][k][is_same]
    if k == 0:
        return 1
    if i == 0:
        if k >= 2:
            return 0
        if is_same == 1:
            dp[i][k][is_same] = int(S[len(S) - i - 1])
        else:
            dp[i][k][is_same] = 9
        return dp[i][k][is_same]

    res = 0
    a = int(S[len(S) - i - 1])
    if is_same == 1:
        for x in range(a + 1):
            if x == 0:
                res += rec(i - 1, k, 0)
            elif x == a:
                res += rec(i - 1, k - 1, 1)
            else:
                res += rec(i - 1, k - 1, 0)
    else:
        for x in range(10):
            if x == 0:
                res += rec(i - 1, k, 0)
            else:
                res += rec(i - 1, k - 1, 0)

    dp[i][k][is_same] = res
    return res

n = len(S)
res = rec(n - 1, K, 1)
print(res)

Submission status: Wrong Answer

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

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

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

cnt = len(N) - N.count("0")
print(dp[-1][-1][-1] + int(cnt <= K))

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read


def main():
    N, K = map(int, read().split())

    dp1 = [0] * (K + 1)
    dp2 = [0] * (K + 1)
    dp1[0] = 1

    for x in map(int, str(N)):
        dp1, dp1_prev = [0] * (K + 1), dp1
        dp2, dp2_prev = [0] * (K + 1), dp2
        for j in range(K, -1, -1):
            dp2[j] += dp2_prev[j]
            if j > 0:
                dp2[j] = dp2_prev[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1_prev[j - 1] * (x - 1)
            if x != 0:
                dp2[j] += dp1_prev[j]
                
            if x != 0:
                if j > 0:
                    dp1[j] = dp1_prev[j - 1]
            else:
                dp1[j] = dp1_prev[j]

    print(dp1[K] + dp2[K])
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp =[[[ 0 for _ in range(2)] for _ in range(5)] for _ in range(len(N)+1)]
# dp[i][j][flg] i+1桁目までで0以外の個数がj個
# flg = 1 -> N 以下が確定している

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

for i in range(1,L):
  for j in range(3):
    b = i-1 # hitotumae
    now = int(N[i])
    ## N上限に張り付いてる方
    if now == 0:
      dp[i][j][0] += dp[b][j][0]
    else:
      dp[i][j][1] += dp[b][j][0]
      dp[i][j+1][1] += dp[b][j][0] * (now-1)
      dp[i][j+1][0] += dp[b][j][0]
    ## 張り付いてない方
    dp[i][j][1] += dp[b][j][1]
    dp[i][j+1][1] += dp[b][j][1] * 9
  dp[i][1][1] += 9 # i桁目から始まった物（それより上がZEROのもの。）

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

Submission status: Wrong Answer

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

import sys

size = len(N)

if K == 1:
    ans = (size - 1) * 9
    first = int(N[0])
    ans += first
elif K == 2:
    ans = 0
    if size == 1:
        ans = 0
    else:
        for i in range(2, size):
            ans += (i - 1) * 81
        first = int(N[0])
        ans += (first - 1) * (size - 1) * 9
        for i in range(1, size):
            nonzero = 0
            if N[i] != "0":
                nonzero = i
                break
        if nonzero == 0:
            print(ans)
            sys.exit()
        ans += int(N[nonzero])
        ans += (size - nonzero - 1) * 9
else:
    if size < 3:
        ans = 0
    else:
        ans = 0
        for i in range(2, size):
            ans += i * (i - 1) // 2 * 81
        for i in range(size):
            ans += (int(N[i]) - 1) * (size - i - 1) * (size - i -2) // 2 * 81

print(ans)

Submission status: Wrong Answer

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


def func(num,counter):
    remain = num%10
    quotient = num//10
    print(num,counter)
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

Submission status: Wrong Answer

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

dp = [[[0] * 2 for _ in range(4)] for _ in range(101)]

dp[0][0][0]=1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])

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

                if d != 0 :nj+=1
                if nj > K:continue
                if k==0:
                    if d > nd:continue
                    if d < nd:nk =1
                dp[ni][nj][nk] += dp[i][j][k]
                print(d,k)
                print(i,j,k,dp[i][j][k])
                print(ni,nj,nk,dp[ni][nj][nk])
                [print(i) for i in dp]

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

Submission status: Wrong Answer

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

if n<10:
    if k==0:
        print(1)
    elif k==1:
        print(n)
    else:
        print(0)
    exit()

#10
#0の数は高々3つまでなので、jは0,1,2,3の配列だけ持てば良い
#i桁目までは高々100
#
#dp[i][j][smaller]=

lenn=len(str(n))

dp=[[[0]*2 for _ in range(4)]  for _ in range(lenn)]
#smallerは、0：:通常、1:未満の2パターン

if int(str(n)[0])==1:
    dp[0][0][0]=1
    dp[0][1][1]=1
else:
    dp[0][0][0]=1
    dp[0][1][0]=int(str(n)[0])-1
    dp[0][1][1]=1

#print(dp)

for i in range(lenn-1):
    dp[i+1][0][0]+=dp[i][0][0]
    dp[i+1][1][0]+=dp[i][0][0]*9+dp[i][1][0] #+dp[i][0][1]*max(0,(int(str(n)[i])-1))
    dp[i+1][2][0]+=dp[i][1][0]*9+dp[i][2][0] #+dp[i][1][1]*max(0,(int(str(n)[i])-1))
    dp[i+1][3][0]+=dp[i][2][0]*9+dp[i][3][0] #+dp[i][2][1]*max(0,(int(str(n)[i])-1))

    if int(str(n)[i])==0:
        dp[i+1][0][1]+=dp[i][0][1]
        dp[i+1][1][1]+=dp[i][1][1]
        dp[i+1][2][1]+=dp[i][2][1]
        dp[i+1][3][1]+=dp[i][3][1]

    elif int(str(n)[i])==1:
        dp[i+1][1][1]+=dp[i][0][1]
        dp[i+1][2][1]+=dp[i][1][1]
        dp[i+1][3][1]+=dp[i][2][1]

        dp[i+1][1][0]+=dp[i][1][1]
        dp[i+1][2][0]+=dp[i][2][1]
        dp[i+1][3][0]+=dp[i][3][1]
    else:
        dp[i+1][1][1]+=dp[i][0][1]
        dp[i+1][2][1]+=dp[i][1][1]
        dp[i+1][3][1]+=dp[i][2][1]

        dp[i+1][1][0]+=dp[i][1][1]
        dp[i+1][2][0]+=dp[i][2][1]
        dp[i+1][3][0]+=dp[i][3][1]

        dp[i+1][1][0]+=dp[i][0][1]*(int(str(n)[i+1])-1)
        dp[i+1][2][0]+=dp[i][1][1]*(int(str(n)[i+1])-1)
        dp[i+1][3][0]+=dp[i][2][1]*(int(str(n)[i+1])-1)
    #print(dp)

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

Submission status: Wrong Answer

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

if n==1:
    if k==0:
        print(1)
    elif k==1:
        print(n)
    else:
        print(0)
    exit()

#10
#0の数は高々3つまでなので、jは0,1,2,3の配列だけ持てば良い
#i桁目までは高々100
#
#dp[i][j][smaller]=

lenn=len(str(n))

dp=[[[0]*2 for _ in range(4)]  for _ in range(lenn)]
#smallerは、0：:通常、1:未満の2パターン

if int(str(n)[0])==1:
    dp[0][0][0]=1
    dp[0][1][1]=1
else:
    dp[0][0][0]=1
    dp[0][1][0]=int(str(n)[0])-1
    dp[0][1][1]=1

#print(dp)

for i in range(lenn-1):
    dp[i+1][0][0]+=dp[i][0][0]
    dp[i+1][1][0]+=dp[i][0][0]*9+dp[i][1][0] #+dp[i][0][1]*max(0,(int(str(n)[i])-1))
    dp[i+1][2][0]+=dp[i][1][0]*9+dp[i][2][0] #+dp[i][1][1]*max(0,(int(str(n)[i])-1))
    dp[i+1][3][0]+=dp[i][2][0]*9+dp[i][3][0] #+dp[i][2][1]*max(0,(int(str(n)[i])-1))

    if int(str(n)[i])==0:
        dp[i+1][0][1]+=dp[i][0][1]
        dp[i+1][1][1]+=dp[i][1][1]
        dp[i+1][2][1]+=dp[i][2][1]
        dp[i+1][3][1]+=dp[i][3][1]

    elif int(str(n)[i])==1:
        dp[i+1][1][1]+=dp[i][0][1]
        dp[i+1][2][1]+=dp[i][1][1]
        dp[i+1][3][1]+=dp[i][2][1]

        dp[i+1][1][0]+=dp[i][1][1]
        dp[i+1][2][0]+=dp[i][2][1]
        dp[i+1][3][0]+=dp[i][3][1]
    else:
        dp[i+1][1][1]+=dp[i][0][1]
        dp[i+1][2][1]+=dp[i][1][1]
        dp[i+1][3][1]+=dp[i][2][1]

        dp[i+1][1][0]+=dp[i][1][1]
        dp[i+1][2][0]+=dp[i][2][1]
        dp[i+1][3][0]+=dp[i][3][1]

        dp[i+1][1][0]+=dp[i][0][1]*(int(str(n)[i+1])-1)
        dp[i+1][2][0]+=dp[i][1][1]*(int(str(n)[i+1])-1)
        dp[i+1][3][0]+=dp[i][2][1]*(int(str(n)[i+1])-1)
    #print(dp)

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

Submission status: Wrong Answer

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

m = len(N)
ans = 1
for i in range(K):
    ans = (ans*(m-i)*9)//(K-i)
count = K
i = 0

while count and i < m:
    Num = 9-int(N[i])
    for j in range(count-1):
        Num = (Num*(m-1-i-j)*9)//(count-1-j)
    ans -= Num
    # print(Num,i,j,count)
    if int(N[i]) != 0:
        count -= 1
    i += 1

print(ans)

Submission status: Wrong Answer

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

m = len(N)
ans = 1
for i in range(K):
    ans = ans*(m-i)*9//(K-i)
count = K
i = 0

while count and i < m:
    Num = 9-int(N[i])
    for j in range(count-1):
        Num = (Num*(m-1-i-j)*9)//(count-1-j)
    ans -= Num
    # print(Num,i,j,count)
    if int(N[i]) != 0:
        count -= 1
    i += 1

print(ans)

Submission status: Wrong Answer

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

m = len(N)
ans = 1
for i in range(K):
    ans = ans*(m-i)*9//(K-i)
count = K
i = 0

while count and i < m:
    Num = 9-int(N[i])
    for j in range(count-1):
        Num *= (m-1-i-j)*9//(count-1-j)
    ans -= Num
    # print(Num,i,j,count)
    if int(N[i]) != 0:
        count -= 1
    i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = list(map(int, list(input()[:-1])))
    K = int(input())
    L = len(N)

    # dp[i][j][k]
    # i 桁目まで決めて
    # j 個の非0を使って
    # k = 0 : そこまでの桁はNと一致
    # k = 1 : そこまでの桁でN未満であることが確定
    dp = [[[0] * 2 for _ in range(K + 2)] for _ in range(L + 1)]
    dp[0][0][0] = 1

    from pprint import pprint
    for i, x in enumerate(N):
        for k in range(K + 1):
            # 桁ごと数え上げ
            if x == 0:
                # x == 0
                dp[i + 1][k][0] += dp[i][k][0]
            else:
                # x == 0
                dp[i + 1][k][1] = dp[i][k][0]
                # 0 < n < x
                dp[i + 1][k + 1][1] += dp[i][k][0] * (x - 1)
                # n == x
                dp[i + 1][k + 1][0] += dp[i][k][0]
            # N未満で次の桁に1~9を入れる
            dp[i + 1][k + 1][1] += dp[i][k][1] * 9
            # N未満で次の桁に0を入れる
            dp[i + 1][k][1] += dp[i][k][1]

    print(sum(dp[L][K]))  

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

f = len(str(n))

#f-1桁以内に収まる数

en = 1
for i in range(k):
    en *= f-1-i

de = math.factorial(k)


s = en // de * pow(9, k)


#f桁目によって絞る

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

en = 1
for i in range(k-1):
    en *= f-1-i

de = math.factorial(k-1)


s += (en // de * pow(9, k-1)) * (kami-1)


#以下上1桁は同じ数字

keta = list(range(f-1))
num = list(range(1,10))

b =  kami * pow(10, f-1)
m = 0


if k == 1:
    m = b
    if m <= n:
        s += 1
else:
    for d in itertools.product(num, repeat=k-1):
        for c in itertools.combinations(keta, k-1):
            for i in range(k-1):
                m = b + d[i] * pow(10, c[i])
            if m <= n:
                s += 1

print(s)

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

f = len(str(n))

#f-1桁以内に収まる数

en = 1
for i in range(k):
    en *= f-1-i

de = math.factorial(k)


s = en // de * pow(9, k)


#f桁目によって絞る

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

en = 1
for i in range(k-1):
    en *= f-1-i

de = math.factorial(k-1)


s += (en // de * pow(9, k-1)) * (kami-1)


#以下上1桁は同じ数字

keta = list(range(f-1))
num = list(range(1,10))

b =  kami * pow(10, f-1)
m = 0


if k == 1:
    m = b
    if m <= n:
        s += 1
else:
    for d in itertools.product(num, repeat=k-1):
        for c in itertools.combinations(keta, k-1):
            for i in range(k-1):
                m = b + d[i] * pow(10, c[i])
            if m <= n:
                s += 1

print(s)

Submission status: Wrong Answer

Solution code:
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


M = 10**9+7 # 出力の制限
N = 100 # 必要なテーブルサイズ

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 



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

l = len(n)

if k>l:
    ans = 0
else:
    dp0 = [[0]*(k+1) for _ in range(l+1)]
    dp1 = [[0]*(k+1) for _ in range(l+1)]
    dp0[0][0] = 1
    dp1[0][0] = 1
    for i in range(1,l+1):
        for j in range(k+1):
            if j>i:
                continue
            c = int(n[-i])
            dp0[i][j] = cmb(i, j, 10**9+7)*(9**j)
            if j==0:
                dp1[i][j] = 1
            else:
                dp1[i][j] = dp0[i-1][j]
                if c>=1:
                    dp1[i][j] += dp1[i-1][j-1]
                if c>=2:
                    dp1[i][j] += (c-1)*dp0[i-1][j-1]
    ans = dp1[l][k]
print(ans)

Submission status: Wrong Answer

Solution code:
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

M = 10**9+7 # 出力の制限
N = 100 # 必要なテーブルサイズ

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 



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

l = len(n)

if k>l:
    ans = 0
else:
    dp0 = [[0]*(k+1) for _ in range(l+1)]
    dp1 = [[0]*(k+1) for _ in range(l+1)]
    dp0[0][0] = 1
    dp1[0][0] = 1
    for i in range(1,l+1):
        for j in range(k+1):
            if j>i:
                continue
            c = int(n[-i])
            dp0[i][j] = cmb(i, j, 10**9+7)*(9**j)
            if j==0:
                dp1[i][j] = 1
            else:
                dp1[i][j] = dp1[i-1][j-1] + dp0[i-1][j]
                if c>=2:
                    dp1[i][j] += (c-1)*dp0[i-1][j-1]
    ans = dp1[l][k]
print(ans)

Submission status: Wrong Answer

Solution code:
n = str(input())
k = int(input())
dp = [[[0] * (k+1) for i in range(2)] for j in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    for j in range(k+1):
        if n[i] == "0":
            dp[i+1][0][j] = dp[i][0][j]
            dp[i+1][1][j] = dp[i][1][j]
            if j > 0:
                dp[i+1][1][j] += dp[i][1][j-1]*9
        else:
            dp[i+1][1][j] = dp[i][0][j] + dp[i][1][j]
            if j > 0:
                dp[i+1][0][j] = dp[i][0][j-1]
                dp[i+1][1][j] += dp[i][1][j-1] * (int(n[i])-1) + dp[i][1][j-1] * 9
  # print(dp)
print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Wrong Answer

Solution code:
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = input()
k = input()
k = int(k)
l = len(n)
n = list(map(int, n))
ans = 0
if k==1:
    ans = n[0] + 9 * (l-1)
elif k==2:
    if l>=2:
        ans = (n[1] + (n[0]-1)*9) + n[0]*(l-2)*9 + (l-1)*(l-2)//2 * 81
    else:
        ans = 0
else:
    if l<=2:
        ans = 0
    for i in range(l):
        for j in range(i+1,l):
            for kk in range(j+1,l):
                if i==0:
                    if j==1:
                        if kk==2:
                            ans += n[1] * n[2] + (n[0]-1) * 81
                        else:
                            ans += (n[1]+(n[0]-1)*9) * 9
                    else:
                        ans += n[0] * 81
                else:
                    ans += 81*9
print(ans)

Submission status: Wrong Answer

Solution code:
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = input()
k = input()
k = int(k)
l = len(n)
n = list(map(int, n))
ans = 0
if k==1:
    ans = n[0] + 9 * (l-1)
elif k==2:
    if l>=2:
        ans = (n[1] + (n[0]-1)*9) + n[0]*(l-2)*9 + (l-1)*(l-2)//2 * 81
    else:
        ans = 0
else:
    if l<=2:
        ans = 0
    for i in range(l):
        for j in range(i+1,l):
            for kk in range(j+1,l):
                if i==0:
                    if j==1:
                        if kk==2:
                            ans += n[0] * n[1] * n[2]
                        else:
                            ans += n[0] * n[1] * 9
                    else:
                        ans += n[0] * 81
                else:
                    ans += 81*9
print(ans)

Submission status: Wrong Answer

Solution code:
## ABC154E

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = input()
k = input()
k = int(k)
l = len(n)
n = list(map(int, n))
ans = 0
if k==1:
    ans = n[0] + 9 * (l-1)
elif k==2:
    if l>=2:
        ans = (n[1] + (n[0]-1)*9) + n[0]*(l-2)*9 + (l-1)*(l-2)//2 * 81
    else:
        ans = 0
else:
    for i in range(l):
        for j in range(i+1,l):
            for kk in range(j+1,l):
                num = len(set([i,j,kk]))
                if i==0:
                    if num==1:
                        ans += n[0]
                    elif num==2:
                        if kk==1:
                            ans += n[0] * n[1]
                        else:
                            ans += n[0] * 9
                    elif k>=3:
                        if j==1:
                            if kk==2:
                                ans += n[0] * n[1] * n[2]
                            else:
                                ans += n[0] * n[1] * 9
                        else:
                            ans += n[0] * 81
                else:
                    if i==j==kk:
                        ans += 9
                    elif i==j and k>=2:
                        ans += 81
                    elif j==kk and k>=2:
                        ans += 81
                    elif k>=3:
                        ans += 81*9
print(ans)

Submission status: Wrong Answer

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

table = [1, 1]
for i in range(2, 10 ** 2):
    table.append(table[i - 1] * i)

def cmb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return table[n] // table[k] // table[n - k]

ans = 0
if keta >= K:
    for i in range(keta - K):
            ans += cmb(K + i - 1, i) * pow(9, K)
if K == 1:
    if keta >= K:
        ans += int(N[0])
if K == 2:
    if keta >= K:
        ans += ((int(N[0]) - 1) * cmb(keta - 1, 1) * 9 
        + int(N[1]) + cmb(keta - 2, 1) * 9)
if K == 3:
    if keta >= K:
        ans += (
        (int(N[0]) - 1) * cmb(keta - 1, 2) * (9 ** 2) 
        + ((int(N[1]) - 1) * cmb(keta - 2, 1) * 9 if int(N[1]) >= 1 else 0)
        + (int(N[2]) if int(N[1]) >= 1 else 0)
        + (cmb(keta - 3, 1) * 9 if int(N[1]) >= 1 else 0)
        + cmb(keta - 2, 2) * (9 ** 2)
        )
print(ans)

Submission status: Wrong Answer

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

table = [1, 1]
for i in range(2, 10 ** 2):
    table.append(table[i - 1] * i)

def cmb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return table[n] // table[k] // table[n - k]

ans = 0
for i in range(keta - K):
        ans += cmb(K + i - 1, i) * pow(9, K)
if K == 1:
    if keta >= K:
        ans += int(N[0])
if K == 2:
    if keta >= K:
        ans += (int(N[0]) - 1) * cmb(keta - 1, 1) * 9 + int(N[1]) + cmb(keta - 2, 1) * 9
if K == 3:
    if keta >= K:
        ans += (
        (int(N[0]) - 1) * cmb(keta - 1, 2) * (9 ** 2) 
        + ((int(N[1]) - 1) * cmb(keta - 2, 1) * 9 if int(N[1]) >= 1 else 0)
        + (int(N[2]) if int(N[1]) >= 1 else 0)
        + (cmb(keta - 3, 1) * 9 if int(N[1]) >= 1 else 0)
        + cmb(keta - 2, 2) * (9 ** 2)
        )
print(ans)

Submission status: Wrong Answer

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

table = [1, 1]
for i in range(2, 10 ** 2):
    table.append(table[i - 1] * i)

def cmb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return table[n] // table[k] // table[n - k]

ans = 0
for i in range(keta - K):
        ans += cmb(K + i - 1, i) * pow(9, K)
if K == 1:
    if keta >= K:
        ans += int(N[0])
if K == 2:
    if keta >= K:
        ans += (int(N[0]) - 1) * cmb(keta - 1, 1) * 9 + int(N[1]) + cmb(keta - 2, 1) * 9
if K == 3:
    if keta >= K:
        ans += (
        (int(N[0]) - 1) * cmb(keta - 1, 2) * (9 ** 2) 
        + (int(N[1]) - 1) * cmb(keta - 2, 1) * 9 
        + int(N[2]) 
        + cmb(keta - 3, 1) * 9 
        + cmb(keta - 2, 2) * (9 ** 2)
        )
print(ans)

Submission status: Wrong Answer

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

table = [1, 1]
for i in range(2, 10 ** 2):
    table.append(table[i - 1] * i)

def cmb(n, k):
    if n < k:
        return 0
    return table[n] // table[k] // table[n - k]

ans = 0
for i in range(keta - K):
        ans += cmb(K + i - 1, i) * pow(9, K)
if K == 1:
    if keta >= K:
        ans += int(N[0])
if K == 2:
    if keta >= K:
        ans += (int(N[0]) - 1) * cmb(keta - 1, 1) * 9 + int(N[1]) + cmb(keta - 2, 1) * 9
if K == 3:
    if keta >= K:
        ans += ((int(N[0]) - 1) * cmb(keta - 1, 2) * (9 ** 2) 
        + (int(N[1]) - 1) * cmb(keta - 2, 1) * 9 + int(N[2]) 
        + cmb(keta - 3, 1) * 9 + cmb(keta - 2, 2) * (9 ** 2))
print(ans)

Submission status: Wrong Answer

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

table = [1, 1]
for i in range(2, 10 ** 2):
    table.append(table[i - 1] * i)

def cmb(n, k):
    return table[n] // table[k] // table[n - k]

ans = 0
for i in range(keta - K):
        ans += cmb(K + i - 1, i) * pow(9, K)
if K == 1:
    ans += int(N[0])
if K == 2:
    if keta >= K:
        ans += (int(N[0]) - 1) * cmb(keta - 1, 1) * 9 + int(N[1]) + cmb(keta - 2, 1) * 9
if K == 3:
    if keta >= K:
        ans += ((int(N[0]) - 1) * cmb(keta - 1, 2) * (9 ** 2) + (int(N[1])) * cmb(keta - 2, 1) * 9
      + cmb(keta - 2, 2) * (9 ** 2))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq

def cmb(n,r):
    c = 1
    for i in range(r):
        c *= (n-i)
    for i in range(r):
        c //= (i+1)
    return c

n = input()
k = int(input())
ln = len(n)
ans = 1

nn0 = 0
for i in range(ln):
    if int(n[i]) > 0:
        ans += cmb(ln-i-1,k-nn0)*(9**(k-nn0))
        nn0 += 1
        ans += (int(n[i])-1)*cmb(ln-i-1,k-nn0)*(9**(k-nn0))
    if nn0 == k:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    k=int(input())
    keta_n=len(str(n))
    ans=0
    left=n//10**(keta_n-1)
    if k==1:
        ans=(keta_n-1)*9+left
    elif k==2:
        for i in range(2,keta_n):
            ans+=81*(i-1)
        ans+=(left-1)*(keta_n-1)*9
        left2=n%10**(keta_n-1)
        left2_keta=len(str(left2))
        left2_num=left2//10**(left2_keta-1)
        ans+=(left2_keta-1)*9+left2_num
    elif k==3:
        for i in range(3,keta_n):
            ans+=729*(i-1)*(i-2)//2   
        ans+=(left-1)*(keta_n-1)*(keta_n-2)//2
        left2=n%10**(keta_n-1)
        left2_keta=len(str(left2))
        left2_num=left2//10**(left2_keta-1)
        ans+=(left2_keta-1)*(left2_keta-2)//2*81+(left2_keta-1)*left2_num*9
        left3=n%10**(left2_keta-1)
        left3_keta=len(str(left3))
        left3_num=left3//10**(left3_keta-1)        
        ans+=(left3_keta-1)*9+left3_num
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r<0:return 0
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

if k==1:
    syo = int(str(n)[0])
    ans = 9*(len(str(n))-1)+syo
if k==2 and len(str(n))>=2:
    fir = int(str(n)[0])
    sec = int(str(n)[1])
    ans = 9**2*cmb(len(str(n))-1,2)
    ans+=(fir-1)*9+sec
    ans += 9*cmb(len(str(n))-2,1)*fir
elif k==2 :
    ans=0

if k==3 and len(str(n))>=3:
    fir = int(str(n)[0])
    sec = int(str(n)[1])
    thi = int(str(n)[2])
    ans = 9**3*cmb(len(str(n))-1,3)
    ans += (fir-1)*81+(sec-1)*9+thi
    ans += 9*9*cmb(len(str(n))-2,2)*fir
    ans += ((fir-1)*9+sec)*9*cmb(len(str(n))-3,1)
elif k==3:
    ans=0

if ans<0:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

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

def main():
  s=input()
  k=int(input())
  n=len(s)
  def dp(i,j,smaller):
    # i桁目以降について、0以外の値を残りj個使用可能という状況を考える。i桁目までは決定している。残りn-i桁
    # このときi桁目までの部分が「等しい」か「strict に小さくなっている」かを smaller フラグによって分岐する。
    if smaller:# 残りのn-i桁の中からj桁選び好きな数字にできる。j桁以外はすべて0
      if j==0:
        return 1
      elif j==1:
        return (n-i)*9
      elif j==2:
        return ((n-i)*(n-i-1))//2*9**2
    if j==0: # i桁目以降はすべて0で決まり
      return 1
    if n-i<j: # 0でない数字をk個つかえなかったパターン。残り桁数よりも残0以外数の方が大きい
      return 0
    ret=0
    # i+1桁目が0なら0を使うしかない
    if s[i]=='0':
      ret+=dp(i+1,j,smaller)
    else:
      ret+=dp(i+1,j-1,smaller) # i+1桁目でsと同じ数字を使う
      ret+=(int(s[i])-1)*dp(i+1,j-1,True) # i+1桁目で0より大きくs未満の数字使う
      ret+=dp(i+1,j,True) # i+1桁目で0を使う。
    return ret
  print(dp(0,k,False))
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

"""
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

117879300

"""

Submission status: Wrong Answer

Solution code:
NS = input()
N = int(NS)
Nle = len(NS)
K = int(input())
ans = 0
if K > Nle:
    print(0)
    exit()

if K == 1:
    ans = (Nle-1) * 9 + int(NS[0])
elif K == 2:
    ans = Nle * (Nle-1) * 9 * 9//2 - (9 - int(NS[0])) * (Nle-1) * 9 - 1 * (9 - int(NS[1]))
else:
    ans = Nle * (Nle-1) * (Nle-2) * (9**3) // 6 - \
          (9 - int(NS[0])) * (Nle-1) * (Nle-2) * 9 * 9 // 2 -\
          1 * (9 - int(NS[1])) * (Nle-2) * 9 -\
          1 * 1 * (9 - int(NS[2]))

print(ans)

Submission status: Wrong Answer

Solution code:
s = map(int, list(raw_input()))
k = int(raw_input())
seen = {}


2
351
def dfs(i, k, s, cur, seen, pe = False):
	
	if k < 0: return 0
	if i == len(s):
		#if k == 0: print cur

		return 1 if k == 0 else 0

	if k == 0:
		#print cur + [0] * (len(s) - i )
		return 1
	if (i, pe, k) in seen:
		return seen[(i,pe,k)]
	r = 0
	q = max(0, (s[i] if pe else 10) -1)
	r+= q * dfs(i + 1, k - 1, s, cur, seen, False)

	#for num in range(1, s[i] if pe else 10):
	#	r += dfs(i + 1, k - 1, s, cur + [num])

	r += dfs(i + 1, k, s, cur + [0], seen, False )
	if s[i] and pe:
		r += dfs(i + 1, k - 1, s, cur , seen, pe)

	seen[(i,pe,k)] = r
	return r
print dfs(0, k, s, [], seen, True)