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:
def countInRangeUtil(pos, cnt, tight, num): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt <= K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x): 
    global dp, K, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  
dp = [] 
M = 150

K = 0

L = 1
R = int(input())
K = int(input())
print(countInRange(R) - countInRange(L - 1))

Submission status: Wrong Answer

Solution code:
import sys

N = input()
K = int(input())
L = len(N)

if L < K:
	print(0)
	sys.exit()

ans = 0
if K == 3:
	# K=1
	tmp = str(int(N[2:]))
	ans += int(tmp[0])
	ans += (max(0,len(tmp)-1)) * 9

	#K=2
	ans += (max(0,int(N[1])-1))*(L-2)*9
	if int(N[1]) > 0:
		ans += ((L-2)*(L-3)//2) * 9 * 9

	#K=3
	ans += ((int(N[0]))-1) * ((L-1) * (L-2) // 2) * 9 * 9
	ans += ((L-1)*(L-2)*(L-3)//6) * 9 * 9 * 9

elif K == 2:
	tmp = str(int(N[1:]))
	ans += int(tmp[0])
	ans += (len(tmp)-1)*9

	ans += (int(N[0])-1) * (L-1) * 9
	ans += ((L-1) * (L-2) // 2) * 9 * 9

elif K == 1:
	ans += int(N[0])
	ans += (L-1) * 9
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
K = int(input())
strN = str(N)
lenn = len(strN)
if K == 1:
    print((lenn-1)*9 + int(strN[0]))
elif K == 2:
    if lenn == 1:
        print(0)
    else:
        ans1 = 81*comb(lenn-1,2)
        ans1 += (int(strN[0])-1)*9*(lenn-1)
        for i in range(1,lenn):
            if int(strN[i]) != 0:
                ans1 += int(strN[i])
                ans1 += 9*(lenn-i-1)
                break
        print(ans1)
else:
    if lenn <= 2:
        print(0)
    else:
        ans1 = (9**3)*comb(lenn-1,3)
        ans1 += (int(strN[0])-1)*81*comb(lenn-1,2)
        strN = strN[1:]
        lenn = len(strN)
        if lenn == 1:
            ans2 = 0
        else:
            ans2 = 81*comb(lenn-1,2)
            ans2 += (int(strN[0])-1)*9*(lenn-1)
            for i in range(1,lenn):
                if int(strN[i]) != 0:
                    ans2 += int(strN[i])
                    ans2 += 9*(lenn-i-1)
                    break
        print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
from math import factorial
N = int(input())
K = int(input())


def n_C_k(n, k):
    factorial_n = factorial(n)
    factorial_k = factorial(k)
    factorial_nk = factorial(n-k)
    return factorial_n//(factorial_k*factorial_nk)

def solve(N, k):
    #ls = list(str(N))
    n = str(N)
    keta = len(n)

    if k == 0 or keta < k:
        return 0
    t = n[0]
    s = ""

    for i in range(keta-1):
        t += "0"
    for i in range(keta-1):
        s += n[i+1]
    return solve2(t, k) + solve(s, k-1)

def solve2(t, k):
    n = str(t)
    keta = len(n)
    if k == 1:
        #print(t, k)
        #print((keta-1)*9+int(n[0]))
        return (keta-1)*9+int(n[0])
    if k == 2:
        out = 0
        out += (int(n[0])-1)*(keta-1)*9 #最上桁を使う場合
        if keta-1 >= 2:
            out += n_C_k(keta-1, 2)*9*9  # 最上桁を使わない場合
        #print(t, k)
        #print(out)
        return out
    else:
        out = 0
        if keta-1 >= 2:
            out += (int(n[0])-1)*n_C_k(keta-1, 2)*9*9
        if keta-1 >= 3:
            out += n_C_k(keta-1, 3)*9*9*9
        return out

    
ans = solve(N, K)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,k = get_all_int()

# m桁の数値でf(n)=kとなる数の個数
# dp[k][m]
dp = [ [None]*101 for _ in range(4)]

for i in range(101):
    dp[0][i] = 1
dp[0][0] = 0
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0
dp[1][1] = 9
dp[2][1] = 0
dp[3][1] = 0

dp[1][2] = 1 * dp[1][1] + 9 * dp[0][1]
for i in range(2,101):
    dp[1][i] = 1 * dp[1][i-1] + 9 * dp[0][i-1]
    dp[2][i] = 1 * dp[2][i-1] + 9 * dp[1][i-1]
    dp[3][i] = 1 * dp[3][i-1] + 9 * dp[2][i-1]

# log(dp[1])
# log(dp[2])

ans = 0

keta = 0
x = n
while x > 0:
    keta += 1
    x //= 10

def sol(n, keta, k):
    if k == 0:
        return 1
    if k < 0:
        return 0
    if keta < k:
        return 0
    if keta == 0:
        return 1
    
    top = n//10**(keta-1)%10
    if keta==1:
        return top
    ans = 0
    # 0のとき
    ans += 1 * (0 if keta==1 else dp[k][keta-1])
    # ans += sol(n, keta-1, k)
    # log(keta,top,k,ans)

    # 1～top-1のとき
    if top != 0:
        ans += (top-1) * (1 if keta==1 else dp[k-1][keta-1])
        # ans += (top-1) * sol(n, keta-1, k-1)
    # log(keta,top,k,ans)

    # topのとき
    if top != 0:
        ans += sol(n, keta-1, k-1)
    # log(keta,top,k,ans)
    return ans

if keta < k:
    print(0)
    exit()
ans += sol(n, keta, k)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n_str = input()
    k = int(input())
    keta = len(n_str)

    def k1():
        ans = keta*9 - (9-int(n_str[0]))
        print(ans)

    def k2():
        if keta <= 2 and int(n_str) <= 10:
            print(0)
            return

        ans = (
            (keta*(keta-1)//2) * 9**2
            - (9-int(n_str[0])) * (keta-1) * 9
            - (9-int(n_str[1]))
        )
        print(ans)

    def k3():
        if keta <= 3 and int(n_str) <= 110:
            print(0)
            return

        ans = (
            (keta*(keta-1)*(keta-2)//6) * 9**3
            - (9-int(n_str[0])) * ((keta-1)*(keta-2)//2) * 9**2
            - (9-int(n_str[1])) * (keta-2) * 9
            - (9-int(n_str[2]))
        )
        print(ans)

    if k == 1:
        k1()
    elif k == 2:
        k2()
    else:
        k3()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
K = int(input())
strN = str(N)
lenn = len(strN)
if K == 1:
    print((lenn-1)*9 + int(strN[0]))
elif K == 2:
    if lenn == 1:
        print(0)
    else:
        ans1 = 81*comb(lenn-1,2)
        ans1 += (int(strN[0])-1)*9*(lenn-1)
        for i in range(1,lenn):
            if int(strN[i]) != 0:
                ans1 += int(strN[i])
                ans1 += 9*(lenn-i-1)
                break
        print(ans1)
else:
    if lenn <= 2:
        print(0)
    else:
        ans1 = (9**3)*comb(lenn-1,3)
        ans1 += (int(strN[0])-1)*81*comb(lenn-1,2)
        strN = strN[1:]
        lenn = len(strN)
        ans2 = 81*comb(lenn-1,2)
        ans2 += (int(strN[0])-1)*9*(lenn-1)
        for i in range(1,lenn):
            if int(strN[i]) != 0:
                ans2 += int(strN[i])
                ans2 += 9*(lenn-i-1)
                break
        print(ans1+ans2)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
tmpn=int(str(n)[:k]+("0"*(len(str(n))-k)))
# print(tmpn)
if k==2 and n<11:
    print(0)
    quit()
if k==3 and n<111:
    print(0)
    quit()
nonzero=[]
cnt=0
for i in range(keta):
    if str(n)[i]!="0":
        nonzero.append([int(str(n)[i]),keta-i])
        cnt+=1
    if cnt==k:
        break
# print(nonzero)
    

ans=0
def combinations_count(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if k==1:
    ans+=int(str(n)[0])
    ans+=(keta-1)*9
if k==2:
    if len(nonzero)==2:
        ans+=nonzero[1][0]+(int(str(n)[0])-1)*9
        ans+=int(str(n)[0])*(nonzero[1][1]-1)*9
        ans+=combinations_count(keta-1,k)*81
    else:
        ans+=combinations_count(keta-1,k)*81
if k==3:
    if len(nonzero)==3:
        ans+=nonzero[2][0]+(nonzero[1][0]-1)*9+(int(str(n)[0])-1)*81
        ans+=int(str(n)[0])*nonzero[1][0]*(nonzero[2][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[2][1],2)*81
        ans+=combinations_count(keta-1,k)*81*9
    elif len(nonzero)==2:
        ans+=int(str(n)[0])*(nonzero[1][0]-1)*(nonzero[1][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[1][1]-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
    else:
        ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=input()#as string
k=int(input())

e=9**k
f=len(n)
ans=0

zeroexist=True#途中桁に0が存在するかどうか

#kの範囲が極めて狭いので愚直に行く
if k==1:
    for i in range(f):
        if i==0:
            ans+=int(n[i])
        else:
            ans+=e
elif k==2:
    for i in range(f):
        for j in range(i+1,f):
            if i==0:
                ans+=(int(n[i])-1)*9
                if j==1:
                    ans+=int(n[j])
                    if int(n[j])!=0:
                        zeroexist=False
                else:
                    if zeroexist and int(n[j])!=0:
                        zeroexist=False
                    
                    if zeroexist:
                        ans+=int(n[j])
                    else:
                        ans+=9
            else:
                ans+=e
            
else:
    for i in range(f):
        for j in range(i+1,f):
            for k in range(j+1,f):
                if i==0:
                    ans+=(int(n[i])-1)*9*9
                    if j==1:
                        ans+=int(n[j])*9
                        if int(n[j])!=0:
                            zeroexist=False
                    else:
                        if zeroexist and int(n[j])!=0:
                            zeroexist=False
                        
                        if zeroexist:
                            ans+=(int(n[j])-1)*9+int(n[k])
                        else:
                            ans+=9*9
                else:
                    ans+=e
print(ans)

Submission status: Wrong Answer

Solution code:
strN = input()
N = int(strN)
K = int(input())
ans = 0
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    lenN = len(strN)
    if N > 10:
        ans += int(strN[1])
        ans += (int(strN[0]) - 1) * 9
        ans += int(strN[0]) * 9 * (lenN - 2)
        for j in range(1, lenN - 1):
            ans += 9 * 9 * (lenN - j - 1)

        # if lenN >= 3:
        #    ans += (lenN - 2) * 9
        #now_pattern = int(strN[0])
        # for j in range(1, lenN):
        #    ans += now_pattern * (9 ** (lenN - j - 1))
        #    now_pattern *= int(strN[j])

else:
    lenN = len(strN)
    if N > 110:
        ans += int(strN[2])
        if int(strN[1]) != 0:
            ans += (int(strN[1])-2)*9
        ans += (int(strN[0]) - 1) * 9*9*(((lenN-1)*(lenN-2))//2)
        for h in range(1, lenN - 2):
            ans += 9 * 9 * 9*(((lenN-1-h)*(lenN-2-h))//2)
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

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

M = int(input())
N = list(str(M))
K = int(input())

keta = len(N)
if K == 1:
    ans = 9*(keta-1)+int(N[0])
elif K == 2:
    if keta > 2:
        ans = cmb(keta-1,2)*81+max(0,int(N[0])-1)*9*(keta-1)+int(N[1])
        if int(N[1]) != 0:
            ans += 9*(keta-2)
    else:
        ans = 0
        for i in range(11,M+1):
            if '0' not in str(i):
                 ans += 1
else:
    if keta > 3:
        ans = cmb(keta-1,3)*729+(int(N[0])-1)*81*cmb(keta-1,2)+max(0,int(N[1])-1)*(keta-2)*9
        if int(N[1]) != 0:
            ans += cmb(keta-2,2)*81+int(N[2])
        if int(N[2]) != 0:
            ans += 9*(keta-3)
    else:
        ans = 0
        for i in range(111,M+1):
            if '0' not in str(i):
                ans += 1

print(int(ans))

Submission status: Wrong Answer

Solution code:
import itertools

N = input()
K = int(input())
lN = len(N)


if K == 1:
    ans = int(N[0])+9*(lN-1)
    print(ans)

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 == v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[not0])
            elif not0 < v[1]:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*max(0,int(N[not0f])-1)*9 + int(N[not0s])
                elif not0s < v[2]:
                    ans += int(N[0])*int(N[not0f])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
n = N - 1
l = len(str(n))
cnt = 0


def cng(s):
    x = list(str(N))
    c = 0
    for i in x:
        if int(i) != 0:
            c += 1
    return s == c


if K == 1:
    if N < 1:
        cnt = 0
    else:
        cnt = 9 * (l - 1) + n // (10 ** (l - 1))
    if cng(1):
        cnt += 1
elif K == 2:
    if N < 11:
        cnt = 0
    else:
        a = int(str(n)[0])
        b = int(str(n)[1])
        cnt = 81 * ((l - 1) * (l - 2) // 2) + 9 * a * (l - 2) + (a - 1) * 9 + b
    if cng(2):
        cnt += 1
else:
    if N < 111:
        cnt = 0
    else:
        a = int(str(n)[0])
        b = int(str(n)[1])
        c = int(str(n)[2])
        cnt = (9 ** 3 * ((l - 1) * (l - 2) * (l - 3) // 6)
               + a * 9 * 9 * ((l - 2) * (l - 3) // 2)
               + (a - 1) * 9 * 9 * (l - 2)
               + (b - 1) * 9 * (l - 2) + 9 * (l - 3) + c)
    if cng(3):
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
ans = 0
while N!=0:
    n = str(N)
    if len(n)<K:break

    if n[1:].count("9")==len(n)-1:
        if K==1:ans+=int(n[0])
        elif K==2:
            for i in range(1,len(n)):
                ans+=int(n[0])*9
        else:
            for i in range(1,len(n)-1):
                for j in range(i+1,len(n)):
                    ans+=int(n[0])*9*9
    else:
        if K==1:ans+=1
        elif K==2:
            k = 0
            for i in range(1,len(n)):
                if k==0:
                    ans += int(n[i])
                    if n[i]!="0":k=1
                else:
                    ans+=9
        else:
            for i in range(1,len(n)-1):
                for j in range(2,len(n)):
                    ans += int(n[i])*9
    if len(n)==1:N = 0
    elif n[1:].count("9")==len(n)-1:N = 10**(len(n)-1)-1
    else:N = int(n[0])*(10**(len(n)-1))-1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools

str_N = input()
K = int(input())
N = int(str_N)
zero_num = len(str_N)-K

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def count():
    c = 0
    top = int(str_N[0])
    if K==3:
        for one in itertools.combinations(list(range(1,len(str_N))), K-1):
            a,b = one
            if a==1:
                if int(str_N[a])==0:
                    c+=0
                else:
                    c += (top-1)*int(str_N[a])*9+(int(str_N[a])-1)*9+int(str_N[b])
            else:
                c += top*9*9
            
    elif K==2:
        for one in range(1, len(str_N)):
            if one==1:
                c += (top-1)*9+int(str_N[one])
            else:
                c += top*9
    elif K==1:
        c+=top
    return c

ans = 0
if len(str_N)<K:
    ans = 0
elif len(str_N)==K:
    ans += count()
else:
    if len(str_N)==1:
        ans += N
    else:
        ans += combinations_count(len(str_N)-1, K)*(9**K)
        ans += count()
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
K = int(input())
def one(N):
    n = list(str(N))
    A = (len(n)-1)*9
    A += int(n[0])
    return A

def two(N):
    n = list(str(N))
    r = len(n)
    A = (int(n[0])-1)*(r-1)*9 #r-1C1*9
    A = A + (r-2)*(r-1)*81/2  #r-1C2*81
    A = A + one(N%(10**(r-1)))
    return(A)

if K==1:
    print(one(N))

elif K==2:
    print(two(N))

elif K==3:
    n = list(str(N))
    r = len(n)
    A = two(10**(r-1)-1)*(int(n[0])-1)
    A = A + two(N%(10**(r-1)))
    A = A + (r-2)*(r-1)*(r-3)*81*9/6
    print(A)

Submission status: Wrong Answer

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

# 桁数調べる
# tmp = N
# digit = 1
# while tmp >= 10:
#     tmp //= 10
#     digit += 1
# print(digit)

if K > len(str(N)):
    print(0)
    exit()

if K == 1:  # done
    N = str(N)
    ans = (len(N)-1) * 9
    ans += int(N[0])
    print(ans)

elif K == 2:
    N = str(N)
    # 最上位を避けた, (n-1)C2 * 9の二乗
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    # 最上位の桁2つのみ, 最上位がN[0]のパターン, N[0]の1通りと, N[1]通り
    ans += 1 * int(N[1])
    # 最上位の桁2つののみ, 最上位!=N[0]のパターン
    ans += (int(N[0])-1) * 9
    # 最上位とその他(二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    # 最上位を避けた選び方, n-1C3 * 9の三乗
    ans = (len(N)-1) * (len(N)-2) * (len(N)-3) * 9 * 9 * 9 // 6
    # 上位二桁とその他, 最上位がN[0]の場合
    ans += 1 * int(N[1]) * (len(N)-2) * 9
    # 上位二桁とその他, 最上位!=N[0]の場合, int(N[0])-1なのはN[0]のパターンを除くため
    ans += (int(N[0])-1) * 9 * (len(N)-2)*9
    # 最上位とその他 (二桁目は選ばない)
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) * 9 * 9 // 2
    print(-1)

Submission status: Wrong Answer

Solution code:
N=input()
K=input()
a=1
a1=1
a2=1
c=0
ans=0
while (a<=int(N)):
  a1=a
  while (c>=(len(str(N))-1)):
    a1=str(a1).rstrip("0")
    c=c+1
  L=len(str(a1))
  a=int(a)+1
  if(int(L)==int(K)):
    ans=ans+1
print(ans)
print(len(str(N))-1)

Submission status: Wrong Answer

Solution code:
import math
n=input()#as string
k=int(input())

e=9**k
f=len(n)
ans=0

zeroexist=True#途中桁に0が存在するかどうか

#kの範囲が極めて狭いので愚直に行く
if k==1:
    for i in range(f):
        if i==0:
            ans+=int(n[i])
        else:
            ans+=e
elif k==2:
    for i in range(f):
        for j in range(i+1,f):
            if i==0:
                ans+=(int(n[i])-1)*9
                if j==1:
                    ans+=int(n[j])
                    if int(n[j])!=0:
                        zeroexist=False
                else:
                    if zeroexist and int(n[j])!=0:
                        zeroexist=False
                    
                    if zeroexist:
                        ans+=int(n[j])
                    else:
                        ans+=9
            else:
                ans+=e
            
else:
    for i in range(f):
        for j in range(i+1,f):
            for k in range(j+1,f):
                if i==0:
                    ans+=(int(n[i])-1)*9*9
                    if j==1:
                        ans+=int(n[j])*9
                        if int(n[j])!=0:
                            zeroexist=False
                    else:
                        if zeroexist and int(n[j])!=0:
                            zeroexist=False
                        
                        if zeroexist:
                            ans+=int(n[j])*k
                        else:
                            ans+=9*9
                else:
                    ans+=e
print(ans)

Submission status: Wrong Answer

Solution code:
#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

#選び方（コンビネーション nCr）
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


n_given = input_one_number()
k_given = input_one_number()

ans = 0
ndigits = len(str(n_given))
if k_given == 1:
    msd = n_given
    while msd >= 10:
        msd //=10

    ans = (ndigits-1)*9+msd

elif k_given == 2:
    if ndigits < 2:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 100:
            msd1 //=10
        msd2 = msd1%10
        msd1 = msd1//10

        if(ndigits > 2):
            ans += cmb(ndigits-1,2)*pow(9,2)
        ans += (msd1-1)*(ndigits-1)*9
        ans += (ndigits-2)*9+msd2

else:
    if ndigits < 3:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 1000:
            msd1 //=10
        msd3 = msd1%10
        msd1 = msd1//10
        msd2 = msd1%10
        msd1 = msd1//10
        
        if(ndigits > 3):
            ans += cmb(ndigits-1,3)*pow(9,3)
        if(ndigits > 3):
            ans += cmb(ndigits-2,2)*pow(9,2)*(msd1)
        if(ndigits > 3):
            ans += (ndigits-3)*msd1*msd2*9
        ans += (msd1-1) * 81 + msd2*msd3

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input()) # 数字を変数に格納
K = int(input()) # 数字を変数に格納

num = len(str(N))
n = str(N)
List = [[0,0],[0,0],[0,0]]
count = 0

for i in range(num):
    if n[i] != '0':
        List[count][0] = int(n[i])
        List[count][1] = num - i
        count += 1
        if count == 3:
            break

result = 0

if K == 1:
    result += List[0][0] + (List[0][1] - 1) * 9
elif K == 2:
    if N <= 10:
        result = 0
    else:
        result += List[1][0] + (List[1][1] - 1) * 9 # 最高桁数固定
        result += (List[0][0] - 1) * (List[0][1] - 1) * 9 # 最高桁数が上記以外
        result += 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) / 2 # 最高桁数が0
elif K == 3:
    if N <= 110:
        result = 0
    else:
        result += List[2][0] + (List[2][1] - 1) * 9 # 最高1桁2桁固定
        result += (List[1][0] - 1) * (List[1][1] - 1) * 9 # 最高1桁固定2桁が上記以外
        result += 9 * 9 * (List[1][1] - 1) * (List[1][1] - 2) / 2 # 最高1桁固定2桁が0
        result += (List[0][0] - 1) * 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) / 2 # 最高1桁が上記以外
        result += 9 * 9 * 9 * (List[0][1] - 1) * (List[0][1] - 2) * (List[0][1] - 3) / 3 / 2 # 最高1桁が0

print(int(result))

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
w=[int(i) for i in str(n)]
x=len(w)
ans=chk=0
if n<10000:
    for i in range(1,n+1):
        chk=0
        p=i
        while p>0:
            if p%10>0:
                chk+=1
            p//=10
        ans += chk==k
    print(ans)
    exit()
if k==3:
    for a in range(x-2):
        e=1
        for b in range(a+1,x-1):
            f=1
            for c in range(b+1,x):
                if a==0 and (b==1 or e==1) and (c==2 or f==1):
                    ans+=(w[a]-1)*w[b]*9
                    ans+=1*(w[b]-1)*9
                    ans+=1*1*w[c]
                    if f and w[c]!=0:
                        f=0
                else:
                    ans+=9**3
        if e==1 and w[b]!=0:
            e=0
elif k==2:
    for a in range(x-1):
        for b in range(a+1,x):
            if a==0 and b==1:
                ans+=(w[a]-1)*9
                ans+=1*w[b]
            elif a==0:
                ans+=w[a]*9
            else:
                ans+=9**2
else:
    ans=w[0]*(9**(x-1))
print(ans)

Submission status: Wrong Answer

Solution code:
def cmb(a,b):
    if b == 0 :
        ans=1
    else:
        Nu = 1
        Di = 1
        for i in range(b):
            Nu = Nu*(a-i)
            Di = Di*(b-i)
        ans = Nu/Di
    return ans


def f(a,keta,K):
    ans = cmb(keta,K)*9**K
    if K == 1:
        ans += a
    else:
        ans += cmb(keta, K-1)*9**(K-1)*(a-1)
    return ans



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

    ans = 0
    while K>0 and N>0:
        keta = len(str(N))-1
        if keta + 1 < K: break
        if keta == 0:
            if K==1 :ans += N
        a = int(N/(10**(keta)))
        ans += f(a,keta,K)
        N -= a*10**keta
        K -= 1
        print(a,keta,ans)
    print(int(ans))
    return

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
# import itertools
N = int(input())
K = int(input())

L = list(str(N))
leng = len(L)
st = int(L[0])
cnt = 0

#N(3003)と左桁数(0)をもらってOKな桁数(3)とその数値を返す
def keta(n,l):
    for i in range(l,leng):
        d = n[i]
        if d=='0':
            continue
        else:
            return (i,int(d))
    return -1,-1

if K==1:
    cnt += 1
    cnt += 9*(leng-1)
elif K==2:
    i,d = keta(L,1)
    if not i==-1:
        cnt += d + 9*(leng-i-1)

    cnt += (st-1)*9*(leng-1) + 9*9*(leng-1)*(leng-2)//2
else:
    i_1,d_1 = keta(L,1)
    i_2,d_2 = keta(L,i_1+1)
    if not i_1==-1:
        a = (leng-i_1-1)
        cnt += (d_1-1)*9*a
        cnt += 9*9*(a*(a-1)//2)
    if not i_2==-1:
        cnt += d_2 + 9*(leng-i_2-1)
    cnt += (st-1)*9*9*(leng-1)*(leng-2)//2 + (9**3)*(leng-1)*(leng-2)*(leng-3)//6
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()
S = str(N)

def calc1(S):
    if len(S)<1:
        return 0
    flag = False
    ans = 0
    for s in S:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    return ans

def calc2(S):
    bl = len(S)
    ans = 0
    if bl<2:
        return 0
    # 最上位bitに0
    ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    if int(S[0])>=1:
        ans += (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    if bl==2 and S[0]=='0':
        pass
    else:
        ans += calc1(S[1:])
    return ans

def calc3(S):
    bl = len(S)
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=3:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    if bl>=3:
        if bl==3 and S[0]=='0':
            pass
        else:
            ans += calc2(S[1:])
    return ans

if K==1:
    print(calc1(S))
if K==2:
    print(calc2(S))
if K==3:
    print(calc3(S))

Submission status: Wrong Answer

Solution code:
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod



N = int(input())
K = int(input())
SN = str(N)
LN = list(SN)
keta =len(LN)
Nzer = keta-K
Nsei = K
output = 0
if keta>=K:
    output += comb(keta,K,10**9+7)*9**K
    t = 0
    while K-1-t>=0:
        output -= (9-int(LN[t]))*comb(keta-1-t,K-1-t,10**9+7)*9**(K-1-t)
        t += 1
print(output)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

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

M = int(input())
N = list(str(M))
K = int(input())

keta = len(N)
if K == 1:
    ans = 9*(keta-1)+int(N[0])
elif K == 2:
    if keta > 2:
        ans = cmb(keta-1,2)*81+(int(N[0])-1)*9*(keta-1)+int(N[1])+9*(keta-2)
    else:
        ans = 0
        for i in range(11,M+1):
            if '0' not in str(i):
                 ans += 1
else:
    if keta > 3:
        ans = cmb(keta-1,3)*729+(int(N[0])-1)*81*cmb(keta-1,2)+max(0,(int(N[1])-1))*(keta-2)*9+cmb(keta-2,2)*81+int(N[2])+9*(keta-3)
    else:
        ans = 0
        for i in range(111,M+1):
            if '0' not in str(i):
                ans += 1

print(int(ans))