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())
n = str(N)
i = 0
while N//10**i != 0:
    i += 1
if i == 1 and K == 1:
    ans = N
elif i == K == 2:
    a = int(n[0])
    ans = (N-a*10)+(a-1)*9
elif i == K == 3:
    a = int(n[0])
    ans = (N-a*100)+(a-1)*81
elif i < K:
    ans = 0
else:
    a = int(n[0])
    ans = a+9*(i-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S=list(map(int,str(N)))

def C(n,r):
  if n>=r:
    return factorial(n)//factorial(r)//factorial(n-r)
  else:
    return 0

def D(i,j):
  return C(i,j)*(9**j)

ans=0
l=len(S)

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

for i in range(l):
  if S[i]!=0:
    ans+=(S[i]-1)*D(l-1,K-1)+D(l-1,K)
    l-=1
    K-=1
  else:
    l-=1
  if K==0:
    break
    
print(ans+1)

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
    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:
#  --*-coding:utf-8-*--

import math

def f(m, k):
    if k > m:
        return 0

    return math.factorial(m)//(math.factorial(m-k)*math.factorial(k))*(9**k)


def g(N, K):
    M = len(N)
    if M < K:
        return 0

    s = 1
    for k in range(K):
        n = int(N[k])
        s += f(M-k-1, K-k) + (n-1)*f(M-k-1, K-k-1)
        
    return s


N = input()
K = int(input())
print(g(N, K))

Submission status: Wrong Answer

Solution code:

def solve(p,n,k):
    if k==1:
        return 10 + 9*(n-1)+(p-1)
    elif k==2:
        return 81 * n*(n-1)//2 + (p-1)*9*n
    else:
        return 729 * n*(n-1)*(n-2)//6 + (p-1)*81*n*(n-1)//2

N=input()
K=int(input())
dig = len(N) - 1

try:
    if K == 2:
        print(solve(int(N[0]),dig,2) + solve(int(N[1]),dig-1,1))
    elif K == 3:
        print(solve(int(N[0]),dig,3) + solve(int(N[1]),dig-1,2) + solve(int(N[2]),dig-2,1))
    elif K == 1:
        print(solve(int(N[0]),dig,1))
except:
    print(0)

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:
	ans += int(N[2])
	ans += (L-3)*9

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

	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:
	ans += int(N[1])
	ans += (L-2)*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:
N = input()
K = int(input())


def f(n, d, k):
    if k == 0:
        return 1
    if d == 1:
        return int(n) if k == 1 else 0
    msb = int(n[0])
    return f(n[1:], d - 1, k - 1) + (msb - 1) * f('9' * (d - 1), d - 1, k - 1) + f('9' * (d - 1), d - 1, k)


print(f(N, len(N), K))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

S=input()
N=int(S)
L = len(S)
K=II()
res = 0
if N <= 100000:
    for i in range(N+1):
        st = str(i)
        res += (len(st) - st.count("0")) == K
else:
    tp = int(S[:3])
    for i in range(tp+1):
        st = str(i)
        nonzeros = len(st)-st.count("0")
        # if nonzeros <= K:
        #     print("i{} non{}".format(i, nonzeros))
        if K-nonzeros == 0:
            res += 1
        elif K-nonzeros == 1:
            res += 9*(L-3)
        elif K-nonzeros == 2:
            res += 81*((L-3)*(L-4)//2)
        elif K-nonzeros == 3:
            res += 729*((L-3)*(L-4)*(L-5)//6)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(input())
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def cnt(i):
  c = 0
  for l in str(i):
    if l != "0":
      c += 1
  return c
if n < 1000:
  q = 0
  for i in range(1,n+1):
    if cnt(i) == k:
      q += 1
  print(q)
  quit()
if k == 1:
  print(9*(len(str(n))-1)+int(str(n)[0]))
if k == 2:
  ans = 0
  top = int(str(n)[0])
  if top > 1:
    ans += (top-1)*(9*(len(str(n))-1))
  ans += cmb(len(str(n))-1,2)*81
  n = n - top*10**(len(str(n))-1)
  ans += 9*(len(str(n))-1)+int(str(n)[0])
  print(ans)
  quit()

#k==3
ans = 0
top = int(str(n)[0])
if top > 1:
  ans += (top-1)*cmb(len(str(n))-1,2)*81
ans += cmb(len(str(n))-1,3)*729
n = n - top*10**(len(str(n))-1)
top = int(str(n)[0])
if top > 1:
  ans += (top-1)*(9*(len(str(n))-1))
ans += cmb(len(str(n))-1,2)*81
n = n - top*10**(len(str(n))-1)
ans += 9*(len(str(n))-1)+int(str(n)[0])
print(ans)

Submission status: Wrong Answer

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

DP = [[[1,0,0,0,],[0,0,0,0]] for i in range(len(N)+1)]
for i in range(len(N)):
    if N[-1-i] == '0':
        for k in range(K):
            DP[i+1][0][k+1] = DP[i][0][k+1]
            DP[i+1][1][k+1] = DP[i][1][k+1]
    else:
        for k in range(K):
            DP[i+1][0][k+1] = DP[i][0][k+1]+DP[i][1][k+1]
    for j in range(1,10):
        for k in range(K):
            if j > int(N[-1-i]):
                DP[i+1][1][k+1] += DP[i][1][k] + DP[i][0][k]
            elif j < int(N[-1-i]):
                DP[i+1][0][k+1] += DP[i][1][k] + DP[i][0][k]
            elif j == int(N[-1-i]):
                DP[i+1][0][k+1] += DP[i][0][k]

print(DP[-1][0][K])

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
        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 = 81*(keta-2)*(keta-1)/2+(int(N[0])-1)*(keta-1)*9+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:
def calc(n,k):
    digit = len(n)
    if digit < k:
        return 0
    
    comb = [1]*(k+1)
    for i in range(1,k+1):
        comb[i] = comb[i-1] * (digit-i) //i
    if k==1:
        return 9*comb[1] + int(n[0])
    elif k==2:
        return (9**2)*comb[2] + (int(n[0])-1) * 9*comb[1] + calc(n[1:],1)
    elif k==3:
        return (9**3)*comb[3] + (int(n[0])-1) * (9**2) * comb[2] + calc(n[1:],2)

n=input()
k=int(input())
print(calc(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~(その数未満)
    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:
import sys

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

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

top = int(n[0])

if l == 1:
    if k >= 2:
        print(0)
        sys.exit()
    print(top)
    sys.exit()

if k == 1:
    z = 9
elif k == 2:
    z = 81
else:
    z = 729

ans = comb(l - 1, k) * z
ans += comb(l - 1, k - 1) * (top - 1) * (z // 9)

if k == 1:
    ans+=top
elif k == 2:
    for i in range(1, l):
        if i==1 or int(n[1:i]) == 0:
            ans += int(n[i])
        else:
            ans += 9
elif k == 3:
    for i in range(1, l):
        for j in range(i + 1, l):
            flag1 = i == 1 or int(n[1:i]) == 0
            flag2 = j == i + 1 or int(n[i + 1 :j]) == 0
            if not(flag1) and not(flag2):
                ans += 81
            elif flag1 and not (flag2):
                ans += 9 * int(n[i])
            elif not (flag1) and flag2:
                ans += 81
            else:
                ans += 9 * (int(n[i]) - 1) + int(n[j])

print(max(0,ans))

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

print(solve(n,k))

Submission status: Wrong Answer

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

l = len(n)

ans = 0

# n-1桁からKこ取る
tmp = 1
for i in range(1, k+1):
    tmp = tmp*9*(l-i)
for i in range(1, k+1):
    tmp = tmp // i
ans += tmp

# 最上位から1つ（最上位の数以外）とる。
tmp = n[0]-1
for i in range(1, k):
    tmp = tmp*9*(l-i)
for i in range(1, k):
    tmp = tmp // i
ans += tmp

# 最上位からその数をとる。
tmp = 0
if k == 3:
    sm = sum(n[2:])
    for i in range(1, l):
        if n[i] != 0:
            aaaa = (n[i]-1) * 9 * (l-i-1)
            aaaa += 1 * sm
            tmp += aaaa
            sm -= n[i]
elif k == 2:
    for i in range(1, l):
        if n[i] != 0:
            tmp += n[i] + 9*(l-i-1)
            break
else:
    tmp += 1
ans += tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    K = int(input())
    if N <= 1000:
        count = 0
        for i in range(1, N + 1):
            d = 0
            ci = i
            while ci > 0:
                d += (1 if ci % 10 > 0 else 0)
                ci //= 10
            if d == K: count += 1
    else:
        strN = str(N)
        dig = len(strN)
        DPsmall = [[0 for j in range(K + 1)] for i in range(dig)]
        DPsmall[0][0] = 1
        DPsmall[0][1] = int(strN[0]) - 1
        for i in range(1, dig):
            DPsmall[i][0] = 1
            for j in range(1, K + 1):
                DPsmall[i][j] += DPsmall[i-1][j-1] * 9 + DPsmall[i-1][j]
            
        DPlarge = [[0 for j in range(K + 1)] for i in range(dig)] #最初の桁がNの最初と一致
        DPlarge[0][0] = 1
        for i in range(1, dig):
            if strN[i] == "0": DPlarge[i][0] = DPlarge[i-1][0]
            else: DPlarge[i][0] = DPlarge[i-1][0] + 1
            for j in range(1, K + 1):
                if DPlarge[i-1][0] == j - 1: DPlarge[i][j] += (int(strN[i]) - 1 if strN[i] != "0" else 0)
                if DPlarge[i-1][0] == j: DPlarge[i][j] += (1 if strN[i] != "0" else 0)

                DPlarge[i][j] += DPlarge[i-1][j] #i桁目が0
                if j > 1: DPlarge[i][j] += DPlarge[i-1][j-1] * 9 #i桁目は0以上

        ans = DPsmall[dig-1][K] + DPlarge[dig-1][K]
        if DPlarge[dig-1][0] == K: ans += 1
        print(ans)   
        #print(DPsmall)
        #print(DPlarge)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S=list(map(int,str(N)))

def C(n,r):
  if n>=r:
    return factorial(n)//factorial(r)//factorial(n-r)
  else:
    return 0

def D(i,j):
  return C(i,j)*(9**j)

ans=0
l=len(S)
for i in range(l):
  if S[i]!=0:
    ans+=(S[i]-1)*D(l-1,K-1)+D(l-1,K)
    l-=1
    K-=1
  else:
    l-=1
  if K==0:
    break
    
print(ans+1)

Submission status: Wrong Answer

Solution code:
import bisect
import math


def perm(n, r):
    if n < r:
        return 0
    return math.factorial(n) // math.factorial(n - r)


def comb(n, r):
    return perm(n, r) // math.factorial(r)


def gen_A():
    A = []
    n = 1
    while n <= 10 ** 100:
        for i in range(1, 10):
            A.append(n * i)
        n *= 10
    return A


N = int(input())
K = int(input())
A = gen_A()
I = bisect.bisect(A, N)
ans = 0
for a in A[: I - 1]:
    length = len(str(a))
    if length >= K:
        ans += comb(length - 1, K - 1) * 9 ** (K - 1)

str_N = str(N)
if len(str_N) >= K:
    if K == 1:
        ans += 1
    if K == 2:
        ans += int(str_N[1])
        for _ in range(len(str_N) - 2):
            ans += 9
    if K == 3:
        ans += int(str_N[1]) * (len(str_N) - 2) * 9
        ans += comb(len(str_N) - 2, 2) * 9 ** 2


print(ans)

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    ret = 0
    for c in n:
        if c != '0':
            ret += 1
    return ret

ans = 0

for i in range(min(len(n), k)):
    if int(n[i]) == 0:
        continue
    if len(n)-i > k:
        ans += calc(i, k)
    k -= 1
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)
    if k == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    ret = 0
    for c in n:
        if c != '0':
            ret += 1
    return ret

ans = 0
# if len(n) == k and cnt(n) == k:
#     ans +=1

for i in range(min(len(n), k)):
    if int(n[i]) == 0:
        continue
    if len(n)-i > k:
        print(calc(i, k))
        ans += calc(i, k)
    k -= 1
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)
    if k == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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


if int(n)<1000:
    c=0
    for i in range(1,int(n)+1):
       if len(str(i))-str(i).count("0")==k:
           c+=1
    #print(c)
else:
    n_l=len(n)
    c=0
    if k==1:
        c=int(n[0])+9*(n_l-1)
    elif k==2:
        for i in range(2,n_l):
            c+=9*9*(i-1)
        c+=(int(n[0])-1)*9*(n_l-1)
        
        for i in range(1,n_l):
            if int(n[i])>0:
                c+=int(n[i])+(n_l-i-1)*9
                break

    else:
        for i in range(3,n_l):
            c+=9**3*((i-1)*(i-2)/2)
            
        c+=(int(n[0])-1)*(n_l*(n_l-1)/2)
        
        flag_i=False
        flag_j=False
        for i in range(1,n_l):
            if int(n[i])>0:
                flag_i=True
                for j in range(i+1,n_l):
                    if int(n[j])>0:
                        flag_j=True
                        break
            if flag_i:
                break
        if flag_i:
            c+=(int(n[i])-1)*9*(n_l-i-1)
            c+=9*9*((n_l-i-1)*(n_l-i-2)*0.5)
            if flag_j:
                c+=(int(n[j])-1)+9*(n_l-j-1)
                c+=1
                
print(int(c))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math
INF = float("inf")


def solve(N: str, K: int):
    M = len(N)
    DP = [[[0]*2 for __ in range(K+1)] for _ in range(M+1)]
    Nstr = N
    # print(len(Nstr), M)
    # print(math.log10(int(N)))

    DP[1][0][True] = 1
    DP[1][1][True] = int(Nstr[0])-1
    DP[1][1][False] = 1
    for i in range(1, M):
        DP[i+1][0][True] = 1
        DP[i+1][0][False] = 0
        for k in range(K):
            DP[i+1][k+1][True] = DP[i][k][True]*9 + DP[i][k+1][True]*1
            if int(Nstr[i]) != 0:
                DP[i+1][k+1][True] += DP[i][k][False]*(int(Nstr[i])-1)
                DP[i+1][k+1][True] += DP[i][k+1][False]
            else:
                DP[i+1][k+1][True] += DP[i][k+1][False]
            if i+1 == k+1:
                DP[i+1][k+1][False] = 1
    print(DP[M][K][True]+DP[M][K][False])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = str(next(tokens))  #
    K = int(next(tokens))  # type: int
    solve(N, K)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = input()
K = int(input())
len_n = len(n)
ans = 0
#自由な数字を選んでいいのかどうか？、今の桁数,今の答え  
def calc(free, count, now):
    global ans
    if count == K:
        ans += 1
        return
    if now == len_n:
        return 
    if free:
        for _ in range(9):
            calc(free, count + 1, now+1)
        #この数字を0にするとき
        calc(free, count, now+1)
    else:
        #自由に数字選べない時
        for _ in range(int(n[now])-1):
            calc(not free, count + 1, now+1)
        #このすうじを0にする
        calc(not free, count, now+1)
        #この数字を元の数字と同じ
        calc(free, count+1, now+1)
calc(False, 0,0)
print(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):
    bl = len(S)
    return int(S[0])+9*(bl-1)

def calc2(S):
    bl = len(S)
    ans = 0
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに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:
import math

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


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

def count(num_str,k):
    digits = len(num_str)
    if digits == 1 and k == 1:
        return int(num_str)
    elif digits == 1 and k > 1:
        return 0
    elif k == 0:
        return 1
    if num_str[0] == '0':
        count_0 = 0
        count_1 = 0
    else:
        if digits >= k+1:
            count_0 = combinations_count(digits-1,k)*(9**k)
        else:
            count_0 = 0
        count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
    return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(n),k))

Submission status: Wrong Answer

Solution code:
N=input()
K=int(input())
m=len(N)
a=0
if K==3:
    for i in range(1,m-2):
        a+=i*(i+1)
    a//=2
    a*=729
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                for b in range(m-2):
                    for c in range(m-2-b):
                        if N>=str(i)+"0"*b+str(j)+"0"*c+str(k)+"0"*(m-3-b-c):
                            a+=1
elif K==1:
    if int(N)<10:
        a=int(N)
    else:
        a=9
        for i in range(2,m):
            a+=9*(i-1)
        for i in range(1,10):
            if N>=str(i)+"0"*(m-1):
                a+=1
else:
    for i in range(1,m-1):
        a+=i
    a*=81
    for i in range(1,10):
        for j in range(1,10):
            for k in range(m-1):
                if N>=str(i)+"0"*k+str(j)+"0"*(m-2-k):
                    a+=1
print(a)

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s, t = input().split()
    a, b = LI()
    u = input()
    if u == s:
        print("{} {}".format(a - 1, b))
    elif u == t:
        print("{} {}".format(a, b - 1))
    return


# B
def B():
    s = input()
    print('x' * len(s))
    return


# C
def C():
    n = I()
    a = LI()
    s = set()
    for i in a:
        s.add(i)
    if len(s) == n:
        print('YES')
    else:
        print('NO')
    return


# D
def D():
    N, K = LI()
    p = LI()
    map_p = list(map(lambda x: (1 + x), p))
    cumsum_p = [0] * N
    ans_p = [0] * N
    cumsum_p[0] = map_p[0]
    ans_p[0] = map_p[0]
    for i in range(1, N):
        cumsum_p[i] = cumsum_p[i - 1] + map_p[i]
        ans_p[i] = ans_p[i - 1] + map_p[i]
    for i in range(K, N):
        ans_p[i] -= cumsum_p[i - K]
    print(max(ans_p[K - 1:]) / 2.0)
    return


# E
def E():
    N = list(map(int, list(input())))
    K = I()
    l = len(N)
    if K == 1:
        ans = N[0] + 9 * (l - 1)
        print(ans)
    elif K == 2:
        if l < 2:
            print(0)
            return
        ans = (l - 1) * (l - 2) * 81 // 2 + N[0] * 9 * (l - 1) - (9 - N[1])
        print(ans)
    elif K == 3:
        if l < 3:
            print(0)
            return
        ans = (l - 1) * (l - 2) * (l - 3) * (9 ** 3) // 6 + N[0] * (l - 1) * (l - 2) * 81 // 2 - (9 - N[1]) * 9 - (9 - N[2])
        print(ans)
    return


# F
def F():
    return


# Solve
if __name__ == "__main__":
    E()

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


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



print(int(ans)+1)

Submission status: Wrong Answer

Solution code:
import sys
n=list(input())
N=len(n)
k=int(input())
dp=[[0 for i in range(len(n))] for j in range(k)]
ans=0
x=int(n[0])
if N<k:
  print(0)
  sys.exit()

if k==1:
  ans+=(N-1)*9
  ans+=x
  print(ans)
  sys.exit()

elif k==2:
  ans+=(N-1)*(N-2)*81//2
  ans+=(x-1)*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans+=(N2-1)*9
  ans+=x
  print(ans)
  sys.exit()

else:
  ans+=(N-1)*(N-2)*(N-3)*729//6
  ans+=(x-1)*(N-1)*(N-2)*81//2
  n=n[1:N+1]
  N=len(n)
  x=int(n[0])
  ans2=0
  ans2+=(N-1)*(N-2)*81//2
  ans2+=(max(x-1,0))*(N-1)*9
  n2=n[1:N+1]
  N2=len(n2)
  x=int(n2[0])
  ans2+=(N2-1)*9
  ans2+=x
  ans+=ans2
  print(ans)
  sys.exit()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

N = readline().strip()
K = int(readline())

MM = [9, 81, 9 ** 3]

def comb(n, k):
    a = 1
    for i in range(k):
        a *= n - i
    
    for i in range(k):
        a = a // (i + 1)
    
    return a

def xxx(N, K):
    L = len(N)
    if L <= K - 1:
        return 0
    
    if K == 0:
        return 1
    
    a = comb(L - 1, K) * MM[K - 1]

    b = int(N[0]) - 1
    a += b * comb(L - 1, K - 1) * MM[K - 2] if K >= 2 else b
    
    a += xxx(N[1:], K - 1)
    return a

print(xxx(N, K))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
l = len(str(N))
K = int(input())
if l>=K:
    t = (math.factorial(l) // (math.factorial(l-K) * math.factorial(K)))*(9**K)
    t2 = math.factorial(l-1) // (math.factorial(l-K) * math.factorial(K-1))
    t2 = t2*(9-int(str(N)[0]))*(9**(K-1))
    print(t-t2)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

N = readline().strip()
K = int(readline())

MM = [9, 81, 9 ** 3]

def comb(n, k):
    a = 1
    for i in range(k):
        a *= n - i
    
    for i in range(k):
        a = a // (i + 1)
    
    return a

def xxx(N, K):
    L = len(N)
    if L <= K - 1:
        return 0
    
    if K == 0:
        return 1
    
    a = comb(L - 1, K) * MM[K - 1]

    b = int(N[0]) - 1
    a += b * comb(L - 1, K - 1) * MM[K - 2] if K >= 2 else b
    
    a += xxx(N[1:], K - 1)
    print(N, K, a)
    return a

print(xxx(N, K))

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
INF = float("inf")

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

len_n = len(str(n))
if len_n < k:
    print(0)
    exit()

base = [[0]*4 for _ in range(100)]
for i in range(4):
    base[i][0] = 0

for i in range(100):
    base[i][0] = 1
for i in range(1, 100):
    base[i][1] = 9 * i
for i in range(2, 100):
    base[i][2] = 9 * 9 * i*(i-1)//2
for i in range(3, 100):
    base[i][3] = 9 * 9 * 9 * i * (i - 1) * (i-2) // 6

ans = 0
len_n = len(str(n))
n_str = str(n)

for i in range(len(n_str)):
    if int(n_str[i]) > 0:
        ans += (int(n_str[i])-1)*base[len_n-1][k-1] + base[len_n-1][k]
        # print(ans)
        k -= 1
    len_n -= 1
    if k == 0:
        break

print(ans+1)

Submission status: Wrong Answer

Solution code:
N=input()
k=int(input())
ln=len(N)
DP=[[[0]*2 for _ in range(k+1)] for _ in range(len(N)+1)]
DP[0][0][0]=1
for i in range(1,len(N)+1):
  DP[i][0][1]=1
for i in range(len(N)):
  ni=int(N[i])
  for j in range(1,k+1):
    DP[i+1][j][1]=DP[i][j][1]+max(0,ni-1)*DP[i][j-1][0]+9*DP[i][j-1][1]+DP[i][j][0]
    if ni==0:
      DP[i+1][j][0]=DP[i][j][0]
    else:
      DP[i+1][j][0]=DP[i][j-1][0]
print(DP[ln][k][0]+DP[ln][k][1])

Submission status: Wrong Answer

Solution code:
N=input()
K=int(input())
l=len(N)
dp=[[0]*(l+1) for i in range(K+1)]
dp[0][0]=1
for i,n in enumerate(N):
    n=int(n)
    dp[0][i+1]=dp[0][i]
    for j in range(1,K+1):
        dp[j][i+1]=dp[j][i]+dp[j-1][i]*9 if i-j>-1 else 0 if i-j<-1 else n if i==0 else (dp[j-1][i]-1)*9+n
print(dp[-1][-1])

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=[0]*3
cnt=0
for i in range(keta):
    if str(n)[i]!=0:
        nonzero[cnt]=int(str(n)[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:
    ans+=nonzero[1]+(int(str(n)[0])-1)*9
    ans+=int(str(n)[0])*(keta-2)*9
    ans+=combinations_count(keta-1,k)*81
if k==3:
    if nonzero[1]==0:
        ans+=9
    ans+=nonzero[2]+(nonzero[1]-1)*9+(int(str(n)[0])-1)*81
    ans+=int(str(n)[0])*nonzero[1]*(keta-k)*9
    ans+=int(str(n)[0])*combinations_count(keta-2,2)*81
    ans+=combinations_count(keta-1,k)*81*9
print(ans)