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 = 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 += n[i]>0
    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))

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 += n[i]>0
    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]+1)

Submission status: Wrong Answer

Solution code:
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (K+1) for _ in range(2)] for _ in range(n)
]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
  for k in range(K):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

Submission status: Wrong Answer

Solution code:
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (4) for _ in range(2)] for _ in range(n)
]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
  for k in range(3):
    if N[i] != 0:
      DP[i][0][k+1] = DP[i-1][0][k]
      DP[i][1][k] = DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i-1] - 1)
    else:
      DP[i][0][k] = DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

Submission status: Wrong Answer

Solution code:
def comb(n, k):
    nume, deno = 1, 1
    for i in range(k):
        deno *= n - i
        nume *= i + 1
    return deno // nume


def ans(N, K):
    if K == 0:
        return 1
    if len(N) < K or int(N) == 0:
        return 0
    ret = sum([9 ** K * comb(max(dig - 1, 1), K - 1)
               for dig in range(K, len(N))])
    ret += (int(N[0]) - 1) * 9 ** (K - 1) * comb(len(N) - 1, K - 1)
    return ret + ans(N[1:], K - 1)


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

Submission status: Wrong Answer

Solution code:
def comb(n, k):
    nume, deno = 1, 1
    for i in range(k):
        deno *= n - i
        nume *= i + 1
    return deno // nume


def ans(N, K):
    if K == 0:
        return 1
    if len(N) < K:
        return 0
    ret = sum([9 ** K * comb(max(dig - 1, 1), K - 1)
               for dig in range(K, len(N))])
    ret += (int(N[0]) - 1) * 9 ** (K - 1) * comb(len(N) - 1, K - 1)
    return ret + ans(N[1:], K - 1)


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

Submission status: Wrong Answer

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def contain_one(n):
    a = 100
    max_num = 10**a

    while 1:
        if n // max_num == 0:
            a -= 1
            max_num = 10**a
        else:
            break

    return 9*a+(n//max_num)


def contain_two(n):
    if n <=10:
        return 0

    a = 100
    max_num = 10**a

    while 1:
        if n // max_num == 0:
            a -= 1
            max_num = 10**a
        else:
            break

    cnt = 0
    #10^a位まで
    for i in range(1, a):
        cnt += 9*9*i

    #10^a位
    tmp = n // max_num
    cnt += 9*a*(tmp-1)

    #nの10^a桁より小さい数
    tmp = n % max_num
    #怪しい
    if tmp != 0:
        cnt += contain_one(tmp)

    return cnt


def contain_three(n):
    if n <=100:
        return 0

    a = 100
    max_num = 10**a

    while 1:
        if n // max_num == 0:
            a -= 1
            max_num = 10**a
        else:
            break

    cnt = 0
    #10000以上の時ここがダメ
    for i in range(2, a):
        if i == 2:
            cnt += 9**2 * 9
        else:
            #3H(a-2) = aCa-2
            cnt += 9**2 * 9 * cmb(i, i-2)
            #aH2
            #cnt += 9**2 * 9 * (i*(i+1)//2)
            # tmp = tmp * 3
            # cnt += tmp

    print(cnt)

    tmp = n // max_num
    if a == 2:
        cnt += 9**2 * (tmp-1)
    else:
        cnt += 9**2 * (tmp-1) * cmb(a, a-2)
    print(cnt)

    tmp = n % max_num
    if tmp != 0:
        cnt += contain_two(tmp)

    return cnt


if K == 1:
    print(contain_one(N))
elif K == 2:
    print(contain_two(N))
else:
    print(contain_three(N))

Submission status: Wrong Answer

Solution code:
s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    elif x == 1:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) #与えられた数字よりも一桁少ない999999999・・・までの個数
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) == 0:
    print(tasumae)
    exit()
if len(doko) == 1:
    ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + com(l-1-doko[0],2)*(9**2) + tasumae
    print(ans)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) #与えられた数字よりも一桁少ない999999999・・・までの個数
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) == 0:
    print(tasumae)
    exit()
if len(doko) == 1:
    ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + tasumae
    print(ans)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) #与えられた数字よりも一桁少ない999999999・・・までの個数
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) <= 1:
    print(tasumae)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

Submission status: Wrong Answer

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

    digits = len(n)
    if digits < k:
        print(0)
        return
    
    ans = 1
    for i in range(0,k):
        ans = ans * (digits-i)
    for i in range(1,k+1):
        ans = ans//i
    
    for i in range(k):
        ans *= 9

    minus = 0
    if k == 1:
        minus = 9 - int(n[0])
    elif k == 2:
        b = 9 - int(n[0])
        minus = b*(digits-1)*9
        minus += (9-int(n[1]))
        if n[1] == '0':
            minus += (digits-2)*9
    elif k == 3:
        b = 9 - int(n[0])
        minus += b*(digits-1)*(digits-2)*9*9//2
        minus += (9-int(n[1]))*(digits-2)*9
        if n[1] == '0':
            minus += (digits-2)*(digits-3)*9*9//2
        if n[2] == '0':
            minus += (digits-3)*(digits-4)*9*9//2
        else:
            minus += (9-int(n[2]))


    print(ans-minus)


main()

Submission status: Wrong Answer

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

    digits = len(n)
    if digits < k:
        print(0)
        return
    
    ans = 1
    for i in range(0,k):
        ans = ans * (digits-i)
    for i in range(1,k+1):
        ans = ans//i
    
    for i in range(k):
        ans *= 9

    minus = 0
    if k == 1:
        minus = 9 - int(n[0])
    elif k == 2:
        b = 9 - int(n[0])
        minus = b*(digits-1)*9+(9-int(n[1]))
    elif k == 3:
        b = 9 - int(n[0])
        minus += b*(digits-1)*(digits-2)*9*9//2
        minus += (9-int(n[1]))*(digits-2)*9
        minus += (9-int(n[2]))

    print(ans-minus)


main()

Submission status: Wrong Answer

Solution code:
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))

def answer(n,k):
    ans = 0
    # nが空の時
    if n=='':
        return 0
    # 先頭が0の時
    if n[0]=='0':
        ans += answer(n[1:],k)
    else:
        # 先頭以外でk個使う
        if len(n) > k:
            ans += combination(len(n)-1,k) * 9**k
        # 先頭でNの先頭より小さい数を1つ使う
        if len(n)>k-1:
            ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
        # 先頭でNの先頭と同じ数を使う
        if k>1:
            ans += answer(n[1:],k-1)
        else:
            ans += int(n[0])
    return ans

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

print(answer(n,k) if len(n)>=k else 0)

Submission status: Wrong Answer

Solution code:
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))


def answer(n,k):
    ans = 0
    if k>1:
        # 先頭が0の時
        if n=='':
            return 0
        if n[0]=='0':
            ans += answer(n[1:],k)
        else:
            # 先頭以外で3つ使う
            if len(n)>k:
                ans += combination(len(n)-1,k)*9**k
            # 先頭で一つ使うが、先頭はNの先頭より小さい
            if len(n)>k-1:
                ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
            # 先頭で、Nの先頭と同じ数を使う
            ans += answer(n[1:],k-1)
    else:
        if n=='':
            return 0
        if len(n)>1:
            ans += combination(len(n)-1,1)*9
        ans += int(n[0])
    return ans

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

print(answer(n,k) if len(n)>=k else 0)

Submission status: Wrong Answer

Solution code:
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))


def answer(n,k):
    ans = 0
    if k>1:
        # 先頭以外で3つ使う
        if len(n)>k:
            ans += combination(len(n)-1,k)*9**k
        # 先頭で一つ使うが、先頭はNの先頭より小さい
        if len(n)>k-1:
            ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
        # 先頭で、Nの先頭と同じ数を使う
        ans += answer(n[1:],k-1)
    else:
        if len(n)>1:
            ans += combination(len(n)-1,1)*9
        ans += int(n[0])
    return ans

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

print(max(0,answer(n,k)) if len(n)>=k else 0)

Submission status: Wrong Answer

Solution code:
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))


def answer(n,k):
    ans = 0
    if k>1:
        if len(n)>k:
            ans += combination(len(n)-1,k)*9**k
        if len(n)>k-1:
            ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
        ans += answer(n[1:],k-1)
    else:
        if len(n)>1:
            ans += combination(len(n)-1,1)*9
        ans += int(n[0])
    return ans

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

print(answer(n,k) if len(n)>=k else 0)

Submission status: Wrong Answer

Solution code:
from math import factorial
def combination(n, r):
    return factorial(n)//(factorial(n-r) * factorial(r))


def answer(n,k):
    ans = 0
    if k>1:
        if len(n)>k:
            ans += combination(len(n)-1,k)*9**k
        if len(n)>k-1:
            ans += (int(n[0])-1)*combination(len(n)-1,k-1)*9**(k-1)
        ans += answer(n[1:],k-1)
    else:
        if len(n)-1>1:
            ans += combination(len(n)-1,1)*9
        ans += int(n[0])
    return ans

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

print(answer(n,k) if len(n)>=k else 0)

Submission status: Wrong Answer

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

d = len(N)

if d < K:
    print(0)
    exit()

def f(j,k):#j桁で0でない桁がk桁ある自然数の個数(最高位0を許す)
    if j < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return 9*j
    elif k == 2:
        return 81*j*(j-1)//2
    elif k == 3:
        return 729*j*(j-1)*(j-2)//6

b = 0
ans = 0

for i in range(d):
    if b == K:
        break
    else:
        if N[i] != 0:
            ans += f(d-(i+1),K-b) + (int(N[i])-1)*f(d-(i+1),K-b-1)
            b += 1
        else:
            continue

print(ans+1)

Submission status: Wrong Answer

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

d = len(N)

def f(j,k):#j桁で0でない桁がk桁ある自然数の個数(最高位0を許す)
    if j < k:
        return 0
    elif k == 0:
        return 1
    elif k == 1:
        return 9*j
    elif k == 2:
        return 81*j*(j-1)//2
    elif k == 3:
        return 729*j*(j-1)*(j-2)//6

b = 0
ans = 0

for i in range(d):
    if b == K:
        break
    else:
        if N[i] != 0:
            ans += f(d-(i+1),K-b) + (int(N[i])-1)*f(d-(i+1),K-b-1)
            b += 1
        else:
            continue

print(ans+1)

Submission status: Wrong Answer

Solution code:
def main():
    n = input()
    digit = len(n)
    
    k = int(input())
    dp0 = [[0]*k for _ in range(digit)]
    dp0[0][0] = int(n[0])-1
    
    dp1 = [[0]*k for _ in range(digit)]
    dp1[0][0] = 1
    
    c = 1
    flag1 = True
    flag2 = True
    flag3 = False
    flag4 = False
    flag5 = True
    for i in range(1, digit):
        if n[i] != "0":
            c += 1
        for j in range(k):
            if j > i or j > k:
                continue
            if j == 0:
                dp0[i][j] = 9+dp0[i-1][j]
                if c == 1:
                    dp1[i][j] = 1
                else:
                    if flag1:
                        dp0[i][j] += 1
                        flag1 = False
            if j == 1:
                dp0[i][j] = dp0[i-1][j-1]*9+dp0[i-1][j]
                if flag3:
                    dp0[i][j] += dp1[i-1][j-1]*9
                else:
                    dp0[i][j] += dp1[i-1][j-1]*max([(int(n[i])-1), 0])
                    if c >= 2:
                        flag3 = True
                
                if c == 2:
                    dp1[i][j] = 1
                if flag2 and ((c == 3 and n[i] != "0") or (c == 2 and n[i] == "0")):
                    dp0[i][j] += 1
                    flag2 = False
                
            if j == 2:
                dp0[i][j] = dp0[i-1][j-1]*9+dp0[i-1][j]
                
                if flag4:
                    dp0[i][j] += dp1[i-1][j-1]*9
                else:
                    dp0[i][j] += dp1[i-1][j-1]*max([(int(n[i])-1), 0])
                    if c >= 3:
                        flag4 = True

                if c == 3:
                    dp1[i][j] = 1
                if flag5 and ((c == 4 and n[i] != "0") or (c == 3 and n[i] == "0")):
                    dp0[i][j] += 1
                    flag5 = False

    print(dp0[digit-1][k-1]+dp1[digit-1][k-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
	print(int(n))  
else:
  print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Wrong Answer

Solution code:
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
	print(dp[-1][0][-1] + dp[-1][1][-1])  
else:
  print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Wrong Answer

Solution code:
n = int (input ())
k = int (input ())
if k == 1:
	ans = 0
	i = 0
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += (r - l) // pow (10, i) + 1
		i += 1
	print (ans)
elif k == 2:
	ans = 0
	i = 1
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * i 
		tmp = (r - l) // pow (10, i - 1)
		a = tmp % 10
		ans -= (9 - a) 
		i += 1
	print (ans)
else:
	ans = 0
	i = 2
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * 9 * i * (i - 1) // 2
		tmp = (r - l) // pow (10, i - 2)
		a = tmp % 100 // 10
		b = tmp % 10 
		ans -= (9 - a) * 9 + (9 - b)
		i += 1
		# print (l, r, ans)
	print (max (0, ans))

Submission status: Wrong Answer

Solution code:
n = int (input ())
k = int (input ())
if k == 1:
	ans = 0
	i = 0
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += (r - l) // pow (10, i) + 1
		i += 1
	print (ans)
elif k == 2:
	ans = 0
	i = 1
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * i 
		tmp = (r - l) // pow (10, i - 1)
		a = tmp % 10
		ans -= (9 - a) 
		i += 1
	print (ans)
else:
	ans = 0
	i = 2
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * 9 * i * (i - 1) // 2
		tmp = (r - l) // pow (10, i - 2)
		a = tmp % 100 // 10
		b = tmp % 10 
		ans -= (9 - a) * 9 + (9 - b)
		i += 1
		# print (l, r, ans)
	print (ans)

Submission status: Wrong Answer

Solution code:
n = int (input ())
k = int (input ())
if k == 1:
	ans = 0
	i = 0
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += (r - l) // pow (10, i) + 1
		i += 1
	print (ans)
elif k == 2:
	ans = 0
	i = 1
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * i 
		tmp = (r - l) // pow (10, i - 1)
		a = tmp % 10
		ans -= (9 - a) 
		i += 1
	print (ans)
else:
	ans = 0
	i = 2
	while (pow (10, i) <= n):
		l = pow (10, i)
		r = min (10 * l - 1, n)
		ans += ((r - l) // pow (10, i) + 1) * 9 * 9 * i * (i - 1) // 2
		tmp = (r - l) // pow (10, i - 2)
		a = tmp % 100
		ans -= (99 - a)
		i += 1
		# print (l, r, ans)
	print (ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def search(d, cnt, isEq):
    if d == len(N):
        return 1 if cnt == K else 0

    n = int(N[d])

    if isEq and n == '0':
        return search(d + 1, cnt, isEq)

    if isEq:
        ret = 0
        ret += search(d + 1, cnt, False)
        for _ in range(1, n):
            ret += search(d + 1, cnt + 1, False)
        ret += search(d + 1, cnt + 1, True)
        return ret

    return search(d + 1, cnt, False) + search(d + 1, cnt + 1, False) * 9

print(search(0, 0, True))

Submission status: Wrong Answer

Solution code:
##i==0,k==0の場合分けが死ぬ

def f(i,k):#i桁目がnum未満
    if i == 0:
        return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 0
        else: return 1
    if num==0:
        return ncr(i-1,k)*9**k
    return (num-1)* ncr(i-1,k-1)*9**(k-1)+ncr(i-1,k)*9**k


def g(i,k):#i桁目がnum
    if i == 0:
        if k==0:return 1
        else:return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 1
        else:return 0

    if num==0:
        return f(i-1,k) +g(i-1,k)
    else:
        return f(i-1,k-1) + g(i-1,k-1)



def ncr(n,r):##　n>>r の場合のncr　O(r) r>nなら0
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
    return x//y

s = input()
k = int(input())
l= len(s)
print(f(l,k)+g(l,k))

Submission status: Wrong Answer

Solution code:
##toketenaiiiiiiii!!!!!

def f(i,k):#i桁目がnum未満
    if i == 0:
        return 0
    num = int(s[-i])
    if k == 0: return 1
    if num==0:
        return ncr(i-1,k)*9**k
    return (num-1)* ncr(i-1,k-1)*9**(k-1)+ncr(i-1,k)*9**k


def g(i,k):#i桁目がnum
    if i == 0:
        if k==0:return 1
        else:return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 1
        else:return 0

    if num==0:
        return f(i-1,k) +g(i-1,k)
    else:
        return f(i-1,k-1) + g(i-1,k-1)



def ncr(n,r):##　n>>r の場合のncr　O(r) r>nなら0
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
    return x//y

s = input()
k = int(input())
l= len(s)
print(f(l,k)+g(l,k))

Submission status: Wrong Answer

Solution code:
def rec(i,k,f):#i桁で0以外がkこあるやつを返す  f ==0:i桁めがnum　f==1:num未満
    if i==0 :
        return 0  #長さ0なのは存在しない
    num = int(s[-i])
    if f==1 :
        if k==0:
            return 0 ##k
        else:
            return max(0,num-1)* ncr(i-1,k-1)*9**(k-1)+ncr(i-1,k)*9**k
        #先頭0とそれ以外 * k or k-1個の選び方*1~9

    else:
        if k == 0:
            return 1 ##k==0なら全部0 k<0にしない
        return rec(i-1,k-1,0) + rec(i-1,k-1,1)


def ncr(n,r):##　n>>r の場合のncr　O(r) r>nなら0
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
    return x//y

s = input()
k = int(input())
l= len(s)
print(rec(l,k,0) + rec(l,k,1))

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**3):
        fact.append(fact[-1]*i % mod)

    def inv_n(n):
        return pow(n, mod-2, mod)

    def nCr(n, r, mod=10**9+7):
        return inv_n(fact[n-r]*fact[r] % mod)*fact[n] % mod

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

    ans = 0
    m = len(n)
    if len(n) < 5:
        n = int(n)
        for i in range(1, n+1):
            i = str(i)
            if len(i)-i.count("0") == k:
                ans += 1
        print(ans)
        return
    for i in range(k):
        ans += nCr(m-i-1, k-i)*pow(9, k-i)
        ans += (int(n[i])-1)*nCr(m-i-1, k-i-1)*pow(9, k-i-1)

    print(ans+1)


main()

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
#桁の数字を取得
dig=[]
n=N
while n>0:
  dig.append(n%10)
  n//=10
a=dig[-1]
d=len(dig)

ans=0
if K==1:
  ans=a+9*(d-1)
elif K==2:
  if N<10:
    ans=0
  else:
    b=dig[-2]
    ans+=(a-1)*9+b
    ans+=a*9*(d-2)
    ans+=9*9*(d-1)*(d-2)//2
else: #K=3
  if N<100:
    ans=0
  else:
    b=dig[-2]
    c=dig[-3]
    if b>0:
      ans+=(a-1)*81+(b-1)*9+c
      ans+=((a-1)*81+(b-1)*9+9)*(d-3)
    ans+=a*9*9*(d-2)*(d-3)//2
    ans+=9*9*9*(d-1)*(d-2)*(d-3)//6
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
#桁の数字を取得
dig=[]
n=N
while n>0:
  dig.append(n%10)
  n//=10
a=dig[-1]
d=len(dig)

ans=0
if K==1:
  ans=a+9*(d-1)
elif K==2:
  if N<10:
    ans=0
  else:
    b=dig[-2]
    ans+=(a-1)*9+b
    ans+=a*9*(d-2)
    ans+=9*9*(d-1)*(d-2)//2
else: #K=3
  if N<100:
    ans=0
  else:
    b=dig[-2]
    c=dig[-3]
    if b>0:
      ans+=(a-1)*81+(b-1)*9+c
    ans+=a*b*9*(d-3)
    ans+=a*9*9*(d-2)*(d-3)//2
    ans+=9*9*9*(d-1)*(d-2)*(d-3)//6
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K=int(input())
#桁の数字を取得
dig=[]
n=N
while n>0:
  dig.append(n%10)
  n//=10
a=dig[-1]
d=len(dig)

ans=0
if K==1:
  ans=a+9*(d-1)
elif K==2:
  if N<10:
    ans=0
  else:
    b=dig[-2]
    ans+=(a-1)*9+b
    ans+=a*9*(d-2)
    ans+=9*9*(d-1)*(d-2)//2
else: #K=3
  if N<100:
    ans=0
  else:
    b=dig[-2]
    c=dig[-3]
    ans+=(a-1)*81+(b-1)*9+c
    ans+=a*b*9*(d-3)
    ans+=a*9*9*(d-2)*(d-3)//2
    ans+=9*9*9*(d-1)*(d-2)*(d-3)//6
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n = int(input())
k = int(input())
ans = 0
if k == 1:
	for i in range(1, 101):
		m = n//(10**i)
		if m == 0:
			ans += n//(10**(i-1))
			break
		else:
			ans += 9
	print(ans)

elif k == 2:
	if n < 10:
		print(0)
	elif n < 100:
		p = n//10
		q = (n-10*p)
		print(9*(p-1)+q)
	else:
		ans += 81
		for i in range(3, 101):
			m = n//(10**i)
			if m == 0:
				p = n//(10**(i-1))
				ans += 9*(p-1)*(i-1)
				q = n - p*(10**(i-1))
				for j in range(i-2, -1, -1):
					r = q//(10**j)
					if r != 0:
						ans += (r + j*9)
						break
					else:
						q -= r*(10**j)
				break
			else:
				ans += (i-1) * 81
		print(ans)

else:
	if n < 100:
		print(0)
	elif n < 1000:
		p = n//100
		q = (n-100*p)
		r = q//10
		print(81*(p-1)+9*(q-1)+r)
	else:
		ans += 729
		for i in range(4, 101):
			m = n//(10**i)
			if m == 0:
				p = n//(10**(i-1))
				ans += (p-1)*81*(i-1)*(i-2)//2
				q = n - p*(10**(i-1))
				for j in range(i-2, 0, -1):
					r = q//(10**j)
					if r == 0:
						continue
					else:
						ans += (81*j*(j-1)//2 + 9*j*(r-1))
						q -= r * (10**j)
						l = j-1
						while (l+1):
							th = q//(10**l)
							if th == 0:
								l -= 1
							else:
								ans += th + 9*l
								break
						break
			else:
				ans += (729 * (i-1) * (i-2)) //2
		print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
N=str(n)
l=len(N)
if k==1:
    ans=(l-1)*9+int(N[0])
elif k==2:
    ans=(l-1)*(l-2)*9*9//2+(int(N[0])-1)*(l-1)*9
    for i in range(1,l):
        if N[i]!='0':
            ans+=int(N[i])+(l-i-1)*9
            break
else:
    ans=(l-1)*(l-2)*(l-3)*9*9*9//6+(int(N[0])-1)*(l-1)*(l-2)*9*9//2
    for i in range(1,l):
        if N[i]!='0':
            if i!=l-1:
                ans+=int(N[i+1])+(l-i-2)*9
            else:
                ans+=int(N[l-1])
            ans+=(int(N[i])-1)*(l-i-1)*9
            ans+=(l-i-1)*(l-i-2)*9*9//2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
N=str(n)
l=len(N)
if k==1:
    ans=(l-1)*9+int(N[0])
elif k==2:
    ans=(l-1)*(l-2)*9*9//2+(int(N[0])-1)*(l-1)*9
    for i in range(1,l):
        if N[i]!='0':
            ans+=int(N[i])+(l-i-1)*9
            break
else:
    ans=(l-1)*(l-2)*(l-3)*9*9*9//6+(int(N[0])-1)*(l-1)*(l-2)*9*9//2
    for i in range(1,l):
        if N[i]!='0':
            if i!=n-1:
                ans+=int(N[i+1])+(l-i-2)*9
            ans+=(int(N[i])-1)*(l-i-1)*9
            ans+=(l-i-1)*(l-i-2)*9*9//2
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools
n=int(input())
k=int(input())
def comb(n,k):
    return len(list(itertools.combinations(range(n), k)))
x=str(n)
m=len(x)
ans=0
for i in range(1,m):
    ans+=(comb(i-1,k-1)*(9**k))
if k==1:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            ans+=1
elif k==2:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        ans+=1
                    else:
                        exit()
        else:
            break
else:
    for i in range(1,10):
        if i*(10**(m-1))<=n:
            for j in range(m-1):
                for a in range(1,10):
                    if i*(10**(m-1))+a*(10**(j))<=n:
                        for b in range(j):
                            for c in range(1,10):
                                if i*(10**(m-1))+a*(10**(j))+c*(10**(b))<=n:
                                    ans+=1
                                else:
                                    break
                    else:
                        break
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:

n = list(map(int, list(input())))
k = int(input())
l = len(n)
dp0 = [[0]*(k+1) for _ in range(l+1)] #小さいの確定
dp1 = [[0]*(k+1) for _ in range(l+1)]

for i in range(1, l+1):
    dp0[i][0] = 1

dp1[0][0] = 1

for i in range(l):
    for j in range(k):

        if n[i] > 0:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1] + dp1[i][j+1] + (n[i]-1)*dp1[i][j]
            dp1[i + 1][j + 1] = dp1[i][j]
        else:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1]
            dp1[i + 1][j + 1] = dp1[i][j + 1]



print(dp1[l][k])
print(dp0[l][k] + dp1[l][k])

Submission status: Wrong Answer

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

def solve(N, K):
    l = len(N)
    dp = [[[0] * (10) for i in range(2)] for _ in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        D = int(N[i])
        for j in range(2):
            for k in range(K+1):
                for d in range(10):
                    if j == 0 and d > D: break
                    dp[i+1][j or (d < D)][k if d != 0 else k+1] += dp[i][j][k]
    
    return dp[l][0][K] + dp[l][1][K]

print(solve(N,K))