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 = int(input())
K = int(input())

let = list(map(int, list(str(N))))
digit = len(let)

if K > digit:
  print(0)
  exit()

def comb(n, k):
  nu = 1
  de = 1
  if n-k < k:
    k = n - k
  for i in range(0,k):
    nu *= n-i
    de *= k-i
  return int(nu/de)

def test(N):
  digit = 1
  arr = [0] * (1 + digit)
  for i in range(1,N + 1):
    cnt = 0
    temp = list(str(i))
    for j in temp:
      if j == "0":
        cnt += 1
    arr[cnt] += 1
    if len(str(i+1)) > digit:
      digit = len(str(i+1))
      print(arr)
      arr = [0] * (1 + digit)
  print(arr)
      
def sum_by_digit_and_K(digit, K):
  temp = 9 ** K 
  res = []
  for i in range(1, digit+1-K):
    res.append(comb(i,K-1) * temp)
  print(res)
  return sum(res)

def solve(N, K, digit, let):
  res = 0
  for i in range(K):
    res += let[i] * sum_by_digit_and_K(digit-i, K-i)
  return res
        
print(solve(N, K, digit, let))

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve(n, k, m):
    ans = 0
    for i in range(k, m):
        # i: 桁数
        if k == 1:
            ans += 9
        else:
            ans += pow(9, k)*comb(i-1, k-1)
    if k == 1:
        ans += int(n[0])
    elif k == 2:
        ans += (int(n[0])-1)*pow(9, k-1)*comb(m-1, k-1)
        j = 1
        while j < m and n[j] == '0':
            j += 1
        if j < m:
            ans += int(n[j]) + pow(9, k-1)*comb(m-1-j, k-1)
    else:
        while m >= k and n.count('0') > m - k:
            n = str(int(n)-1)

        if m > len(n):
            return ans

        m = len(n)
        a = []
        for i in range(m):
            if len(a) < 3 and n[i] != '0':
                a.append(i)

        if len(a) == 3:
            ans += 1 + int(n[a[2]])-1 + 9*comb(m-1-a[2], 1)
            ans += (int(n[a[1]])-1)*9*comb(m-1-a[1], 1) + 9*9*comb(m-1-a[1], 2)
            ans += (int(n[a[0]])-1)*9*9*comb(m-1-a[0], 2)
    print(ans)
    return ans

def solve2(n, k, m):
    ans = 0
    for i in range(1, int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            ans += 1
    print(ans)
    return ans

if __name__ == '__main__':
    n = input()
    k = INT()
    m = len(n)

    solve(n,k,m)
    #solve2(n,k,m)
    #for i in range(10000):
    #    print(i)
    #    if solve(str(i), k, len(str(i))) != solve2(str(i), k, len(str(i))):
    #        break

Submission status: Wrong Answer

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

DP = [[[0] * (K+2) 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+1):
        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 = input()
a = list(n)
k = int(input())
n = len(a)
for i in range(n):
    a[i] = int(a[i])
dp = [[[0 for i in range(2)] for i in range(k+2)]for i  in range(n)]
dp[0][0][0] = 1
dp[0][1][0] = a[0]-1
dp[0][1][1] = 1
for i in range(n-1):
    for j in range(k+1):
        if a[i+1] == 0:
            dp[i+1][j][1] += dp[i][j][1]
            dp[i+1][j][0] += dp[i][j][0]
            dp[i+1][j+1][0] += dp[i][j][0]*9+dp[i][j][1]*(a[i+1]-1)
        else:
            dp[i+1][j][0] += dp[i][j][0]+dp[i][j][1]
            dp[i+1][j+1][0] += dp[i][j][1]*(a[i+1]-1)+dp[i][j][0]*9
            dp[i+1][j+1][1] += dp[i][j][1]
print(dp[n-1][k][0]+dp[n-1][k][1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def f(dig, under, num):
  #if dig >= l: return 0
  if num > l - dig: return 0
  if num == 0: return 1
  if under:
    if n[dig] == 0:
      res = f(dig+1, True, num)
      #print(dig, under, num, res)
      return res
    else:
      res = f(dig+1, False, num)
      res += (int(n[dig])-1) * f(dig+1, False, num-1)
      res += f(dig+1, True, num-1)
      #print(dig, under, num, res)
      return res
  else:
    res = f(dig+1, False, num)
    res += 9 * f(dig+1, False, num-1)
    #print(dig, under, num, res)
    return res

ans = f(0, True, k)
print(ans)

Submission status: Wrong Answer

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

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

D3 = [0]*100
n = 0
for i in range(100, 1000):
    if str(i).count("0") == 0:
        n += 1
        D3.append(n)
    else:
        D3.append(n)
D2 = [0]*10
n = 0
for i in range(10, 100):
    if str(i).count("0") == 0:
        n += 1
        D2.append(n)
    else:
        D2.append(n)
ans = 0
if K==3:
    for i in range(l):
        for j in range(i+1, l):
            for k in range(j+1, l):
                if (i,j,k)==(0,1,2):
                    ans += D3[int(N[:3])]
                elif (i,j)==(0,1):
                    ans += 9 * D2[int(N[:2])]
                elif i==0:
                    ans += 81 * int(N[0])
                else:
                    ans += 729
elif K==2:
    for i in range(l):
        for j in range(i+1, l):
            if (i,j)==(0,1):
                ans += D2[int(N[:2])]
            elif i==0:
                ans += 9 * int(N[0])
            else:
                ans += 81
else:
    for i in range(l):
        if i==0:
            ans += int(N[0])
        else:
            ans += 9
print(ans)

Submission status: Wrong Answer

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

ans = 0
if k == 1:
    ans = n[0] + (l - 1) * 9
elif k == 2:
    if l == 1:
        ans = 0
    else:
        for i in range(l - 1):
            p = True
            for j in range(i + 1, l):
                if i == 0 and p:
                    ans += (n[i] - 1) * 9 + n[j]
                elif i == 0:
                    ans += n[i] * 9
                else:
                    ans += 9 * 9
                if n[j] != 0:
                    p = False
else:
    if l <= 2:
        ans = 0
    else:
        for i in range(l - 2):
            p1 = True
            for j in range(i + 1, l - 1):
                p2 = True
                for k in range(j + 1, l):
                    if i == 0 and p1 and p2:
                        ans += (n[i] - 1) * 9 * 9 + (n[j] - 1) * 9 + n[k]
                    elif i == 0 and p1 and not p2:
                        ans += (n[i] - 1) * 9 * 9 + n[j] * 9
                    elif i == 0 and not p1:
                        ans += n[i] * 9 * 9
                    else:
                        ans += 9 * 9 * 9
                    if n[k] != 0:
                        p2 = False
                if n[j] != 0:
                    p1 = False
print(ans)

Submission status: Wrong Answer

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

ans = 0
if k == 1:
    ans = n[0] + (l - 1) * 9
elif k == 2:
    if l == 1:
        ans = 0
    else:
        for i in range(l - 1):
            p = True
            for j in range(i + 1, l):
                if i == 0 and p:
                    ans += (n[i] - 1) * 9 + n[j]
                elif i == 0:
                    ans += n[i] * 9
                else:
                    ans += 9 * 9
                if n[j] != 0:
                    p = False
else:
    if l <= 2:
        ans = 0
    else:
        for i in range(l - 2):
            p1 = True
            for j in range(i + 1, l - 1):
                p2 = True
                for k in range(j + 1, l):
                    if i == 0 and p1 and p2:
                        ans += (n[i] - 1) * 9 * 9 + (n[j] - 1) * 9 + n[k]
                    elif i == 0 and p1 and not p2:
                        ans += (n[i] - 1) * 9 * 9 + n[j] * 9
                    elif i == 0 and not p1 and p2:
                        ans += n[i] * 9 * 9
                    else:
                        ans += 9 * 9 * 9
                    if n[k] != 0:
                        p2 = False
                if n[j] != 0:
                    p1 = False
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = list(input())
K = int(input())
length = len(N)

dp = [[[0]*2 for _ in range(K+1)] for _ in range(length+1)]
dp[0][0][1] = 1
for i in range(length):
    n = int(N[i])
    for k in range(K+1):
        if k==K:
            dp[i+1][k][0]+=dp[i][k][0]
            if n==0:
                dp[i+1][k][1]+=dp[i][k][1]
            continue
        for j in range(10):
            if j==0:
                if n==0:
                    dp[i+1][k][0]+=dp[i][k][0]
                    dp[i+1][k][1]+=dp[i][k][1]
                else:
                    dp[i+1][k][0]+=dp[i][k][0]+dp[i][k][1]
            elif j==n:
                dp[i+1][k+1][1]+=dp[i][k][1]
                dp[i+1][k+1][0]+=dp[i][k][0]
            elif j<n:
                dp[i+1][k+1][0]+=dp[i][k][0]+dp[i][k][1]
            else:
                dp[i+1][k+1][0]+=dp[i][k][0]
print(dp[-1][K][0]+1)

Submission status: Wrong Answer

Solution code:
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):
  if D<=K:
    break
  score+=calc(int(a),D-i,K)
  if a!="0":
    K-=1
  if K==0:
    break
print(int(score))

Submission status: Wrong Answer

Solution code:
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):
  if D-i>K:
  	score+=calc(int(a),D-i,K)
  if a!="0":
    K-=1
  if K==0:
    break
print(int(score))

Submission status: Wrong Answer

Solution code:
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):
  if D-i>=K:
  	score+=calc(int(a),D-i,K)
  if a!="0":
    K-=1
  if K==0:
    break
print(int(score))

Submission status: Wrong Answer

Solution code:
def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):
  score+=calc(int(a),D-i,K)
  if a!="0":
    K-=1
  if K==0:
    break
print(int(score))

Submission status: Wrong Answer

Solution code:
def resolve():
    N = list(input())
    lenN = len(N)
    K = int(input())
    dp = [[[None, None] for _ in range(K+1)] for __ in range(lenN)]

    def rec(i, k, smaller):
        if k==0:
            return 1
        if i>=lenN:
            return 0
        
        if dp[i][k][int(smaller)] is not None:
            return dp[i][k][int(smaller)]
        
        ret = 0
        if smaller:
            ret += rec(i+1, k, True)
            ret += rec(i+1, k-1, True) * 9
        else:
            if N[i] == "0":
                ret += rec(i+1, k, True)
            else:
                ret += rec(i+1, k, True) # 次も0を選ぶ
                ret += rec(i+1, k-1, True) * (int(N[i]) - 1) # 0 < ?? < N[i]
                ret += rec(i+1, k-1, False) # N[i]を選ぶ、真にsmallerとは限らないのでまだFalse
        
        dp[i][k][int(smaller)] = ret
        return ret

    print(rec(0, K, False))
    
    
if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
ans = 0
if K == 1:
    ans +=  9 * (len(str(N))-1)
elif K == 2:
    for i in range(2,len(str(N))):
        print(i)
        ans += 9*9*(i-1)
else:
    n = len(str(N))
    for i in range(3,len(str(N))):
        ans += 9*81*(i-1)*(i-2)//2
#         for j in range(1,i-1):
#             for k in range(2,i):
#                 ans += 9*9*9

#print(ans)
if K == 1:
    ans += int(str(N)[0])
elif K == 2:
    val = int(str(N)[0])
    for i in range(1,len(str(N))):
        if i == 1:
            ans -= 9-int(str(N)[1])
        ans += val*9
else:
    # for i in range(1,int(str(N)[0])):
    #     for j in range(1,len(str(N))-1):
    #         for k in range(j+1,len(str(N))):
    #             if j == 1:
    #                 if k == 2:
    #                     ans += int(str(N)[j]) * int(str(N)[k])
    #                 else:
    #                     ans += 9*int(str(N)[j])
    #             else:
    #                 ans += 81
    n = len(str(N))
    d = list(str(N))
    ans += 9*81*(n*(n-1))//2
    ans -= (9-int(d[0])) * 81 * (n*(n-1)//2)
    ans -= (9-int(d[1])) * 9 * (n-1)*(n-2)//2
    ans -= (9-int(d[2]))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
ans = 0
if K == 1:
    ans +=  9 * (len(str(N))-1)
elif K == 2:
    for i in range(2,len(str(N))):
        print(i)
        ans += 9*9*(i-1)
else:
    n = len(str(N))
    for i in range(3,len(str(N))):
        for j in range(1,i-1):
            for k in range(2,i):
                ans += 9*9*9
print(ans)
if K == 1:
    ans += int(str(N)[0])
elif K == 2:
    val = int(str(N)[0])
    for i in range(1,len(str(N))):
        if i == 1:
            ans -= 9-int(str(N)[1])
        ans += val*9
else:
    for i in range(1,int(str(N)[0])):
        for j in range(1,len(str(N))-1):
            for k in range(j+1,len(str(N))):
                if j == 1:
                    if k == 2:
                        ans += int(str(N)[j]) * int(str(N)[k])
                    else:
                        ans += 9*int(str(N)[j])
                else:
                    ans += 81
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
k=int(input())
a=math.log10(n)
if k==1:
    print(int((a//1)*9+n//(10**(a//1))))
elif k==2:
    if 1<=n<=10:
        print(0)
    else:
        b=a//1
        c=int(81*(1/2)*b*(b-1))
        if n%10**b==0:
            print(int(c+9*b*(n//10**b-1)))
        else:
            d=math.log10(n%10**b)
            print(int(c+9*b*(n//10**b-1)+(d//1)*9+(n%10**b)//(10**(d//1))))
else:
    if 1<=n<=110:
        print(0)
    else:
        sumnum=0
        b=int(a//1)
        num=0
        for i in range(2,b):
            num+=math.factorial(i)//(2*math.factorial(i-2))
        sumnum+=num*729
        sumnum+=int((n//10**b-1)*81*(1/2)*b*(b-1))
        if 0<=n%10**b<=10:
            print(int(sumnum))
        else:
            d=math.log10(n%10**b)
            e=d//1
            sumnum+=int(81*(1/2)*e*(e-1))
            if n%10**b%10**e==0:
                print(int(sumnum+9*e*(n%10**b//10**e-1)))
            else:
                f=math.log10((n%10**b)%10**e)
                print(int(sumnum+9*e*(n%10**b//10**e-1)+(f//1)*9+(n%10**b%10**e)//(10**(f//1))))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
k=int(input())
a=math.log10(n)
if k==1:
    print(int((a//1)*9+n//(10**(a//1))))
elif k==2:
    if 1<=n<=10:
        print(0)
    else:
        b=a//1
        c=int(81*(1/2)*b*(b-1))
        if n%10**b==0:
            print(int(c+9*b*(n//10**b-1)))
        else:
            d=math.log10(n%10**b)
            print(int(c+9*b*(n//10**b-1)+(d//1)*9+(n%10**b)//(10**(d//1))))
else:
    if 1<=n<=110:
        print(0)
    else:
        sumnum=0
        b=int(a//1)
        num=0
        for i in range(2,b):
            num+=math.factorial(i)//(2*math.factorial(i-2))
        sumnum+=num*729
        sumnum+=int((n//10**b-1)*81*(1/2)*b*(b-1))
        if 0<=n%10**b<=10:
            print(int(sumnum))
        else:
            d=math.log10(n%10**b)
            e=d//1
            sumnum+=int(81*(1/2)*e*(e-1))
            if n%10**b%10**e==0:
                print(sumnum+9*e*(n%10**b//10**e-1))
            else:
                f=math.log10((n%10**b)%10**e)
                print(int(sumnum+9*e*(n%10**b//10**e-1)+(f//1)*9+(n%10**b%10**e)//(10**(f//1))))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
k=int(input())
a=math.log10(n)
if k==1:
    print(int((a//1)*9+n//(10**(a//1))))
elif k==2:
    if 1<=n<=10:
        print(0)
    else:
        b=a//1
        c=int(81*(1/2)*b*(b-1))
        if n%10**b==0:
            print(c)
        else:
            d=math.log10(n%10**b)
            print(int(c+9*b*(n//10**b-1)+(d//1)*9+(n%10**b)//(10**(d//1))))
else:
    if 1<=n<=110:
        print(0)
    else:
        sumnum=0
        b=int(a//1)
        num=0
        for i in range(2,b):
            num+=math.factorial(i)//(2*math.factorial(i-2))
        sumnum+=num*729
        sumnum+=int((n//10**b-1)*81*(1/2)*b*(b-1))
        if 0<=n%10**b<=10:
            print(int(sumnum))
        else:
            d=math.log10(n%10**b)
            e=d//1
            sumnum+=int(81*(1/2)*e*(e-1))
            if n%10**b%10**e==0:
                print(sumnum)
            else:
                f=math.log10((n%10**b)%10**e)
                print(int(sumnum+9*e*(n%10**b//10**e-1)+(f//1)*9+(n%10**b%10**e)//(10**(f//1))))

Submission status: Wrong Answer

Solution code:
def main():
    h = int(input())
    ans = 1
    if h >= 1:
        i = 0
        while 2**i <= h:
            ans = 2**(i+1) - 1
            i += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

    ans = 0
    # 最上位K桁が0の場合
    # l-K_C_K * 9^K
    if K == 1:
        ans += (l-1) * 9
    elif K == 2:
        ans += (l-1) * (l-2) * 81 // 2
    else:
        ans += (l-1) * (l-2) * (l-3) * 729 // 6

    if K == 1:
        # 最上位の数以外0
        ans += int(N[0])
    elif K == 2:
        # 最上位1桁が0ではなく,残りl-1桁中1桁だけ0以外（Nより大きくならないように注意）
        if l >= 2:
            ans += int(N[0]) * (l-1) * 9 - (9 - int(N[1]))
    else:
        # 最上位1桁が0ではなく,残りl-1桁中2桁だけ0以外（Nより大きくならないように注意）
        if l >= 3:
            ans += int(N[0]) * (l-1) * (l-2) * 81 // 2 - (99 - int(N[1:3]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if len(N) < K:
  print(0)
  exit()

ans = [1, int(N[-1]), 0, 0];
nine = [1, 9, 81, 729]

def combination(N,K):
  if N < K:
    return 0
  elif K == 0:
    return 0
  elif K == 1:
    return N
  elif K == 2:
    return N*(N-1)//2
  else:
    return N*(N-1)*(N-2)//6

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += nine[j]*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*nine[j-1] + ans[j-1]
    ans = a
print(ans[K])

Submission status: Wrong Answer

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

if len(N) < K:
  print(0)
  exit()

ans = [1, int(N[-1]), 0, 0];
nine = [1, 9, 81, 729]

def combination(N,K):
  if N < K:
    return 0
  elif K == 0:
    return 0
  elif K == 1:
    return N
  elif K == 2:
    return N*(N-1)//2
  else:
    return N*(N-1)*(N-3)//6

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += nine[j]*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*nine[j-1] + ans[j-1]
    ans = a
print(ans[K])

Submission status: Wrong Answer

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

if int(N) < K:
  print(0)
  exit()

keta = []
for k in range(len(N)):
  keta.append(int(N[-k-1]))
ans = [1, keta[0], 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p
for k in range(1, len(N)-1):
  if keta[k] > 0:
    a = [1, 0, 0, 0]
    for j in range(1, 4):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (keta[k]-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = [] + a
answer = (9**(K))*combination(len(N)-1, K)
answer += (keta[-1]-1)*(9**(K-1))*combination(len(N)-1, K-1)
answer += ans[K-1]
print(answer)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
keta = []
for k in range(len(N)):
  keta.append(int(N[-k-1]))
ans = [1, keta[0], 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p
for k in range(1, len(N)-1):
  if keta[k] > 0:
    a = [1, 0, 0, 0]
    for j in range(1, 4):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (keta[k]-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = [] + a
answer = (9**(K))*combination(len(N)-1, K)
answer += (keta[-1]-1)*(9**(K-1))*combination(len(N)-1, K-1)
answer += ans[K-1]
print(answer)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
keta = []
for k in range(len(N)):
  keta.append(int(N[-k-1]))
ans = [1, keta[0], 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p
for k in range(1, len(N)-1):
  if keta[k] > 0:
    a = [] + ans
    for j in range(1, 4):
      a[j] += (keta[k]-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = [] + a
answer = (9**(K))*combination(len(N)-1, K)
answer += (keta[-1]-1)*(9**(K-1))*combination(len(N)-1, K-1)
answer += ans[K-1]
print(answer)

Submission status: Wrong Answer

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

def keta(n):
    number = 0
    while(n>0):
        number += 1
        n = n //10
    return number

def k1(n):
    number = keta(n)
    sum = n // (10**(number-1))
    for i in range(number - 1):
        sum += 9
    return sum

def k2(n):
    number = keta(n)
    if number < 2:
        return 0
    first_digit = n // (10**(number-1))
    second_digit = (n%(10**(number-1))) // (10**(number-2))
    #最上桁がそのままの数のとき.ex.250なら210,220,230,240,250
    sum = k1(second_digit) + (first_digit - 1) * 9
    #ex.250なら201,202,...209
    #ex.2500なら2010,...2090,2001,2002,...2009
    sum += first_digit * 9 * (number - 2)
    #上位桁を0で埋めていく場合.ex.250なら11,12,...99
    sum += 9 * 9 * (number - 1) * (number - 2) //2
    return sum

def k3(n):
    number = keta(n)
    if number < 3:
        return 0
    first_digit = n // (10**(number-1))
    #print(first_digit)
    #最上桁を除いたn
    new_n = n - first_digit * (10**(number-1))
    #print(new_n)
    #最上桁そのままの場合
    sum = k2(new_n)
    #print(sum)
    #最上桁を変化させていった場合
    sum += (first_digit - 1) * 9 * 9 * (number - 1) * (number - 2) // 2
    #print(sum)
    #上位桁を0で埋めていく場合
    sum += 9 * 9 * 9 * (number - 1) * (number - 2) * (number - 3) // 6
    #print(sum)
    return sum
    
if k == 1:
    print(k1(n))

elif k == 2:
    print(k2(n))

elif k == 3:
    print(k3(n))

Submission status: Wrong Answer

Solution code:

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

def keta(n):
    number = 0
    while(n>0):
        number += 1
        n = n //10
    return number

def k1(n):
    number = keta(n)
    sum = n // (10**(number-1))
    for i in range(number - 1):
        sum += 9
    return sum

def k2(n):
    number = keta(n)
    if number < 2:
        return 0
    first_digit = n // (10**(number-1))
    second_digit = (n%(10**(number-1))) // (10**(number-2))
    #最上桁がそのままの数のとき.ex.250なら210,220,230,240,250
    sum = k1(second_digit) + (first_digit - 1) * 9
    #ex.250なら201,202,...209
    #ex.2500なら2010,...2090,2001,2002,...2009
    sum += first_digit * 9 * (number - 2)
    #上位桁を0で埋めていく場合.ex.250なら11,12,...99
    sum += 9 * 9 * (number - 1) * (number - 2) //2
    return sum

def k3(n):
    number = keta(n)
    if number < 3:
        return 0
    first_digit = n // (10**(number-1))
    print(first_digit)
    #最上桁を除いたn
    new_n = n - first_digit * (10**(number-1))
    print(new_n)
    #最上桁そのままの場合
    sum = k2(new_n)
    print(sum)
    #最上桁を変化させていった場合
    sum += (first_digit - 1) * 9 * 9 * (number - 1) * (number - 2) // 2
    print(sum)
    #上位桁を0で埋めていく場合
    sum += 9 * 9 * 9 * (number - 1) * (number - 2) * (number - 3) // 6
    print(sum)
    return sum
    
if k == 1:
    print(k1(n))

elif k == 2:
    print(k2(n))

elif k == 3:
    print(k3(n))

Submission status: Wrong Answer

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

def keta(n):
    number = 0
    while(n>0):
        number += 1
        n = n //10
    return number

def k1(n):
    number = keta(n)
    sum = n // (10**(number-1))
    for i in range(number - 1):
        sum += 9
    return sum

def k2(n):
    number = keta(n)
    first_digit = n // (10**(number-1))
    second_digit = (n%(10**(number-1))) // (10**(number-2))
    #最上桁がそのままの数のとき.ex.250なら210,220,230,240,250
    sum = k1(second_digit) + (first_digit - 1) * 9
    #ex.250なら201,202,...209
    #ex.2500なら2010,...2090,2001,2002,...2009
    sum += first_digit * 9 * (number - 2)
    #上位桁を0で埋めていく場合.ex.250なら11,12,...99
    sum += 9 * 9 * (number - 1) * (number - 2) //2
    return sum

def k3(n):
    number = keta(n)
    first_digit = n // (10**(number-1))
    second_digit = (n%(10**(number-1))) // (10**(number-2))
    third_digit = (n%(10**(number-2))) // (10**(number-3))
    #最上桁を除いたn
    new_n = n - first_digit * (10**(number-1))
    #最上桁そのままの場合
    sum = k2(new_n)
    #最上桁を変化させていった場合
    sum += (first_digit - 1) * 9 * 9 * (number - 1) * (number - 2) // 2
    #上位桁を0で埋めていく場合
    sum += 9 * 9 * 9 * (number - 1) * (number - 2) * (number - 3) // 6
    return sum
    
if k == 1:
    print(k1(n))

elif k == 2:
    print(k2(n))

elif k == 3:
    print(k3(n))

Submission status: Wrong Answer

Solution code:
def solve():
    s = [int(x) for x in input()]
    n = len(s)
    s.append(0)
    m = int(input())
    dp = [[[0] * (m + 1) for _ in range(2)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][1][0] = 1
    for i in range(m):
        dp[i][0][i + 1] = 1
    dp[0][1][1] = s[0] - 1

    for i in range(n):
        for j in range(2):
            for k in range(m):
                if j:
                    dp[i + 1][j][k + 1] = dp[i][0][k] * (s[i + 1] - 1) + dp[i][0][k + 1] + dp[i][1][k] * 9 + dp[i][1][k + 1]
    print(dp[n - 1][1][k + 1] + dp[n - 1][0][k + 1])


solve()

Submission status: Wrong Answer

Solution code:
from math import factorial
from itertools import product

S = input()
N = int(S)
m = len(S)
K = int(input())
# 0でない数字がちょうどK個でK桁のものを数える
product_K = product(['1', '2', '3', '4', '5', '6', '7', '8', '9'], repeat=K)
product_K = [int(''.join(x)) for x in product_K]
ans = len([x for x in product_K if x <= N])
# K+1桁からlen(N)-1桁までを数える
if m > K:
    for i in range(1, m-K):
        ans += 9**K * factorial(i+K-1)//factorial(i)//factorial(K-1)
        # print(factorial(i+K)//factorial(i)//factorial(K))
    # Nと同じ桁数で条件を満たすものを数える
    zero_n = m-K
    non_zero_n = K
    i = 0
    while non_zero_n*zero_n > 0:
        l = int(S[i])
        if l == 0:
            zero_n -= 1
            continue
        if non_zero_n < K:
            ans += 9**non_zero_n\
                * factorial(zero_n-1 + non_zero_n)\
                //factorial(zero_n-1)\
                //factorial(non_zero_n)
        non_zero_n -= 1
        ans += len([x for x in range(1, l)])\
                * 9**non_zero_n\
                * factorial(zero_n + non_zero_n)\
                //factorial(zero_n)\
                //factorial(non_zero_n)
        i += 1
    ans += 1
print(ans)

Submission status: Wrong Answer

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

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

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






if __name__ == '__main__':
    main()