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:
from collections import deque
n = input()
a = [int(i) for i in list(n)]
k = int(input())
n = len(n)
ans = 0

if k > n:
    ans = 0
elif k == 1:
    # n 桁目に非負整数
    ans += a[0]
    # n 桁目以外に非負整数
    ans += (n - 1)*9
elif k == 2:
    # 上と同様
    for i in range(1, n):
        if a[i] != 0:
            j = i
            break
    else:
        j = n - 1
    ans += a[j] + (n - j - 1)*9
    # n 桁目の最大ではない非負整数と n-1 桁目以降に 1 つ非負整数
    ans += (a[0] - 1)*(n - 1)*9
    # n-1 桁目以降の中から 2 つ非負整数
    ans += (n - 1)*(n - 2)*9*9//2
else:
    # 上と同様
    j = -1
    for i in range(1, n - 1):
        if a[i] != 0:
            j = i
            break
    if j != -1:
        ans += a[j + 1] + (n - j - 2)*9 + (a[j] - 1)*(n - j - 1)*9 + (n - j - 1)*(n - j - 2)*9*9//2
    # n 桁目の最大でない非負整数と n-1 桁目以降に 2 つ非負整数
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    # n-1 桁目以降から 3 つ非負整数
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = input()
a = [int(i) for i in list(n)]
k = int(input())
n = len(n)
ans = 0

if k > n:
    ans = 0
elif k == 1:
    # n 桁目に非負整数
    ans += a[0]
    # n 桁目以外に非負整数
    ans += (n - 1)*9
elif k == 2:
    # 上と同様
    ans += a[1] + (n - 2)*9
    # n 桁目の最大ではない非負整数と n-1 桁目以降に 1 つ非負整数
    ans += (a[0] - 1)*(n - 1)*9
    # n-1 桁目以降の中から 2 つ非負整数
    ans += (n - 1)*(n - 2)*9*9//2
else:
    # 上と同様
    j = -1
    for i in range(1, n - 1):
        if a[i] != 0:
            j = i
            break
    if j != -1:
        ans += a[j + 1] + (n - j - 2)*9 + (a[j] - 1)*(n - j - 1)*9 + (n - j - 1)*(n - j - 2)*9*9//2
    # n 桁目の最大でない非負整数と n-1 桁目以降に 2 つ非負整数
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    # n-1 桁目以降から 3 つ非負整数
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = input()
k = int(input())
a = [int(n[i]) for i in range(min(k, len(n)))]
n = len(n)
ans = 0

if k > n:
    ans = 0
elif k == 1:
    # n 桁目に非負整数
    ans += a[0]
    # n 桁目以外に非負整数
    ans += (n - 1)*9
elif k == 2:
    # 上と同様
    ans += a[1] + (n - 2)*9
    # n 桁目の最大ではない非負整数と n-1 桁目以降に 1 つ非負整数
    ans += (a[0] - 1)*(n - 1)*9
    # n-1 桁目以降の中から 2 つ非負整数
    ans += (n - 1)*(n - 2)*9*9//2
else:
    # 上と同様
    ans += a[2] + (n - 3)*9 + (n - 2)*(n - 3)*9*9//2
    if a[1] != 0:
        ans += (a[1] - 1)*(n - 2)*9
    # n 桁目の最大でない非負整数と n-1 桁目以降に 2 つ非負整数
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    # n-1 桁目以降から 3 つ非負整数
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = input()
k = int(input())
a = [int(n[i]) for i in range(min(k, len(n)))]
n = len(n)

if k > n:
    ans = 0
elif k == 1:
    ans = a[0] + (n - 1)*9
elif k == 2:
    ans = a[1] + (n - 2)*9 + (a[0] - 1)*(n - 1)*9 + (n - 1)*(n - 2)*9*9//2
else:
    ans = a[2] + (n - 3)*9 + (a[1] - 1)*(n - 2)*9 + (n - 2)*(n - 3)*9*9//2 + (a[0] - 1)*(n - 1)*(n - 2)*9*9//2 + (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

Submission status: Wrong Answer

Solution code:
n=input()
l=len(n)
k=int(input())
if l<k:print(0);exit()
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
if k==2:
  ans=((l-2)*9)+int(n[1])
  ans+=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
  print(ans)
if k==3:
  ans=((l-3)*9)+int(n[2])
  ans+=((l-2)*(l-3)//2)*81+(int(n[1])-1)*((l-2)*9)
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Wrong Answer

Solution code:
n=input()
l=len(n)
k=int(input())
if l<k:print(0);exit()
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Wrong Answer

Solution code:
n=input()
if n[0]=="0":ans=1/0
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Wrong Answer

Solution code:
n=input()
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
  exit()
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Wrong Answer

Solution code:
n=input()
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
  exit()
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Wrong Answer

Solution code:
n=input()
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
  exit()
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = [int(i) for i in STR()]
k = INT()
l = len(n)
dp = [[[0, 0] for _ in range(l)] for _ in range(k + 1)] #dp[i個の0以外][j桁目まで][0:未満 1:未決定]
dp[0][0][0] = 1 #0
dp[1][0][1] = 1 #n[0]
dp[1][0][0] = n[0] - 1 #1からn[0] - 1
for j in range(1, l):
    dp[0][j][0] = dp[0][j - 1][0] #全部0

    for i in range(1, k + 1):
        dp[i][j][0] += dp[i - 1][j - 1][0] * 9 #0以外i-1個に0以外を
        dp[i][j][0] += dp[i - 1][j - 1][1] * (n[j] - 1) #0以外i個の未満未決定にn[j]未満の数を
        dp[i][j][0] += dp[i][j - 1][0] #0以外i個かつ未満に0を
        dp[i][j][0] += dp[i][j - 1][1] if n[j] > 0 else 0 #0以外i個かつ未満未決定に0を

        dp[i][j][1] += dp[i][j - 1][1] if n[j] == 0 else 0 #0以外i個の未満未決定にn[j]を
        dp[i][j][1] += dp[i - 1][j - 1][1] if n[j] > 0 else 0 #0以外i-1個の未満未決定にn[j]を
print(sum(dp[k][l - 1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
n = str(N)
l = len(n)
m = int(n[0])
if K == 1:
    if l == 1:ans = N
    else:ans = 9*(l-1)+m
elif K == 2:
    if l < 2:ans = 0
    elif l == 2:ans = (m-1)*9+int(n[-1])
    else:ans = 9*(l-1)*9*(l-2)//2+(m-1)*(l-1)*9+1+(l-2)*9
else:
    if l < 3:ans = 0
    elif l == 3:ans = (m-1)*9*9+int(n[1])*int(n[2])
    else:ans = 9*9*9*(l-1)*(l-2)*(l-3)//6+(m-1)*9*9*(l-1)*(l-2)//2+int(n[1])*int(n[2])+9*9*(l-3)*(l-4)//2+(int(n[1])+int(n[2]))*9*(l-3)
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

def solve_one(N):
    N_len = len(N)
    ans = N[0] + 9 * (N_len-1)
    return ans

def solve_two(N):
    N_len = len(N)
    non_zero_index = 0
    index = 1
    while index < N_len:
        if N[index] != 0:
            non_zero_index = index
            break
        index += 1
    ans = N[non_zero_index] + 9 * len(N[non_zero_index+1:]) 
    #print(f'ans {ans}')
    # 1~N[0]-1
    ans += (N[0]-1) * 9 *(N_len-1)
    #print(f'ans {ans}')
    for i in range(1,N_len-1):
        ans += 9*9*i
    return ans

N = list(map(int, input()))
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    ans = solve_one(N)
elif K == 2:
    if N_len >= 2:
        ans = solve_two(N)
elif K == 3:
    if N_len >= 3:
        non_zero_index = [0] * 2
        index = 1
        count = 0
        while count < 2 and index < N_len:
            if N[index] != 0:
                non_zero_index[count] = index
                count += 1
            index += 1
        # N[0],N[1]　を固定
        if non_zero_index[1] < N_len:
            ans = N[non_zero_index[1]] + 9 * len(N[non_zero_index[1]+1:]) 
        # N[0], 1~N[1]-1
        ans += max(N[non_zero_index[0]]-1,0) * 9 * len(N[non_zero_index[0]+1:])
        # N[0], N[1] == 0
        ans += solve_two(N[non_zero_index[1]:])
        # 1~N[0]-1
        ans += (N[0]-1) * 9**2 * comb(N_len-1,2,exact=True)     
        #print(f'ans {ans}')
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

N = list(map(int, input()))
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    ans = N[0] + 9 * (N_len-1)
elif K == 2:
    if N_len >= 2:
        non_zero_index = 0
        index = 1
        while index < N_len:
            if N[index] != 0:
                non_zero_index = index
                break
            index += 1
        ans = N[non_zero_index] + 9 * len(N[non_zero_index+1:]) 
        #print(f'ans {ans}')
        # 1~N[0]-1
        ans += (N[0]-1) * 9 *(N_len-1)
        #print(f'ans {ans}')
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    if N_len >= 3:
        non_zero_index = [0] * 2
        index = 1
        count = 0
        while count < 2 and index < N_len:
            if N[index] != 0:
                non_zero_index[count] = index
                count += 1
            index += 1
        # N[0],N[1]　を固定
        #print(f'index {index}')
        if index <= N_len-2:
            ans = N[non_zero_index[1]] + 9 * len(N[non_zero_index[1]+1:]) 
        #print(f'ans {ans}')
        # N[0], 1~N[1]-1
        ans += max(N[non_zero_index[0]]-1,0) * 9 * len(N[non_zero_index[0]+1:])
        #print(f'ans {ans}')
        ans += 9**2 * comb(len(N[non_zero_index[1]:]),2,exact=True)
        # 1~N[0]-1
        ans += (N[0]-1) * 9**2 * comb(N_len-1,2,exact=True)     
        #print(f'ans {ans}')
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)
#print(f'diff {9**3*comb(N_len,3,exact=True)-ans}')

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
import time

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

N_len = len(N)

ans = 0
if K == 1:
    time.sleep(0.3)
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    time.sleep(0.6)
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    time.sleep(0.9)
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

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

N_len = len(N)

ans = 0
if K == 1:
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    if N_len >= 3:
        # N[0],N[1]
        if int(N[1]) != 0:
            ans = int(N[2]) + 9 * (N_len-3)
        #print(f'ans {ans}')
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        #print(f'ans {ans}')
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        #print(f'ans {ans}')
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        #print(f'ans {ans}')
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb

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

N_len = len(N)

ans = 0
if K == 1:
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations, product

def nCr(n, r):
    total = 1
    r = min(r, n - r)
    for i in range(r):
      total *= (n - i) / (r - i)
    return int(total)

n = int(input())
k = int(input())
size = len(str(n))
count = 0 if k > size - 1 else (nCr(size - 1, k) * (9 ** k))
if k == 1:
  count += sum(i * (10 ** (size - 1)) <= n for i in range(1, 9))
else:
  for digits in combinations(range(size - 1), k - 1):
    digits = [size - 1] + list(digits)
    count += sum(
      sum(num * (10 ** digit) for num, digit in zip(nums, digits)) <= n
      for nums in product(range(1, 10), repeat=k)
    )
print(count)

Submission status: Wrong Answer

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

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    for i in range(le-1):
      if int(N[i+1]) == 0:
        j+=1
        break
      
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    for i in range(le-1):
      if int(N[i+1]) == 0:
        j+=1
        break
    n2 = N[j:le]
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Wrong Answer

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

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    n = N[1:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    n1 = N[2:le]
    n2 = N[1:le]
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))

Submission status: Wrong Answer

Solution code:
def comb(x,y):
    if y==1:
        return x
    elif y==2:
        return max(x*(x-1)//2, 0)
    elif y==3:
        return max(x*(x-1)*(x-2)//6, 0)
n = int(input())
k = int(input())
digit = len(str(n))
ans1 = comb(digit-1, k) * (9**k)
lst = [int(i) for i in list(str(n))]
if n < int('1'*k):
    print(0)
    exit()
if k==1:
    ans2 = lst[0]
    
elif k==2:
    ans2 = 0
    ans2 += (lst[0]-1) * (digit-1) * 9
    if lst[1]!=0:
        ans2 += lst[1] + (digit-2)*9
    
elif k==3:
    ans2 = 0
    ans2 += (lst[0]-1) * comb(digit-1, 2) * (9**2)
    if lst[1]!=0:
        ans2 += lst[1]*(digit-2)*9 + comb(digit-2, 2)*(9**2)
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
def comb(x,y):
    if y==1:
        return x
    elif y==2:
        return max(x*(x-1)//2, 0)
    elif y==3:
        return max(x*(x-1)*(x-2)//6, 0)
n = int(input())
k = int(input())
digit = len(str(n))
ans1 = comb(digit-1, k) * (9**k)
lst = [int(i) for i in list(str(n))]
if digit - list(str(n)).count('0') < k:
    print(0)
    exit()
if k==1:
    ans2 = lst[0]
    
elif k==2:
    ans2 = 0
    ans2 += (lst[0]-1) * (digit-1) * 9
    ans2 += lst[1] + (digit-2)*9
    
elif k==3:
    ans2 = 0
    ans2 += (lst[0]-1) * comb(digit-1, 2) * (9**2)
    ans2 += lst[1]*(digit-2)*9 + comb(digit-2, 2)*(9**2)
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
def comb(x,y):
    if y==1:
        return x
    elif y==2:
        return max(x*(x-1)//2, 0)
    elif y==3:
        return max(x*(x-1)*(x-2)//6, 0)
n = int(input())
k = int(input())
digit = len(str(n))
ans1 = comb(digit-1, k) * (9**k)
lst = [int(i) for i in list(str(n))]

if digit < k:
    print(0)
    exit()

if k==1:
    ans2 = lst[0]
elif k==2:
    ans2 = 0
    ans2 += (lst[0]-1) * (digit-1) * 9
    ans2 += lst[1] + (digit-2)*9
elif k==3:
    ans2 = 0
    ans2 += (lst[0]-1) * comb(digit-1, 2) * (9**2)
    ans2 += lst[1]*(digit-2)*9 + comb(digit-2, 2)*(9**2)
print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
n = list(map(int,list(input())))
k = int(input())
l = len(n)
count = 0 # 0でない数字がnに何度出てきたか
lst = [[0]*(k+1) for _ in range(l+1)] #nより小さい
for i in range(l):
    if count < k:
        lst[i+1][count] += 1
        lst[i+1][count+1] += n[i]-1
    if count == k:
        lst[i+1][count] += 1
    for j in range(k):
        lst[i+1][j] += lst[i][j]
        lst[i+1][j+1] += 9*lst[i][j]
    lst[i+1][k] += lst[i][k]
    if n[i] != 0:
        count += 1
if count == k:
    print(lst[l][k]+1)
else:
    print(lst[l][k])

Submission status: Wrong Answer

Solution code:
def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + mondai(d, 1)
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = mondai(n, k)
    
print(ans)

Submission status: Wrong Answer

Solution code:
def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + mondai(d, 1)
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = mondai(n, k)

Submission status: Wrong Answer

Solution code:
def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + (keta - 1) * 9 + b[-1]
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = mondai(n, k)
    
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
sum=0
for i in range(1,n+1):
    a=list(str(i))
    if a.count("0")==k:
        sum+=1

print(sum)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
sum=0
for i in range(1,n+1):
    a=list(str(i))
    if a.count('0')==k:
        sum+=1

print(sum)

Submission status: Wrong Answer

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

c=len(str(N))
a=[[0 for _ in range(5)] for _ in range(c+1)]
a[0][0],a[1][0],a[1][1]=1,1,9

def dfs(n,k,o):
  d=n//10**(o-1)
  if d==0:
    return a[o-2][k]+(dfs(n,k,o-1) if o>1 else 0)
  else:
    return a[o-1][k-1]*((d-1) if o>1 else d) +a[o-1][k]+ (dfs(n-d*10**(o-1),k-1,o-1) if (k>0 and o>1) else 0)

for i in range(2,c):
  for j in range(4):
    a[i][j]=a[i-1][j-1]*9+a[i-1][j]

print(dfs(N,K,c))

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = stdin.readline().rstrip()
K = int(stdin.readline().rstrip())

N = N[::-1]

dp = [[0] * len(N) for i in range(3)]

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

for i in range(1, len(N)):
    if N[i] == '0':
        dp[0][i] = dp[0][i - 1]
    else:
        dp[0][i] = int(N[i]) + 9 * i

for i in range(1, len(N)):
    if N[i] == '0':
        dp[1][i] = dp[1][i - 1]
    else:
        dp[1][i] = dp[0][i - 1] + 9 * 9 * i * (i - 1)  // 2 + 9 * i * (int(N[i]) - 1)

for i in range(2, len(N)):
    if N[i] == '0':
        dp[2][i] = dp[2][i - 1]
    else:
        dp[2][i] = dp[1][i - 1] + 9 * 9 * 9 * i * (i - 1) * (i - 2) // 6 + 9 * 9 * i * (i - 1) // 2 * (int(N[i]) - 1)

print(dp[1][len(N) - 1])

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = stdin.readline().rstrip()
K = int(stdin.readline().rstrip())

N = N[::-1]

dp = [[0] * len(N) for i in range(3)]

for i in range(len(N)):
    dp[0][i] = int(N[i]) + 9 * i

for i in range(1, len(N)):
    dp[1][i] = dp[0][i - 1] + 9 * 9 * i * (i - 1)  // 2 + 9 * i * (int(N[i]) - 1)

for i in range(2, len(N)):
    dp[2][i] = dp[1][i - 1] + 9 * 9 * 9 * i * (i - 1) * (i - 2) // 6 + 9 * 9 * i * (i - 1) // 2 * (int(N[i]) - 1)

print(dp[K - 1][len(N) - 1])

Submission status: Wrong Answer

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

c=len(str(N))
a=[[0 for _ in range(5)] for _ in range(c+1)]
a[0][0],a[1][0],a[1][1]=1,1,9

def dfs(n,k,o):
  d=n//10**(o-1)
  return a[o-1][k-1]*((d-1) if o>1 else d) +a[o-1][k]+ (dfs(n-d*10**(o-1),k-1,o-1) if (k>0 and o>1) else 0)

for i in range(2,c):
  for j in range(4):
    a[i][j]=a[i-1][j-1]*9+a[i-1][j]

print(dfs(N,K,c))

Submission status: Wrong Answer

Solution code:
import math
import sys

comb=[0,0,0,1,3,6,10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950]
n=int(input())
k=int(input())
s=str(n)
L=len(s)

ans=0
if n<k:
    ans=0

elif k==1:
    for i in range(L):
        for a in range(1,10):
            if a*(10**i)<=n:
                ans+=1

elif k==2:
    for i in range(1,L):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=n: ans+=1


elif k==3 and L<4:
    for a in range(1,10):
        for b in range(1,10):
            for c in range(1,10):
                if a*100+b*10+c<=n: ans+=1

elif k==3 and L>=4:
    for i in range(L):
        ans+=comb[i]
    ans*=9**3
    ans+=comb[L]* 81 * (int(s[0])-1) #1桁目 1-int(s[0])-1
    if int(s[1])>0:
        ans+=comb[L-1]*81
        ans+=(L-2)*9*(int(s[1])-1)

    m=int(s[2:])

    for i in range(L-1):
        for a in range(1,10):
            if a*(10**i)<=m: ans+=1
                

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

comb=[0,0,0,1,3,6,10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950]
n=int(input())
k=int(input())
s=str(n)
L=len(s)

ans=0
if n<k:
    ans=0

elif k==1:
    for i in range(L):
        for a in range(1,10):
            if a*(10**i)<=n:
                ans+=1

elif k==2:
    for i in range(1,L):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=n: ans+=1


elif k==3 and L<4:
    for a in range(10):
        for b in range(10):
            for c in range(10):
                if a*100+b*10+c<=n: ans+=1

elif k==3 and L>=4:
    a=0
    while True:
        a+=1

    for i in range(L):
        ans+=comb[i]
    ans*=9**3
    ans+=comb[L]* 81 * (int(s[0])-1) #1桁目 1-int(s[0])-1
    if int(s[1])>0:
        ans+=comb[L-1]*81
        ans+=(L-2)*9*(int(s[1])-1)


    m=int(s[2:])

    for i in range(L-1):
        for a in range(1,10):
            if a*(10**i)<=m: ans+=1
                

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

comb=[0,0,0,1,3,6,10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950]
n=int(input())
k=int(input())
s=str(n)
L=len(s)

ans=0
if n<k:
    ans=0

elif k==1:
    for i in range(L+2):
        for a in range(1,10):
            if a*10**i<=n:
                ans+=1

elif k==2:
    for i in range(1,L+2):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=n: ans+=1


elif k==3 and L<4:
    for a in range(10):
        for b in range(10):
            for c in range(10):
                if a*100+b*10+c<=n: ans+=1

elif k==3 and L>=4:
    for i in range(L):
        ans+=comb[i]
    ans*=9**3
    ans+=comb[L]* 81 * (int(s[0])-1) #1桁目 1-int(s[0])-1
    if int(s[1])>0:
        ans+=comb[L-1]*81
        ans+=(L-2)*9*(int(s[1])-1)


    m=int(s[2:])

    for i in range(L-1):
        for a in range(1,10):
            if a*(10**i)<=m: ans+=1
                

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

comb=[0,0,0,1,3,6,10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, 2628, 2701, 2775, 2850, 2926, 3003, 3081, 3160, 3240, 3321, 3403, 3486, 3570, 3655, 3741, 3828, 3916, 4005, 4095, 4186, 4278, 4371, 4465, 4560, 4656, 4753, 4851, 4950]
n=int(input())
k=int(input())
s=str(n)
L=len(s)

ans=0
if n<k:
    ans=0

elif k==1:
    for i in range(L):
        for a in range(1,10):
            if a*10**i<=n:
                ans+=1

elif k==2:
    for i in range(1,L):
        for j in range(i):
            for a in range(1,10):
                for b in range(1,10):
                    if a*(10**i)+b*(10**j)<=n: ans+=1


elif k==3:
    if L<4:
        for a in range(10):
            for b in range(10):
                for c in range(10):
                    if a*100+b*10+c<=n: ans+=1

    else:
        for i in range(L):
            ans+=comb[i]
        ans*=9**3
        ans+=comb[L]* 81 * (int(s[0])-1) #1桁目 1-int(s[0])-1
        if int(s[1])>0:
            ans+=comb[L-1]*81
            ans+=(L-2)*9*(int(s[1])-1)


        m=int(s[2:])

        for i in range(L-1):
            for a in range(1,10):
                if a*(10**i)<=m: ans+=1
                

print(ans)