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

def nCmMOD(A,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**10+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)
elif 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:
    for i in List:
        for j in range(L-1):
            for k in range(j+1,L-1):
                if i+9*10**j+9*10**k<=N:
                    ans+=81
                else:
                    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)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0

    for i in range(point2,99):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0

    for i in range(point3,999):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "0":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-3)
            delay += 9*(n-2)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
n=int(input())
lenn=len(str(n))

k=int(input())
#k:1~3

result=0

if n <=9:
    if k==1:
        print(n)
    else:
        print(0)
    exit()
elif n <=99:
    if k==1:
        print(n//10+9)
    elif k==2:
        print((n//10-1)*9+n%10)
    else:
        print(0)
    exit()
    """
elif n <=999:
    if k==1:
        print(n//100+9+9)
    elif k==2:
        print((n//100-1)*9+9*9)
    else:
        print(0)
    exit()
    """
else:
    if k==1:
        print(9*(lenn-1)+n//(10**(lenn-1)))
    elif k==2:
        result=0
        #先頭の文字を抜いた状態で
        result+=9*9*(lenn-1)*(lenn-2)//1//2
        #print(result)
        #先頭の文字を1ひいて
        result+=(n//(10**(lenn-1))-1)*9*(lenn-1)
        #print(result)

        for i in str(n)[1:]:
            result+=int(i)
        print(result)
    else:
        if lenn==3:
            result=(n//(10**(lenn-1))-1)*9*9
            temp=1
            for i in str(n)[1:]:
                temp=temp*int(i)
            result+=temp
            print(result)
            exit()
        else:
            result=0
            #先頭の文字を抜いた状態で
            result+=9*9*9*(lenn-1)*(lenn-2)*(lenn-3)//1//2//3
        #先頭の文字を1ひいて
            result+=(n//(10**(lenn-1))-1)*9*9*(lenn-1)*(lenn-2)//1//2
            temp=1
            i=1
            while i<lenn:
                j=i+1
                while j<lenn:
                    result+=int(str(n)[i])*int(str(n)[j])
                    j+=1
                i+=1

            print(result+17)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  #未満T or F , i桁目, 0でない数値がちょうどk個

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        dp[("T",i,0)]=1
        dp[("T",i,1)]=max(x-1,0)
        dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            #print "dp i,k,i-1,k ",i,k,i-1,k
            dp[("T",i,k)]+=dp[("T",i-1,k)]
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9
            dp[("F",i,k)]+=dp[("F",i-1,k)]
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*1
            dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1)

print dp[("T",l,K)]+dp[("F",l,K)]

Submission status: Wrong Answer

Solution code:
N = int(input())
n = str(N)
K = int(input())
if len(n)< K:
    print(0)
else:
    if K == 1:
        if N < 10:
            print(N)
        else:
            print(9*(len(n)-1)+1)
    elif K == 2:
        if N <= 10:
            print(0)
        elif N <= 99:
            print((int(str(N)[0])-1)*9+int(str(N)[1]))
        else:
            print(81*(len(n)-2)*(int(str(N)[0])-1))
            print(int(str(N)[-1]))
    else:
        print()

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    if n == 0: return 1
    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

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

ans = 0
if K == 1:
    d = 1
    flag = False
    while True:
        for i in range(1,10):
            if d * i > N:
                flag = True
            else:
                ans += 1
        d *= 10

        if flag:
            break
elif K == 2:
    d1 = 10
    flag = False
    while True:
        for i in range(1,10):
           d2 = 1
           while d2 < d1:
                for j in range(1,10):
                    if d1 * i + d2 * j > N:
                       flag = True
                    else:
                        ans += 1
                
                d2 *= 10

                if flag:
                    break
        
        d1 *= 10

        if flag:
            break
else:
    d1 = 100
    flag = False
    while True:
        tmp = cmb(len(str(d1))-1,K-1)
        for i in range(1,10):
            if d1 * i <= N:
                ans += tmp
                continue

            d2 = 10
            while d2 < d1:
                tmp = (d1*i) * cmb(len(str(d2))-1,K-2)
                for j in range(1,10):
                    if d1 * i + d2*j <= N:
                        ans += tmp
                        continue

                    d3 = 1
                    while d3 < d2:
                        for k in range(1,10):
                            if d1 * i + d2 * j + d3 * k > N:
                                flag = True
                            else:
                                ans += 1
                        d3 *= 10
                        if flag:
                            break
                
                d2 *= 10

                if flag:
                    break
        
        d1 *= 10

        if flag:
            break

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]))
        )

        for i in range(1, keta):
            if n_str[i] != 0:
                break
            else:
                ans -= (9-int(n_str[i]))

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


M = len(N)
if K >= M:
    print(0)
    quit()

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

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

if K == 3:
    ans = int(N[2])
    ans += (M - 3) * 9
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (M - 2) * (M - 3) // 2 * 9 * 9
    ans += (int(N[0]) - 1) * (M - 1) * (M - 2) // 2 * 9 * 9
    ans += (M - 1) * (M - 2) * (M - 3) // 6 * 9 * 9 * 9
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

input = sys.stdin.readline
n = int(input())
k = int(input())
t = n
m = 0
while t:
    m += 1
    t //= 10

def comb(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 9 ** k * comb(m-1, k)
tk = k

def dfs(i, mt, kt):
    a = i // 10 ** mt
    b = n // 10 ** mt
    if i == n:
        return 1
    elif i > n:
        return 0
    if kt < 0:
        return 0
    if mt < kt:
        return 0
    if a < b:
        if mt >= 0:
            return 9 ** kt * comb(mt, kt)
        else:
            return 1
    elif a > b:
        return 0
    ret = 0
    for j in range(10):
        f = 0
        if j != 0:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

t_ans = 0
for i in range(1, n // (10 ** (m-1) )+1):
    ti = i * 10 ** (m-1)
    if ti > n:
        break
    t_ans += dfs(ti, m-1, k-1)

print(int(ans+t_ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
R = len(str(n))
r = R - 1
q = 0
num = [0] * 4
index = [0] * 4
s = str(n)
for i in range(R):
    if s[i] != "0":
        num[q] = int(s[i])
        index[q] = i
        q += 1
    if q == 4:
        break

if k == 1:
    ans = 9 * r + num[0]
elif k == 2:
    ans = 81 * r * (r-1) // 2
    if num[1] != 0:
        pass
    else:
        num[1] = 9
        index[1] = 1
    ans += 9 * (R - 1) * (num[0] - 1) + num[1] + 9 * (R - index[1] - 1)
elif k == 3:
    ans = 243 * r * (r-1) * (r-4) // 2
    if num[2] != 0:
        pass
    elif num[1] != 0:
        num[1] -= 1
        index[2] = index[1] + 1
        num[2] = 9
    else:
        num[0] -= 1
        index = [0, 1, 2]
        num[1], num[2] = 9, 9
    ans += 81 * (R-1)*(R-2)*(num[0]-1)//2 + 9 * (R - index[1] - 1) * (num[1] - 1)
    ans += 81 * (R-index[1]-1)*(R-index[1]-2) // 2
    ans += 9 * (R - index[2] - 1) + num[2]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
k=int(input())
m=str(n)
l=len(m)
if k>l:
  print(0)
  sys.exit()
if k==1:
  print(9*(l-1)+int(m[0]))
if k==2:
  print((((9**2)*(l-1)*(l-2)//2)+(int(m[0])-1)*(l-1)*9)+9*(l-2)+int(m[1]))
if k==3:
  if int(m[1])>0:
    print(((9**3)*(l-1)*(l-2)*(l-3)//6)+(int(m[0])-1)*(9**2)*((l-2)*(l-1)//2)+(((9**2)*(l-2)*(l-3)//2)+(int(m[1])-1)*(l-2)*9)+9*(l-3)+int(m[2]))
  else:
    print(((9**3)*(l-1)*(l-2)*(l-3)//6)+(int(m[0])-1)*(9**2)*((l-2)*(l-1)//2)+(((9**2)*(l-2)*(l-3)//2)))

Submission status: Wrong Answer

Solution code:
# E
N = int(input())
K = int(input())
import math
L = int(math.ceil(math.log10(N))) # 桁数

if K==1:
    print(9 * (L-1) + N//(1*10**(L-1)))
if K==2:
    if L==1:
        print(0)
    else:
        s = 0
        for i in range(2,L):
            s += 9*9*(i-1)
        # 全探索しちゃう
        for i in range(1,L):
            for mx in range(1,10):
                for lx in range(1,10):
                    if N >= (mx*10**(L-1) + lx*10**(i-1)):
                        s += 1
        print(s)
if K==3:
    if L<=2:
        print(0)
    else:
        s = 0
        for i in range(3,L):
            for j in range(2,i):
                s += 9*9*9*(j-1)
        for mx in range(1,10): # 先頭
            for bi in range(2,L): # おっきい方
                for bx in range(1,10):
                    for si in range(1,bi): # ちっさい方
                        if N >= (mx*10**(L-1) + 9*10**(bi-1) + bx*10**(si-1)):
                            s += 9
        print(s)

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+=(int(str(n)[0])-1)*(keta-1)*9
        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
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
    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
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
    else:
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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

ans = 0

for i in range(k, len(str(n))) :
    if k == i or k == 1:
        ans += 9**(k)
        continue
    ans += combinations_count(i-1, k) * 9**(k)

print(ans)

Submission status: Wrong Answer

Solution code:
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 = int(input());
k = int(input());
ns = str(n);

ans = 0;
for m in range(k,len(ns)) :
	ans += cmb(m-1,k-1)*9**k;

print(ans);

if k == 1 :
	ans += int(ns[0]);
elif k == 2 :
	for i in range(1,len(ns)) :
		ans += int(ns[0]) * int(ns[i]) + (int(ns[i])-1)*9;
elif k == 3 :
	for i in range(1,len(ns)) :
		for j in range(1,len(ns)) :
			if not i == j :
				ans += int(ns[0]) * int(ns[i])* int(ns[j])+ (int(ns[i])-1)*9*9;

print(ans);

Submission status: Wrong Answer

Solution code:
import itertools as it
import math

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

keta = len(N)

ans = 0
num = "9" *K
def perm(n,k):
    return math.factorial(n)//math.factorial(n-k)

ans=0
if keta > K:
    ans += (9**K) * perm(keta-1, K)//math.factorial(K)
#print(ans)

if K>keta:
    ans = 0
elif K==1:
    ans += int(N[0])
elif K==2:
    ans += (int(N[0])-1) * 9 * (keta-1)#あたまが1小さい
    ans += int(N[1])#頭が同じ
    if keta >= 3:
        ans += 9 * (keta-2)
else:
    ans += (int(N[0]) - 1)*(9**2)*perm(keta-1, 2)//2 ##頭が1小さい
    ##頭が同じ
    if keta-2 >= 2:
        ans += 9**2 * perm(keta-2, 2)//2
    if int(N[1])>0:#上2桁目-1
        ans += (int(N[1])-1)*9*(keta-2)
    #上2桁目まで同じ
    if keta-3>0:
        ans += 9*(keta-3)
    #上3桁目まで同じ
    ans += int(N[2])

# if K==1:
#     ans += int(N[0])
# elif K==2:
#     ans += int(N[0:2])
#     for i in range(keta-2):
#         ans += int(N[0]) * 9 
# else:
#     ans += int(N[0:3])
#     ans += int(N[0]) * 99 * perm(keta-2, 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


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

def zero(n,k,l):
    saidai=n//(10**(l-1))
    small=n-10**(l-1)*saidai
    if l<k:
        return 0
    elif k==0:
        return 1
    elif l==1:
        return n
    elif l==k:
        return (cmb(l-1,k-1)*9**(k-1)*(saidai-1)+zero(small,k-1,l-1))
    else:
        ans = cmb(l-1,k)*9**k+cmb(l-1,k-1)*9**(k-1)*(saidai-1)+zero(small,k-1,l-1)
        return ans


print(zero(n,k,l))

Submission status: Wrong Answer

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


M = len(N)
if K > M:
    print(0)
    quit()

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

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

if K == 3:
    ans = int(N[2])
    ans += (M - 3) * 9
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (M - 2) * (M - 3) // 2 * 9 * 9
    ans += (int(N[0]) - 1) * (M - 1) * (M - 2) // 2 * 9 * 9
    ans += (M - 1) * (M - 2) * (M - 3) // 6 * 9 * 9 * 9
    print(ans)

Submission status: Wrong Answer

Solution code:
strN = input()
N = int(strN)
K = int(input())
ans = 0
N_copy = 0
N_copy += N
lenN = 0
for s in range(N):
    if N_copy > 0:
        lenN += 1
        N_copy //= 10
    else:
        break
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    if lenN >= 2:
        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:
    if lenN >= 3:
        ans += int(strN[2])+(lenN-3)*9
        if int(strN[1]) != 0:
            ans += (int(strN[1]) - 1) * 9 * (lenN - 2)
        ans += 9 * 9 * (((lenN - 2) * (lenN - 3)) // 2)
        ans += (int(strN[0]) - 1) * 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)
        ans += 9*9*9*(((lenN-1)*(lenN-2)*(lenN-3))//6)
        # 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:
n = int(input())
k = int(input())

sm = 0
if n > 10**k:
  sm += n // 10**k
  sm += 10**k - 10**(k-1) - 10*(k-1)
print(sm)

Submission status: Wrong Answer

Solution code:
# give up
n = int(input())
k = int(input())
digit = len(str(n))
s,m =  divmod(n,10**(digit-1))
print(s,m)
if k == 1:
    ans = (digit-1)*9 + s
if k == 2:
    ans = (digit-1)*9 * (s-1) + m
if k == 3:
    ans = 0 
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
start = int('1'*k)
i = start
inc = 10**(k-1)
x = 1
r = 0
lst = []
while i <= n:
    lst.append(i)
    i += inc
    x += 1
    if x == 10:
        x = 0
        inc = 10**(k-r)
        r -= 1
print(len(lst))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
from collections import Counter, deque
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import groupby, permutations, combinations, product
from sys import stdin, stderr


# 最大公約数（ユークリッドの互除法）
# Python3.5 で math.gcd()が追加され、
# AtCoder環境と最新環境でパッケージが分かれてしまったので、自分で書いておく
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


# 拡張ユークリッド互除法
# 正整数x, y について、a*x + b*y == gcd(x,y)なるa,bを返す。
# 特に、互いに素なるx, yについては a*x + b*y == 1 となる a, b。
def exgcd(x, y):
    if y == 0:
        return 1, 0
    a, b = exgcd(y, x % y)
    return b, a - (x // y) * b


# 最小公倍数
def lcm(x, y):
    m = gcd(x, y)
    return (x // m) * (y // m)


def func(n, k):
    if len(n) == 0:
        return 0
    head = int(n[0])
    tail = 9 * (len(n) - 1)
    if k == 1:
        return head + tail
    ret = func(n[1:len(n)], k-1)
    ret += (head-1) * func("9" * (len(n) - 1), k - 1)
    # print(ret)
    for i in range(len(n) - 2):
        ret += 9 * func("9" * (len(n) - 2 - i), k - 1)
    return ret


def main():
    n = input()
    k = int(input())
    return func(n, k)


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0

    for i in range(point2,99):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0

    for i in range(point3,999):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "0":
                delay += 81*(n-3)
            else:
                delay += 9*(n-3)
            delay += 9*(n-2)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
N = input()
num = int(N)
K = int(input())
nl = len(N)
cnt = 0


for i in range(1,nl+1):
    if i < nl:
        if K == 1:
            cnt += 9
        elif K == 2:
            if i > 1:
                cnt += 9 * (i-1) * 9
        else:
            if i > 2:
                cnt += 9 * (i-1) * (i-2) * 9 * 9 // 2
    else:
        if K == 1:
            t = int(N[0])
            cnt += t
        elif K == 2 and i > 1:
            x = int(N[0])
            cnt += (x-1) * (i-1) * 9
            nflg = False
            for j in range(1,nl):
                nj = int(N[j])
                if nflg:
                    cnt += 9
                else:
                    cnt += nj
                if nj > 0:
                    nflg = True
        elif K == 3 and i > 2:
            x = int(N[0])
            cnt += (x-1) * (i-1) * (i-2) * 9 * 9 // 2
            ncnt = 0
            for j in range(1,nl):
                nj = int(N[j])
                #if ncnt > 1 and i-j-2 > 0:
                #   cnt += (i-j-1) * (i-j-2) * 9 * 9 // 2
                if ncnt == 1:
                    if nj > 0 :
                        ncnt += 1
                        if i-j-1 > 0:
                            cnt += (nj-1) * (i-j-1) * 9
                        elif i-j > 0:
                            cnt += nj
                elif ncnt == 0:
                    if nj > 0:
                        ncnt += 1
                        #if i-j-2 > 0:
                        #    cnt += (nj-1) * (i-j-1) * (i-j-2) * 9 * 9 // 2
                        #elif i-j-1 > 0:
                        #    cnt += (nj-1) * 9

print (cnt)

Submission status: Wrong Answer

Solution code:

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


def k1(n, d):
    return n[0] + 9 * (d - 1)


def k2(n, d):
    if d == 1:
        return 0
    res = k1(n[1:], d-1)+(n[0]-1)*9*(d-1)
    for i in range(d-2):
        res += 81*(i+1)
    return res

def k3(n, d):
    if d <= 2:
        return 0
    res = k2(n[1:], d-1)+(n[0]-1)*9*9*((d-2)/2*(d-1))
    for i in range(1, d-2):
        res += 9*9*9*(i/2*(i+1))
    return int(res)

if K == 1:
    print(k1(N, D))
elif K == 2:
    print(k2(N, D))
else:
    print(k3(N, D))

Submission status: Wrong Answer

Solution code:
import math
fac = math.factorial
n = int(input())
K = int(input())
lst = []
cnt = 0
for i in range(10**(K-1), 10**K):
  if str(i).count("0") != 0:
    continue
  lst.append(list(map(int, list(str(i)))))
if K == 1:
  for i in range(100-K):
    for lsti in lst:
      if lsti[0] * 10 ** i <= n:
        cnt += 1
elif K == 2:
  for i in range(1, 100-K):
    for j in range(100-K-i):
      for lsti in lst:
        if lsti[0] * 10 ** (i+j) \
             + lsti[1] * 10 ** j <= n:
          cnt += 1
elif K == 3:
  for i in range(2, 100-K):
    for j in range(1, 100-K-i):
      for k in range(100-K-i-j):
        for lsti in lst:
          if lsti[0] * 10 ** (i+j+k) \
             + lsti[1] * 10 ** (j+k) \
             + lsti[2] * 10 ** k <= n:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
# E
N = int(input())
K = int(input())
import math
L = int(math.ceil(math.log10(N))) # 桁数

if K==1:
    print(9 * (L-1) + N//(1*10**(L-1)))
if K==2:
    if L==1:
        print(0)
    else:
        s = 0
        for i in range(2,L):
            s += 9*9*(i-1)
        # 全探索しちゃう
        for i in range(1,L):
            for mx in range(1,10):
                for lx in range(1,10):
                    if N >= (mx*10**(L-1) + lx*10**(i-1)):
                        s += 1
        print(s)
if K==3:
    if L<=2:
        print(0)
    else:
        s = 0
        for i in range(3,L):
            for j in range(2,i):
                s += 9*9*9*(j-1)
        for mx in range(1,10): # 先頭
            for bi in range(2,L): # おっきい方
                for bx in range(1,10):
                    for si in range(1,bi): # ちっさい方
                        
                            if N >= (mx*10**(L-1) + bx*10**(bi-1) + 9*10**(si-1)):
                                s += 9
        print(s)

Submission status: Wrong Answer

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

for i in range(1, n+1):
    if sum([int(x) for x in list(str(i))]) > k-1 and len(str(i)) >= k:
    # if len(str(i)) >= k:
        count += 1
        if i % 10 != k-1 and len(str(i)) > k:
            count -= 1
        if k == int(str(i).replace("0","")):
            count -=1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools as it
import math

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

keta = len(N)

ans = 0
num = "9" *K
def perm(n,k):
    return math.factorial(n)//math.factorial(n-k)

ans=0
if keta > K:
    ans += (9**K) * perm(keta-1, K)//math.factorial(K)
#print(ans)

if K>keta:
    ans = 0
elif K==1:
    ans += int(N[0])
elif K==2:
    ans += (int(N[0])-1) * 9 * (keta-1)#あたまが1小さい
    ans += int(N[1])#頭が同じ
    if keta >= 3:
        ans += 9 * (keta-2)
else:
    ans += (int(N[0]) - 1)*(9**2)*perm(keta-1, 2)//2 ##頭が1小さい
    ##頭が同じ
    if keta-2 >= 2:
        ans += 9**2 * perm(keta-2, 2)//2
    if int(N[1])>0:#上2桁目-1
        ans += (int(N[1])-1)*9*(keta-2)
    #上2桁目まで同じ
    ans += 9*(keta-3)
    #上3桁目まで同じ
    ans += int(N[2])

# if K==1:
#     ans += int(N[0])
# elif K==2:
#     ans += int(N[0:2])
#     for i in range(keta-2):
#         ans += int(N[0]) * 9 
# else:
#     ans += int(N[0:3])
#     ans += int(N[0]) * 99 * perm(keta-2, 2)

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

def search(n,k):
    if k<=0:return
    global ans
    nn = str(n)
    keta = len(nn)
    ans += comb(keta - 1, k ) * 9 ** k
    if int(nn[0])-1>0:
        ans+=(int(nn[0])-1)*comb(keta-1,k-1)*9**(k-1)
    ne=n-int(nn[0])*10**(keta-1)
    search(ne,k-1)

search(n,k)
print(int(ans)+1)

Submission status: Wrong Answer

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


def count_0(range_value, zero_count):
    k = 0

    for i in range(range_value):
        if str(i).count("0") == zero_count:
            k+=1

    return k


print(count_0(N, K))

Submission status: Wrong Answer

Solution code:
import sys
import math

input = sys.stdin.readline
n = int(input())
k = int(input())
t = n
m = 0
while t:
    m += 1
    t //= 10

def comb(n, r):
    if r > n:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 9 ** k * comb(m-1, k)
tk = k

def dfs(i, mt, kt):
    a = i // 10 ** mt
    b = n // 10 ** mt
    if i == n:
        return 1
    elif i > n:
        return 0
    if kt < 0:
        return 0
    if mt < kt:
        return 0
    if a < b:
        if mt >= 0:
            return 9 ** kt * comb(mt, kt)
        else:
            return 1
    elif a > b:
        return 0
    ret = 0
    for j in range(10):
        f = 0
        if j != 0:
            f = 1
        ret += dfs(i+j*10**(mt-1), mt-1, kt-f)
    return ret

t_ans = 0
for i in range(1, n // (10 ** (m-1) )+1):
    ti = i * 10 ** (m-1)
    t_ans += dfs(ti, m-1, k-1)

print(int(ans+t_ans))