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:
s = map(int, list(raw_input()))
k = int(raw_input())
seen = {}


2
351
def dfs(i, k, s, cur, 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)

	#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], )
	if s[i] and pe:
		r += dfs(i + 1, k - 1, s, cur + [s[i]], pe)

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

Submission status: Wrong Answer

Solution code:
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2 and l >= 2:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*9*(l-1)
    # 最大桁がNのとき
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i-1) <= N:
            ans += 9
        else:
            ans += S[i]
    # 最大桁が0のとき
    if l > K:
        ans += (l-1)*(l-2)//2*9**2
elif K == 3 and l >= 3:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*(l-1)*(l-2)//2*9**2
    # 最大桁がNのとき
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 8*9 + S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                ans += (S[a]-1)*9 + S[b]
    # 最大桁が0のとき
    ans += (l-1)*(l-2)*(l-3)//6*9**3
else:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2 and l >= 2:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*9*(l-1)
    # 最大桁がNのとき
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i-1) <= N:
            ans += 9
        else:
            ans += S[i]
    # 最大桁が0のとき
    if l > K:
        ans += (l-1)*(l-2)//2*9**2
elif K == 3 and l >= 3:
    ans = 0
    # 最大桁がN未満のとき
    ans += (S[0]-1)*(l-1)*(l-2)//2*9**2
    # 最大桁がNのとき
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 9*S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                ans += S[a]*S[b]
    # 最大桁が0のとき
    ans += (l-1)*(l-2)*(l-3)//6*9**3
else:
    ans = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*9*(l-1)
    # 最大桁がNのとき
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i-1) <= N:
            ans += 9
        else:
            ans += S[i]
    # 最大桁が0のとき
    if l > K:
        ans += (l-1)*(l-2)//2*9**2
else:
    ans = 0
    # 最大桁がN未満のとき
    ans += (S[0]-1)*(l-1)*(l-2)//2*9**2
    # 最大桁がNのとき
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 9*S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                ans += S[a]*S[b]
    # 最大桁が0のとき
    ans += (l-1)*(l-2)*(l-3)//6*9**3
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*9*(l-1)
    # 最大桁がNのとき
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i) <= N:
            ans += 9
        else:
            ans += S[i]
    # 最大桁が0のとき
    if l > K:
        ans += (l-1)*(l-2)//2*9**2
else:
    ans = 0
    # 最大桁がN未満のとき
    ans += (S[0]-1)*(l-1)*(l-2)//2*9**2
    # 最大桁がNのとき
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 9*S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                ans += S[a]*S[b]
    # 最大桁が0のとき
    ans += (l-1)*(l-2)*(l-3)//6*9**3
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2:
    # 最大桁がN未満のとき
    ans = (S[0]-1)*9*(l-1)
    # 最大桁がNのとき
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i) <= N:
            ans += 9
        else:
            ans += S[i]
    # 最大桁が0のとき
    if l > K:
        ans += (l-1)*(l-2)//2*9*2
else:
    ans = 0
    # 最大桁がN未満のとき
    ans += (S[0]-1)*(l-1)*(l-2)//2*9**2
    # 最大桁がNのとき
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 9*S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                ans += S[a]*S[b]
    # 最大桁が0のとき
    ans += (l-1)*(l-2)*(l-3)//6*9**3
print(ans)

Submission status: Wrong Answer

Solution code:
s = raw_input()
k = int(raw_input())
want = int(s)
ret = dict()
for a in xrange(len(s)):
    for b in xrange(a):
        for c in xrange(b):
            for d in xrange(10):
                for e in xrange(10):
                    for f in xrange(10):
                        num = 0
                        if d:
                            num += 1
                        if e:
                            num += 1
                        if f:
                            num += 1
                        if num != k:
                            continue
                        cand = (10**a) * d
                        cand += (10**b) * e
                        cand += (10**c) * f
                        if cand and cand <= want:
                            ret[cand] = True
print len(ret)

Submission status: Wrong Answer

Solution code:
s = raw_input()
k = int(raw_input())
want = int(s)
ret = dict()
for a in xrange(len(s)):
    for b in xrange(a):
        for c in xrange(b):
            for d in xrange(10):
                for e in xrange(10):
                    for f in xrange(10):
                        num = 0
                        if d:
                            num += 1
                        if e:
                            num += 1
                        if f:
                            num += 1
                        if num > k:
                            continue
                        cand = (10**a) * d
                        cand += (10**b) * e
                        cand += (10**c) * f
                        if cand and cand <= want:
                            ret[cand] = True
print len(ret)

Submission status: Wrong Answer

Solution code:
N_string = input()
l = len(N_string)
N = int(N_string)
K = int(input())

n = int(N_string[0])
dp0 = [[n - 1, 0, 0]]
dp1 = [[1, 0, 0]]

for i in range(l - 1):
    n = int(N_string[i + 1])
    if n == 0:
        dp0.append([9 + dp0[i][0],
                    dp0[i][0] * 9 + dp0[i][1],
                    dp0[i][1] * 9 + dp0[i][2]])
        dp1.append([dp1[i][0], dp1[i][1], dp1[i][2]])
    else:
        dp0.append([9 + dp0[i][0] + dp1[i][0],
                    dp0[i][0] * 9 + dp0[i][1] + dp1[i][0] * (n - 1) + dp1[i][2],
                    dp0[i][1] * 9 + dp0[i][2] + dp1[i][1] * (n - 1) + dp1[i][2]])
        dp1.append([0, dp1[i][0], dp1[i][1]])
print(dp0[-1][K - 1] + dp1[-1][K - 1])

Submission status: Wrong Answer

Solution code:
# 約分してから計算するアルゴリズム

def combination(n, r):
    # n >= 0, r >= 0, r <= n を仮定
    if n < 0 or r < 0 or n < r:
        return 0

    # r <= n - r を仮定
    if n - r < r:
        r = n - r

    # r < 2 の場合
    if r == 0:
        return 1
    if r == 1:
        return n

    # nCr の分子
    # [n - r + 1, n - r + 2, ... , n - 1, n]
    numerator = [n - r + 1 + i for i in range(r)]


    # nCr の分母
    # [1, 2, ... , r - 1, r]
    denominator = [i + 1 for i in range(r)]

    # nCr を約分する
    for i in range(r):
        # i番目の分母で約分する
        # 0番目は1なので省略

        # 元の（今までの約分を行う前の）i番目の分母の値
        original_denominator = i + 1

        # 今までの約分を行った後の、i番目の分母の値
        # 今回の約分で割る数
        divisor = denominator[i]

        # divisorが1（全て約分済み）の場合は無視する
        if divisor == 1:
            continue

        # 約分する相手の分子を決める
        # 0～i番目の分子（約分前）の中で、
        # original_denominatorで割り切れる数
        # （一つしかない）を選ぶ
        # remainder = i番目の分子 % original_denominator
        # とするとき、
        # (i - remainder)番目の分子 = i番目の分子 - remainder
        # (i - remainder)番目の分子 % original_denominator
        #  = (i番目の分子 - remainder) % original_denominator
        #  = 0
        # なので、(i - remainder)番目の分子を選べばよい。

        # remainder = i番目の分子 % original_denominator
        #           = (n - r + i + 1) % (i + 1)
        #           = (n - r) % (i + 1)
        remainder = (n - r) % original_denominator

        # divisor で約分できるペアをすべて約分する
        for j in range(i, r, original_denominator):
            numerator[j - remainder] = numerator[j - remainder] // divisor
            denominator[j] = denominator[j] // divisor

    ans = 1
    for i in numerator:
        ans *= i
    return ans


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

if N < 10:
    if K == 1:
        print(N)
    else:
        print(0)
# elif N < 100:
#     if K == 1:
#         print(9 + N // 10)
#     elif K == 2:
#         print(9 * (N // 10 - 1) + (N - (N // 10) * 10))
#     else:
#         print(0)
else:
    # 10 ** n <= N < 10 ** (n + 1) なる n
    # すなわち、N が n + 1 桁であるような n
    n = len(N_string) - 1

    # 10 ** n 未満で条件を満たす整数の数
    ans = combination(n, K) * (9 ** K)

    # Nの先頭の数字
    a = int(N_string[0])

    if K == 1:
        ans += a
    else:
        # a以外に0でない数字が出現するかどうか
        if N_string[1:] == "0" * n:
            # 出現しないとき
            ans += (a - 1) * combination(n, K - 1) * (9 ** (K - 1))
        else:
            # 出現するとき
            # Nの2番目の0以外の数字とその表れる桁数を計算
            m = n - 1
            while True:
                if N_string[n - m] != 0:
                    b = int(N_string[n - m])
                    break
                m -= 1

            if K == 2:
                # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                # 問題の条件を満たす整数の個数
                ans += (a - 1) * combination(n, K - 1) * 9

                # n + 1 桁かつ、先頭の数字が　a　であるような、
                # 問題の条件を満たす整数でN以下のもののの個数
                ans += combination(m, 1) * 9 + b
            else:
                # K == 3
                # a, b以外に0でない数字が出現するかどうか
                if N_string[n - m + 1:] == "0" * m:
                    # 出現しないとき

                    # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (a - 1) * combination(n, 2) * 9 * 9

                    # n + 1 桁で先頭の数字が　a　かつ、 m + 1 桁目が0であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(m, 2) * 9 * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が1以上b未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (b - 1) * combination(m, 1) * 9
                else:
                    # Nの3番目の0以外の数字とその表れる桁数を計算
                    l = m - 1
                    while True:
                        if N_string[n - l] != 0:
                            c = int(N_string[n - l])
                            break
                        l -= 1

                    # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (a - 1) * combination(n, K - 1) * 9 * 9

                    # n + 1 桁で先頭の数字が　a　かつ、 m + 1 桁目が0であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(m, K - 1) * 9 * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が1以上b未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (b - 1) * combination(m, K - 2) * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が　b　であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(l, 1) * 9 + c

    print(ans)

Submission status: Wrong Answer

Solution code:
# 約分してから計算するアルゴリズム

def combination(n, r):
    # n >= 0, r >= 0, r <= n を仮定
    if n < 0 or r < 0 or n < r:
        return 0

    # r <= n - r を仮定
    if n - r < r:
        r = n - r

    # r < 2 の場合
    if r == 0:
        return 1
    if r == 1:
        return n

    # nCr の分子
    # [n - r + 1, n - r + 2, ... , n - 1, n]
    numerator = [n - r + 1 + i for i in range(r)]


    # nCr の分母
    # [1, 2, ... , r - 1, r]
    denominator = [i + 1 for i in range(r)]

    # nCr を約分する
    for i in range(r):
        # i番目の分母で約分する
        # 0番目は1なので省略

        # 元の（今までの約分を行う前の）i番目の分母の値
        original_denominator = i + 1

        # 今までの約分を行った後の、i番目の分母の値
        # 今回の約分で割る数
        divisor = denominator[i]

        # divisorが1（全て約分済み）の場合は無視する
        if divisor == 1:
            continue

        # 約分する相手の分子を決める
        # 0～i番目の分子（約分前）の中で、
        # original_denominatorで割り切れる数
        # （一つしかない）を選ぶ
        # remainder = i番目の分子 % original_denominator
        # とするとき、
        # (i - remainder)番目の分子 = i番目の分子 - remainder
        # (i - remainder)番目の分子 % original_denominator
        #  = (i番目の分子 - remainder) % original_denominator
        #  = 0
        # なので、(i - remainder)番目の分子を選べばよい。

        # remainder = i番目の分子 % original_denominator
        #           = (n - r + i + 1) % (i + 1)
        #           = (n - r) % (i + 1)
        remainder = (n - r) % original_denominator

        # divisor で約分できるペアをすべて約分する
        for j in range(i, r, original_denominator):
            numerator[j - remainder] = numerator[j - remainder] // divisor
            denominator[j] = denominator[j] // divisor

    ans = 1
    for i in numerator:
        ans *= i
    return ans


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

if N < 10:
    if K == 1:
        print(N)
    else:
        print(0)
elif N < 100:
    if K == 1:
        print(9 + N // 10)
    elif K == 2:
        print(9 * (N // 10 - 1) + (N - (N // 10) * 10))
    else:
        print(0)
else:
    # 10 ** n <= N < 10 ** (n + 1) なる n
    # すなわち、N が n + 1 桁であるような n
    n = len(N_string) - 1

    # 10 ** n 未満で条件を満たす整数の数
    ans = combination(n, K) * (9 ** K)

    # Nの先頭の数字
    a = int(N_string[0])

    if K == 1:
        ans += a
    else:
        # a以外に0でない数字が出現するかどうか
        if N_string[1:] == "0" * n:
            # 出現しないとき
            ans += (a - 1) * combination(n, 1) * 9
        else:
            # 出現するとき
            # Nの2番目の0以外の数字とその表れる桁数を計算
            m = n - 1
            while True:
                if N_string[n - m] != 0:
                    b = int(N_string[n - m])
                    break
                m -= 1

            if K == 2:
                # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                # 問題の条件を満たす整数の個数
                ans += (a - 1) * combination(n, K - 1) * 9

                # n + 1 桁かつ、先頭の数字が　a　であるような、
                # 問題の条件を満たす整数でN以下のもののの個数
                ans += combination(m, 1) * 9 + b
            else:
                # K == 3
                # a, b以外に0でない数字が出現するかどうか
                if N_string[n - m + 1:] == "0" * m:
                    # 出現しないとき
                    ans += (a - 1) * combination(n, 2) * 9 * 9
                    ans += combination(m, 2) * 9 * 9
                    ans += (b - 1) * combination(m, 1) * 9
                else:
                    # Nの3番目の0以外の数字とその表れる桁数を計算
                    l = m - 1
                    while True:
                        if N_string[n - l] != 0:
                            c = int(N_string[n - l])
                            break
                        l -= 1

                    # n + 1 桁かつ、先頭の数字が1以上a未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (a - 1) * combination(n, K - 1) * 9 * 9

                    # n + 1 桁で先頭の数字が　a　かつ、 m + 1 桁目が0であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(m, K - 1) * 9 * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が1以上b未満であるような、
                    # 問題の条件を満たす整数の個数
                    ans += (b - 1) * combination(m, K - 2) * 9

                    # n + 1 桁で先頭の数字が a かつ、
                    # m + 1 桁目の数字が　b　であるような、
                    # 問題の条件を満たす整数でN以下のもののの個数
                    ans += combination(l, 1) * 9 + c

    print(ans)

Submission status: Wrong Answer

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

if n < 1000:
    result = 0
    for i in range(n + 1):
        if len(str(i)) - str(i).count("0") == k:
            result += 1
    print(result)
    sys.exit(0)

keta = len(str(n))
firstdigit = int(str(n)[0])


def sigma(n):
    result = 0
    for i in range(1, n + 1):
        result += i
    return result

result = 0
if k == 3:
    # 3桁の任意の数字に0を足していくパターン
    basetype3 = 9 ** 3
elif k == 2:
    # 2桁の任意の数字に0を足していくパターン
    basetype = 9 ** 2
    result += basetype * sigma(keta - 2)
    # 一番高い桁の値が一つ低い値の場合は同様に自由に0を足せる
    result += (firstdigit - 1) * 9 * sigma(keta - 2)
elif k == 1:
    # 1桁の任意の数字に0を足していくパターン
    basetype = 9
    result += basetype * (keta - 1)
    result += firstdigit  # n == 301のような場合には100と200と300
print(result)

Submission status: Wrong Answer

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

if n < 1000:
    result = 0
    for i in range(n + 1):
        if len(str(i)) - str(i).count("0") == k:
            result += 1
    print(result)
    sys.exit(0)

keta = len(str(n))
firstdigit = int(str(n)[0])


def sigma(n):
    result = 0
    for i in range(1, n + 1):
        result += i
    return result

result = 0
print(keta)
if k == 3:
    # 3桁の任意の数字に0を足していくパターン
    basetype3 = 9 ** 3
elif k == 2:
    # 2桁の任意の数字に0を足していくパターン
    basetype = 9 ** 2
    result += basetype * sigma(keta - 2)
    # 一番高い桁の値が一つ低い値の場合は同様に自由に0を足せる
    result += (firstdigit - 1) * 9 * sigma(keta - 2)
elif k == 1:
    # 1桁の任意の数字に0を足していくパターン
    basetype = 9
    result += basetype * (keta - 1)
    result += firstdigit  # n == 301のような場合には100と200と300
print(result)

Submission status: Wrong Answer

Solution code:
def nCk(n,k):
    res = 1
    for i in range(k,0,-1):
        res = res*(n+1-i)/i
    return int(res)

N = input()
K = int(input())
ans = 0
dp_mikakutei = [[0 for i in range(0,K+1,1)] for j in range(0,len(N),1)]#Nより小さいかまだわからん
dp_kakutei = [[0 for i in range(0,K+1,1)] for j in range(0,len(N),1)]

dp_mikakutei[0][1]=1#その桁がまさにNのその桁と同じ
dp_kakutei[0][0]=1
dp_kakutei[0][1]=int(N[0])-1#1~N[0]-1

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

Submission status: Wrong Answer

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

# K = 1の時の組み合わせを求める関数
def func_1(N):
    Nm = int(N[0])
    return Nm + 9 * (len(N) - 1)

# K = 2の時の組み合わせを求める関数
def func_2(N):
    #NはStringなので
    #print(N[0])

    Nm = int(N[0])
    m = len(N)
    if m == 1:
        print("0")
    #print((Nm-1)*(m-1)*9)
    #print((m - 1) * (m - 2) * 9 * 9 / 2)
    x = int(N) - Nm * pow(10, m-1)
    #print(x)
    #print(1)
    #print(func_1(str(x)))


    return  int((Nm-1)*(m-1)*9+(m-1)*(m-2)*9*9/2+func_1(str(x)))

def func_3(N):
    print("OK")
    Nm = int(N[0])
    m = len(N)
    if m == 1 or m == 2:
        print("0")
    return int(pow(9,3)*(m-1)*(m-2)*(m-3)/6+(Nm-1)*(m-1)*(m-2)*9*9/2+func_2(str(int(N)-Nm*(10**(m-1)))))



if K == 1:
    print(func_1(N))
elif K == 2:
    print(func_2(N))
elif K == 3:
    print(func_3(N))

Submission status: Wrong Answer

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

if K == 1:
    Nm = int(N[0])
    print(Nm+9*(len(N)-1))
elif K == 2 :
    #print("no")
    m = len(N)
    if m == 1:
        print("0")
    else:
        Nm = int(N[0])
        Nm_1 = int(N[1])
        print(int((Nm-1)*(m-1)*9+9*9*(m-1)*(m-2)/2+Nm_1+9*(m-2)))
elif K == 3 :
    m = len(N)
    if m == 1 or m == 2:
        print("0")
    else:
        Nm = int(N[0])
        Nm_1 = int(N[1])
        Nm_2 = int(N[2])

        print(int(((Nm-1)*(m-1)*(m-2)*9*9/2)+((m-1)*(m-2)*(m-3)*9*9*9/6)+((Nm_1-1)*(m-2)*9+9*9*(m-2)*(m-3)/2+Nm_2+9*(m-3))))

Submission status: Wrong Answer

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

if K == 1:
    Nm = int(N[0])
    print(Nm+9*(len(N)-1))
else :
    print("no")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7
    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    if ln < k:
        print(0)
        exit()
    res = 0
    if k == 1:
        if ln >= 2:
            res += ncr(ln-1, 1, mod) * 9
        res += int(n[0])
    if k == 2:
        if ln >= 3:
            res += ncr(ln-1, 2, mod) * (9**k)
        res += ncr(ln-1, 1, mod) * 9 * (int(n[0])-1)
        for i in range(1, ln):
            if n[i] != '0':
                if i == ln-1:
                    res += int(n[i])
                else:
                    res += ncr(ln-i-1, 1, mod) * 9
                    res += int(n[i])
                break
    if k == 3:
        if ln >= 4:
            res += ncr(ln-1, 3, mod) * (9**k)
        res += ncr(ln-1, 2, mod) * 81 * (int(n[0])-1)
        for i in range(1, ln-1):
            if n[i] != '0':
                res += ncr(ln-i-1, 2, mod) * 81
                res += ncr(ln-i-1, 1, mod) * 9 * (int(n[i])-1)
                for j in range(i+1, ln):
                    if n[j] != '0':
                        if j != ln-1:
                            res += ncr(ln-j-1, 1, mod) * 9 
                        res += int(n[j])
                        break
                break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7
    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    if ln < k:
        print(0)
    res = 0
    if k == 1:
        if ln >= 2:
            res += ncr(ln-1, 1, mod) * 9
        res += int(n[0])
    if k == 2:
        if ln >= 3:
            res += ncr(ln-1, 2, mod) * (9**k)
        res += ncr(ln-1, 1, mod) * 9 * (int(n[0])-1)
        for i in range(1, ln):
            if n[i] != '0':
                if i == ln-1:
                    res += int(n[i])
                else:
                    res += ncr(ln-i-1, 1, mod) * 9
                    res += int(n[i])
                break
    if k == 3:
        if ln >= 4:
            res += ncr(ln-1, 3, mod) * (9**k)
        res += ncr(ln-1, 2, mod) * 81 * (int(n[0])-1)
        for i in range(1, ln-1):
            if n[i] != '0':
                res += ncr(ln-i-1, 2, mod) * 81
                res += ncr(ln-i-1, 1, mod) * 9 * (int(n[i])-1)
                for j in range(i+1, ln):
                    if n[j] != '0':
                        if j != ln-1:
                            res += ncr(ln-j-1, 1, mod) * 9 
                        res += int(n[j])
                        break
                break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7
    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    res = 0
    if k == 1:
        if ln >= 2:
            res += ncr(ln-1, 1, mod) * 9
        res += int(n[0])
    if k == 2:
        if ln >= 3:
            res += ncr(ln-1, 2, mod) * (9**k)
        res += ncr(ln-1, 1, mod) * 9 * (int(n[0])-1)
        for i in range(1, ln):
            if n[i] != '0':
                if i == ln-1:
                    res += int(n[i])
                else:
                    res += ncr(ln-i-1, 1, mod) * 9
                    res += int(n[i])
                break
    if k == 3:
        if ln >= 4:
            res += ncr(ln-1, 3, mod) * (9**k)
        res += ncr(ln-1, 2, mod) * 81 * (int(n[0])-1)
        for i in range(1, ln-1):
            if n[i] != '0':
                res += ncr(ln-i-1, 2, mod) * 81
                res += ncr(ln-i-1, 1, mod) * 9 * (int(n[i])-1)
                for j in range(i+1, ln):
                    if n[j] != '0':
                        if j != ln-1:
                            res += ncr(ln-j-1, 1, mod) * 9 
                        res += int(n[j])
                        break
                break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7
    def ncr(n, r, mod):
        r = min(r, n-r)
        numer = denom = 1
        for i in range(1, r+1):
            numer = numer * (n+1-i) % mod
            denom = denom * i % mod
        return numer * pow(denom, mod-2, mod) % mod

    n = input().rstrip()
    k = int(input())
    ln = len(n)
    res = 0
    if k == 1:
        res += ncr(ln-1, k, mod) * 9
        res += int(n[0])
    if k == 2:
        if ln >= 3:
            res += ncr(ln-1, 2, mod) * (9**k)
        res += ncr(ln-1, 1, mod) * 9 * (int(n[0])-1)
        for i in range(1, ln):
            if n[i] != '0':
                if i == ln-1:
                    res += int(n[i])
                else:
                    res += ncr(ln-i-1, 1, mod) * 9
                    res += int(n[i])
                break
    if k == 3:
        if ln >= 4:
            res += ncr(ln-1, 3, mod) * (9**k)
        res += ncr(ln-1, 2, mod) * 81 * (int(n[0])-1)
        for i in range(1, ln-1):
            if n[i] != '0':
                res += ncr(ln-i-1, 2, mod) * 81
                res += ncr(ln-i-1, 1, mod) * 9 * (int(n[i])-1)
                for j in range(i+1, ln):
                    if n[j] != '0':
                        if j != ln-1:
                            res += ncr(ln-j-1, 1, mod) * 9 
                        res += int(n[j])
                        break
                break
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [[0,0,0] for _ in range(len(n)+1)]
counter = 0

for i in range(len(n)):
    dp[i][0] += dp[i-1][0] + 9*(counter > 0)
    dp[i][1] += dp[i-1][0]*9 + dp[i-1][1]
    dp[i][2] += dp[i-1][1]*9 + dp[i-1][2]
    if n[i] > 0:
        counter += 1
        if counter <= 3:
            dp[i][counter-1] += n[i]-1
            if counter >= 2:
                dp[i][counter-2] += 1

print(dp[len(n)-1][k-1]+(counter==k))

Submission status: Wrong Answer

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

dp = [[0,0,0] for _ in range(len(n)+1)]
counter = 0
dp[0][0] = n[0]-1
for i in range(1, len(n)):
    dp[i][0] += dp[i-1][0] + 9
    dp[i][1] += dp[i-1][0]*9 + dp[i-1][1]
    dp[i][2] += dp[i-1][1]*9 + dp[i-1][2]
    counter += min([1, n[i]])
    if counter < k and n[i] != 0:
        dp[i][counter] += n[i]-1
    if 0<counter and counter < k and n[i] != 0:
        dp[i][counter-1] += 1

print(dp[len(n)-1][k-1]+(counter==k-1)+(len(n)>=4))

Submission status: Wrong Answer

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

dp = [[0,0,0] for _ in range(len(n)+1)]
counter = 0
dp[0][0] = n[0]-1
for i in range(1, len(n)):
    dp[i][0] += dp[i-1][0] + 9
    dp[i][1] += dp[i-1][0]*9 + dp[i-1][1]
    dp[i][2] += dp[i-1][1]*9 + dp[i-1][2]
    counter += min([1, n[i]])
    if counter < k and n[i] != 0:
        dp[i][counter] += n[i]-1
    if 0<counter and counter < k and n[i] != 0:
        dp[i][counter-1] += 1


print(dp[len(n)-1][k-1]+(counter==k-1))