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 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)+(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))

Submission status: Wrong Answer

Solution code:
N = input()
K = input()
A = len(N)
NOB = True
if A == 1 and (K == '2' or K == '3'):
	print(0)
elif K == '1':
	print(9*(A-1)+ord(N[0])-ord('0'))
elif K == '2':
	for i in range(1,A):
		if N[i] != '0':
			NOB = False
			break
	print((81*(A-1)*(A-2))//2 + (ord(N[0])-ord('1'))*9*(A-1) + ord(N[i])- ord('0') + 9*(A-1-i))
else:
	for i in range(1,A):
		if N[i] != '0':
			NOB = False
			break
	print(((A-1)*(A-2)*(A-3)*729)//6 + ((ord(N[0])-ord('1'))*81*(A-1)*(A-2))//2 + (ord(N[i])-ord('1'))*(A-i-1)*9 + (((A-1-i)*(A-2-i))//2)*81 + (A-i-1)*9)

Submission status: Wrong Answer

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

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

if K == 2:
    if len(N) < 2:
        print(0)
        exit()
    c = 0
    if N[0] == 1:
        d = 0
        d += int(N[1])
        d += (len(N) - 2) * 9
        d += int((len(N) - 1) * (len(N) - 2) / 2 * 81)
        print(d)
    else:
        d = 0
        d += int(N[1])
        d += (len(N) - 2) * 9
        d += (len(N) - 1) * 9 * (int(N[0]) - 1)
        d += int((len(N) - 1) * (len(N) - 2) / 2 * 81)
        print(d)

if K == 3:
    pass

Submission status: Wrong Answer

Solution code:
''' بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ '''
#codeforces
gi = lambda : list(map(int,input().split()))
s = input()
n, = gi()
ans = 0
mag = len(s) - 1
#corner cases:
if len(s) <= 3:
	s = int(s)
	for k in range(s + 1):
		if len(str(k)) - str(k).count("0") == n:
			ans += 1
	print(ans)
	exit()
while mag - n >= 0:
	a = 9
	b = 1
	c = 1
	if n > 2:
		c = 81 * ((mag - 1) * (mag - 2) // 2)
	elif n > 1:
		b = 9 * (mag - 1)
	ans += a * b * c
	#print(mag, a, b, c, ans)
	mag -= 1
mag = len(s)
a = int(s[0]) - 1
b, c = 1, 1
if n > 2:
	c = 81 * ((mag - 1) * (mag - 2) // 2)
elif n > 1:
	b = 9 * (mag - 1)
ans += a * b * c
a = b = c = 1
if n == 1:
	print(ans + 1)
	exit()
if n > 1:
	i = -1
	for k in range(1, len(s)):
		if s[k] != "0":
			i = k
			break;
	if i != -1:
		a = int(s[i]) - 1
		if n > 2:
			b = len(s) - i - 1
			b *= 9
		ans += a * b
		a = b = 1
		if n > 2:
			x = len(s) - i - 1
			a = 81 * (x * (x - 1)) // 2
		else:
			a = 9 * (len(s) - i - 1)
		ans += a
	if n > 2:
		a = b = c = 1
		j = -1
		for k in range(i + 1, len(s)):
			if s[k] != "0":
				j = k
				break;
		if j != -1:
			ans += 9 * (len(s) - j - 1) + int(s[j])
	else:
		ans += 1
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 == 0:
        return 1
    
    top = n//10**(keta-1)%10
    ans = 0
    # 0のとき
    ans += 1 * (0 if keta==1 else dp[k][keta-1])
    # log(keta,top,k,ans)

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

    # topのとき
    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:
n = int(raw_input())
k = int(raw_input())
if(k == 1):
    print(1)
else:
    if(k == 2):
        print(11)
    else:
        if(k == 3):
            print(111)

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):
    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
    # 最上位bitに0
    if bl>=2:
        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:
        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>=2:
        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:
n = int(input())
k = int(input())

def solve(n,k):
    if n<10**5:
        ans=0
        for num in range(1,n+1):
            cnt=0
            for char in str(num):
                if char!="0":
                    cnt+=1
            if cnt==k:
                ans+=1
        return ans

    keta = len(str(n))

    if k==1:
        return int(str(n)[0]) + 9*(keta-1)


print(solve(n,k))

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):
    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
    # 最上位bitに0
    if bl>=2:
        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:
        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>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    if bl>=3:
        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 comb(n,k):
  if k==0:
    return 1
  if k==1:
    return n
  if k==2:
    return n*(n-1)//2
  if k==3:
    return n*(n-1)*(n-2)//6
  return None
def cnt(n,k):
  if k==0:
    return 1
  if k>len(n):
    return 0
  return (comb(len(n)-1,k)*9**k
          +(int(n[0])-1)*comb(len(n)-1,k-1)*9**(k-1)
          +cnt(n[1:],k-1))
def main():
  n=input()
  k=int(input())
  print(cnt(n,k))
main()

Submission status: Wrong Answer

Solution code:
def count(keta,kazu):
    if(keta<kazu):
        return 0
    result=1
    wari=1
    for i in range(kazu):
        wari*=i+1
        result*=keta-i
    result//=wari
    #print(result)
    for i in range(kazu):
        result*=9
    return result


def Ans(moji,kazu):
    #print(moji,kazu)
    naga=len(moji)
    if(naga<kazu):
        return 0
    if(kazu==0):
        return 1
    sento=int(moji[0])
    if(naga==1):
        return sento
    #return Ans(moji[1:],kazu)+Ans(moji[1:],kazu-1)+count()
    if(sento==0):
        plus=Ans(moji[1:],kazu)
    else:
        plus=Ans(moji[1:],kazu-1)
    #print(count(naga-1,kazu),count(naga-1,kazu-1),plus)
    return count(naga-1,kazu)+count(naga-1,kazu-1)*(sento-1)+plus

n=input()
l=len(n)
k=int(input())

print(Ans(n,k))

Submission status: Wrong Answer

Solution code:
import itertools
#nCr
import math
def com(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n=input()
k=int(input())
m=len(n)
if k==1:
    x=int(n[0])
    print(9*(m-1)+x)
    exit()
ans=0
x=int(n[0])
ans+=9**k*com(m-1,k)+(x-1)*com(m-1,k-1)*9**(k-1)
# print(9**k*com(m-1,k),(x-1)*com(m-1,k-1)*9**(k-1))
# print(ans)
if k==3:
    if m<3:
        print(0)
    x=int(n[1])
    ans+=9**2*com(m-2,2)+(x-1)*com(m-2,1)*9
    ans+=int(n[2])+9*(m-3)
elif k==2:
    if m==1:
        print(0)
        exit()
    ans+=int(n[1])+9*(m-2)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if m < K:
        return ans
    else:
        if K == 1:
            y = Z[0]
            ans += (m-1) * 9 + y
            #print(ans)
        elif K == 2:
            #0 
            ans += ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * (m-1) * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            ans += nn(Z,K,m)
            #print(ans)
        elif K == 3:
            #0 
            ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
            ans += nn(Z,K,m)
        return ans
if len(str(N)) < K:
    ans = 0
else:
    ans = nn(Z,K,m)        
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial as fac

def comb(n,r):
    if ( r<0 or r>n ):
        return 0
    return fac(n)/(fac(r)*fac(n-r))


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

nn=str(n)
keta=len(nn)

ans=0

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

zero=0

for i in range(keta):
    if int(nn[i])==0:zero+=1
    ans+=comb(keta-i-1,k-i+zero)*9**(k-i)
    if int(nn[i])-1>=0:
        ans+=(int(nn[i])-1)*comb(keta-i-1,k-i-1+zero)*9**(k-i-1+zero)

if keta-zero==k:ans+=1

print(int(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 == 0:
        return 1
    
    top = n//10**(keta-1)%10
    ans = 0
    # 0のとき
    ans += 1 * (0 if keta==1 else dp[k][keta-1])
    # log(keta,top,k,ans)

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

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

ans += sol(n, keta, k)
keta -= 1

# base = 0
# while 10**base <= n:
#     x = n // 10**base % 10
#     y = x * dp[1][base]
#     log(base, x, y)
#     ans += y

#     base += 1

print(ans)

Submission status: Wrong Answer

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

def nCmMOD(A,B,Mod):
    #a conb b を　Mod で割った余り
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

L=len(str(N))
ans=0
if L-1>=K:
    ans=nCmMOD(L-1,K,10**9+7)*(9**K)
#print(ans)

List=[]
for i in range(1,10):
    List.append(i*10**(L-1))
#print(List)

import sys
if K==1:
    for i in List:
        if i<=N:
            ans+=1
        else:
            print(ans)
            sys.exit()
    print(ans)
if K==2:
    for i in List:
        for j in range(L-1):
            for k in range(1,10):
                T=i+k*10**j
                if T<=N:
                    ans+=1
                else:
                    print(ans)
                    sys.exit()
    print(ans)
elif K==3:
    List3=[]
    for i in List:
        for j in range(L-1):
            for k in range(j+1,L-1):
                for l in range(1,10):
                    for m in range(1,10):
                        T=i+m*10**j+l*10**k
                        if T<=N:
                            ans+=1
                        else:
                            print(ans)
                            sys.exit()
    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:
                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())
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):
        for b in range(a+1,x-1):
            for c in range(b+1,x):
                if a==0 and b==1 and c==2:
                    ans+=(w[a]-1)*w[b]*9
                    ans+=1*(w[b]-1)*9
                    ans+=1*1*w[c]
                else:
                    ans+=9**3
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:
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(min(100,len(str(n)))):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    for a in range(1,int(str(n)[i])):
                        for b in range(1,10):
                            for c in range(1,10):
                                P=str(a)+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            for j in range(i+1,100):
                for k in range(j+1,100):
                    for b in range(1,10):
                        for c in range(1,10):
                            P=str(n)[i]+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                            if 1<=int(P)<=n:
                                counter+=1
    print(counter)

Submission status: Wrong Answer

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

    print(max(0,ans))

Submission status: Wrong Answer

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

L = len(N)
if K>L:
    print(0)
    sys.exit()
#%%
def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)* int((L2-1)>0)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == K:
    ans += 1
print(int(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 == 0:
        return 1
    
    top = n//10**(keta-1)%10
    ans = 0
    # 0のとき
    ans += 1 * (1 if keta==1 else dp[k][keta-1])
    # log(keta,top,k,ans)

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

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

ans += sol(n, keta, k)
keta -= 1

# base = 0
# while 10**base <= n:
#     x = n // 10**base % 10
#     y = x * dp[1][base]
#     log(base, x, y)
#     ans += y

#     base += 1

print(ans)

Submission status: Wrong Answer

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

l = len(str(N))
a = N // 10**(l - 1)

if K == 1:
    ans = 9 * (l - 1) + a
    print(ans)
elif K == 2:
    b = N // 10**(l - 2)
    d = b - 10 * a
    if l == 1:
        print(0)
    else:
        ans = 81 * (l - 1) * (l - 2) // 2
        ans += (a - 1) * 9 * (l - 1) + 9 * (l - 2) + d
        print(ans)
else:
    b = N // 10**(l - 2)
    c = N // 10**(l - 3)
    d = b - 10 * a
    e = c - 100 * a - 10 * d
    if l == 1 or l == 2:
        print(0)
    else:
        ans = 729 * (l - 1) * (l - 2) * (l - 3) // 6
        ans += (a - 1) * 81 * (l - 1) * (l - 2) // 2
        ans += 81 * (l - 2) * (l - 3) // 2
        if d != 0:
            ans += (d - 1) * 9 * (l - 2)
            ans += (l - 3) * 9 + e
        else:
            ans += 81 * (l - 2) * (l - 3) // 2
        print(ans)

Submission status: Wrong Answer

Solution code:
N_str = input().strip()
L = len(N_str)
N_list = list(map(int, N_str))
N = int(N_str)
K = int(input())

cache = [None] * 1000

def count3(num):
	if cache[num] != None:
		return cache[num]
	count = 0
	for i in range(100, num + 1):
		if i % 10 != 0 and (i // 10) % 10 != 0:
			count += 1
	cache[num] = count
	return count

def count1(s):
	total = 0
	for i in range(s, L):
		if i == s:
			total += N_list[i]
		else:
			total += 9
	return total

def count2(s):
	total = 0
	for i in range(s, L - 1):
		if i == s:
			total += (N_list[i] - 1) * (L - i - 1) * 9 + count1(i + 1)
		else:
			total += 81 * (L - i - 1)
	return total

if K == 1:
	total = count1(0)
elif K == 2:
	total = count2(0)
else:
	total = 0
	for i in range(0, L - 2):
		if i == 0:
			total += (N_list[i] - 1) * (L - i - 1) * 9 * (L - i - 2) * 9 // 2 + count2(i + 1)
		else:
			total += 729 * (L - i - 1) * (L - i - 2) // 2

print(total)

Submission status: Wrong Answer

Solution code:
from math import factorial

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

strN = str(N)
keta = len(strN)
top = int(strN[0])

def nCr(n, r):
    if n < r:
        return 0
    return int(factorial(n) / factorial(r) / factorial(n - r))

res = 9**K*nCr((keta-1), K)

if K == 1:
    res += top

else:
    res += (top-1)*9**(K-1)*nCr((keta-1), K-1)

    if K == 2:
        for i in range(1, keta):
            if int(strN[i]) == 0:
                continue
            res += int(strN[i])
            res += 9*(keta-i-1)
            break

    else:
        for i in range(1, keta):
            if int(strN[i]) == 0:
                continue
            for j in range(i+1, keta):
                if int(strN[j]) == 0:
                    continue
                res += int(strN[i]) * int(strN[j])
                res += int(strN[i]) * 9 *(keta-j-1)
                break


print(res)

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 == 0:
        return 1
    
    top = n//10**(keta-1)%10
    ans = 0
    # 0のとき
    ans += 1 * dp[k][keta-1]
    # log(keta,top,k,ans)

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

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

ans += sol(n, keta, k)
keta -= 1

# base = 0
# while 10**base <= n:
#     x = n // 10**base % 10
#     y = x * dp[1][base]
#     log(base, x, y)
#     ans += y

#     base += 1

print(ans)

Submission status: Wrong Answer

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

L = len(N)
if K>L:
    print(0)
    sys.exit()
#%%
def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == K:
    ans += 1
print(int(ans))

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):
    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
    # 最上位bitに0
    if bl>=2:
        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:
        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>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    if bl>=3:
        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:
n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())

#割り算のやーつ
MOD = 1000000007

# 二項係数関連.
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0
if(n_digit < k):
    # 満たす物は無い.
    print(0)
else:
    # 最大桁数-1の桁の数について.
    if(n_digit > k):
        # 何が入っても問題ないので、3箇所選んで1-9をそれぞれ選ぶ.
        ans += com.calc_COM(n_digit-1, k) * (9 ** k)
    # 最大桁の桁の数について.
    n_top = int(n_str[0])
    if(k-1 <= 0):
        # これで終わりだから自由
        ans += n_top
    else:
        # 最大桁がn_top未満なら残りは自由
        ans += com.calc_COM(n_digit-1, k-1) * (9 ** (k-1)) * (n_top - 1)
        # 最大桁がn_topなら、残りは自由じゃない……
        n_sec = 0
        count = 1
        for nc in n_str[1:]:
            n_sec = int(nc)
            if(n_sec > 0):
                break
            count += 1
        if((n_digit - count) >= k-1):
            # まだ可能性がある！
            left = n_digit - count
            # 次に来る1以上の数字がcountよりも先だったら二つとも自由
            ans += com.calc_COM(left-1, k-1) * (9 ** (k-1))
            # 次の1以上の数字がcountの位置に来る.
            if(k-2 <= 0):
                ans += n_sec # これで終わりだからその下は考えないでいいのじゃ.
            else:
                # 次に来る1以上の数字がcountで、n_sec未満なら残りは自由
                ans += (left-1) * 9 * (n_sec - 1)
                # 次に来る1以上の数字がcountで、n_secと同じなら、残りは自由じゃない……
                sec_count = count + 1
                n_third = 0
                for nc in n_str[count:]:
                    n_third = int(nc)
                    if(n_sec > 0):
                        break
                    sec_count += 1
                if((n_digit - sec_count - 1) >= k - 2):
                    # まだ可能性がある！
                    left_sec = n_digit - sec_count
                    # 最後の数字がsec_countよりも下の位置
                    ans += (left_sec-1) * 9
                    # 最後の数字がsec_countの位置
                    ans += n_third

    print(ans)