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:
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] == "00":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-3)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
import sys
import math
from itertools import combinations, permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


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


N, K = map(int, read().split())
l = len(str(N))
ll = list(range(l))

ans = 0
for v in combinations(ll, K):
    if v[0] != 0:
        ans += 9**K
    if len(v) >= 2:
        if v[0] == 0 and v[1] != 1:
            ans += int(str(N)[0]) * 9**(K - 1)
        else:
            ans += (int(str(N)[0]) - 1) * 9**(K - 1)
            ans += int(str(N)[1]) - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n=input()
k=int(input())
if len(n)>=3:
    x=int(n[0]+n[1]+n[2])
if len(n)>=2:
    y=int(n[0]+n[1])
z=int(n[0])

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

# k==1のもの数える
if k==1:
    print(z*len(n)+(9-z)*(len(n)-1))

elif k==2 and len(n)>=2:
    a=0
    b=0
    for i in range(1,11):
        for j in range(1,10):
            if int(str(i)+str(j))<=y:
                a+=1
            elif int(str(i)+str(j))<y-int(n[1])+10:
                b+=1
            else:
                v=combinations_count(len(n),2)
                if len(n)>=3:
                    w=combinations_count(len(n)-1,2)
                    w1=b*(len(n)-2)
                    print(a*v+(81-a)*w+w1)
                else:
                    print(a*v)
                exit()

elif k==3 and len(n)>=3:
    a=0
    b=0
    c=0
    for i in range(1,11):
        for j in range(1,10):
            for k in range(1,10):
                if int(str(i)+str(j)+str(k))<=x:
                    a+=1
                elif int(str(i)+str(j)+str(k))<y*10+10:
                    b+=1
                elif int(str(i)+str(j)+str(k))<z*100+100:
                    c+=1

                else:
                    v=combinations_count(len(n),3)
                    if len(n)>=4:
                        w=combinations_count(len(n)-1,3)
                        w1=combinations_count(len(n)-1,2)
                        w2=combinations_count(len(n)-2,2)
                        print(b*v+(729-b)*w+w1*b+w2*c)
                    else:
                        print(b*v)
                    exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r==1 or n==r==0:
    return 1
  else:
    return 0
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    if not_zero==K:
      ans+=1
print(int(ans))

Submission status: Wrong Answer

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


if k==1:
    icnt=0
    for i in range(0,99):
        for i1 in range(1,10):
            x=i1*10**i
            if x<=n:
                icnt=icnt+1
    print(icnt)
elif k==2:
    icnt=0
    for i in range(0,99):
        for j in range(i+1,99):
            for i1 in range(1,10):
                for j1 in range(1,10):
                    x=i1*10**i+j1*10**j
                    if x<=n:
                        icnt=icnt+1
    print(icnt)
elif k==3:
    icnt=0
    for i in range(0,99):
        for j in range(i+1,99):
            for m in range(j+1,99):
                for i1 in range(1,10):
                    for j1 in range(1,10):
                        for m1 in range(1,10):
                            x=i1*10**i+j1*10**j+m1*10**m
                            if x<=n:
                                icnt=icnt+1
    print(icnt)

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) < k:
        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:
def func(p):
    r=0
    for q in range(2,p-1):
        r+=q*(q-1)//2
    return r

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

n=len(str(N))
x=int(str(N)[0])
l=0
y=0
z=0
if n>=2:
    for i in range(1,n):
        if str(N)[i]==0:
            l+=1
        else:
            y=int(str(N)[i])
            if i<n-1:
                z=int(str(N)[i+1])


s=0
if n-l-2>0:
    s=(n-l-1)*(n-l-2)//2

ans=0

if K==1:
    ans=x+9*(n-1)

elif K==2:
    ans=y+9*max(0,x-1)+9*max(0,n-l-2)+81*(n-2)*(n-1)//2

else:
    ans=y*z+x*81+x*81*s+729*func(n)

print(ans)

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)
    print(ans-delay)

Submission status: Wrong Answer

Solution code:
n=input();l=len(n)
k=int(input());x=0;c=-1;y=-1
for i in range(1,l):
  if int(n[i]):
    c=i
    continue
  if c!=-1 and int(n[i]):
    y=i
    break
if k==1:
  x=(l-1)*9 + int(n[0])
elif k==2 and l>1:
  x=81*(l-1)*(l-2)//2+9*(int(n[0])-1)*(l-1)+(int(n[c])+(l-c-1)*9 if c!=-1 else 0)
elif l>2:
  x=729*(l-3)*(l-2)//2+9*(int(n[0])-1)*(l-1)+(int(n[c])+(l-c-1)*9 if c!=-1 else 0)
print(x)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = int(input())
n = len(str(N))
ans = 0

def com(n,k):
  a = n
  b = k
  for i in range(K-2):
    a = a*(n-(i+1))
    b = b*(k-(i+1))
  return a//b

def count(n,K):
  if n < K:
    return 0
  elif n == K:
    return 9**K
  elif n > K and K == 1:
    return 9
  elif n > K and K != 1:
    a = n-1
    b = K-1
    for i in range(K-2):
      a = a*(n-1-(i+1))
    for j in range(K-2):
      b = b*(K-1-(j+1))
    C = a//b
    return C*(9**K)

for i in range(n-1):
  ans += count(i+1,K)

M = str(N)
if n == 1:
  if K == 1:
    ans += int(M[0])
  else:
    ans += 0
elif n == 2:
  s,t = int(M[0]),int(M[1])
  if K == 2:
    ans = ans + (s-1)*(9*(n-1)) + 9*(n-2) + t
  else:
    ans += 0
  
elif n >= 3:
  s,t,u = int(M[0]),int(M[1]),int(M[2])
  if K == 1:
    ans += s
  elif K == 2:
    ans = ans + (s-1)*(9*(n-1)) + 9*(n-2) + t
  elif K == 3:
    ans = ans + (s-1)*(9**2)*com(n-1,K-1) + (9**(K-1))*com(n-2,K-1) + (t-1)*9*(n-2) + 9*(n-3) + u

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def binomial_coefficient(n, r, mod=10**9+7):
    """
    二項係数nCr, (n,r)をmodで除したあまりを返す
    """
    res = 1
    div = 1
    r = min(r, n - r)
    for i in range(r):
        res *= (n - i) % mod
        div *= (i + 1) % mod
    res *= pow(div, mod - 2, mod)
    return res % mod


def calc(N, K):
    if K == 0:
        return 1
    if K > len(N):
        return 0
    if N[0] == 0:
        return calc(N[1:], K)

    res = 0

    # 一番上が0の時
    if len(N)-1 > K:
        res += binomial_coefficient(len(N) - 1, K) * (9 ** K)

    # 一番上が1~N[0]-1の時
    res += (int(N[0]) - 1) * calc(N[1:], K-1)

    # 一番上がN[0]のとき
    res += calc(N[1:], K-1)

    return res


if __name__ == "__main__":
    N = int(input())
    K = int(input())
    d = len(str(N))
    N = str(N)
    ans = calc(N, K)
    print(ans)

Submission status: Wrong Answer

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

N = str(N)
N_keta = len(N)
p = N[0]

if K == 1:
    kotae = int(p) + 9 * (int(N_keta)-1)
    print(int(kotae))

else:
    M = int(N) - int(p)*(10**(int(N_keta)-1))
    M = str(M)
    M_keta = len(M)
    q = M[0]
    if K == 2:
        if int(N) <= 9:
            print(0)
        else:
            kotae = 9 * (int(N_keta)-1) * (int(p)-1) + int(q) + 9 * (int(M_keta)-1) + (int(N_keta)-1)*(int(N_keta)-2)*40.5
            print(int(kotae))
    else:
        if int(N) <= 99:
            print(0)
        else:
             L = int(M) - int(q)*(10**(int(M_keta)-1))
             L = str(L)
             L_keta = len(L)
             r = L[0]
             kotae = 9 * (int(M_keta)-1) * (int(q)-1) + int(r) + 9 * (int(L_keta)-1) + (int(p)-1)*(int(N_keta)-1)*(int(N_keta)-2)*0.5*81+(int(N_keta)-1)*(int(N_keta)-2)*(int(N_keta)-3)*9**3/6
             print(int(kotae))

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

elif K==3:
    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:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
k = ii()
n2 = n

n_keta = 1
while n2:
    n2 = n2 //10
    if n2 == 0:
        break
    n_keta += 1

from math import factorial as fc
def func(keta,kazu,ima):
    ans = 0
    n = n_keta - keta -1
    r =  k - kazu
    if n-r <0:
        return 0
    ans += (ima-1) *fc(n) //fc (r)//fc(n-r)  * (9 **(k-kazu))
    if n - r -1 >= 0: ans += fc(n) // fc (r+1) // fc(n-r-1) *(9**(k-kazu +1))
    return ans
n_in = str(n)
kk = 0
lis = []

for i in range(n_keta):
    if n_in[i] != 0:
        lis.append([i,kk+1,int(n_in[i])]) 
        kk += 1
    if kk ==k:
        break
anss = 0
for lil in lis:
    anss += func(lil[0],lil[1],lil[2])
print(max(int(anss+1),1))

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
from itertools import combinations
N = int(input())
K = int(input())

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

l = len(str(N))
ans = 0
for i in range(1, l):
    if i < K:
        continue
    if i == K:
        ans += 9 ** K
    else:
        ans += comb(i-1, K-1, exact=True) * (9 ** K)
N_str = list(str(N))

keta = l
num = [i for i in range(1, keta)]
if K == 1:
    ans += int(N_str[0])
else:
    ans += comb(keta-1, K-1, exact=True) * (9 ** (K-1)) * (int(N_str[0]) - 1)
    for v in combinations(num, K-1):
        add = 1
        for j in v:
            add *= int(N_str[j])
        ans += add
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

def nCk(N, K):
    if K > n or K < 0:
        return 0
    return fact[N] // fact[K] // fact[N-K]


def digits(N):
    N = abs(N)
    ret = 0
    x = 1
    while x <= N:
        ret += 1
        x *= 10
    return ret

fact = [1]
for i in range(1, 101):
    fact += [fact[i-1] * i]

digit = digits(n)
ans = 0
k9 = 9 ** k
for i in range(k, digit):
    ans += k9 * nCk(i - 1, k - 1)
ans += (n // (10**(digit-1)) - 1) * (k9//9) * nCk(digit-1, k-1)

if k == 1:
    print(ans+1)
    exit()
elif k == 2:
    n10 = n%(10**(digit-1))
    if n10 == 0:
        print(ans)
        exit()
    d = digits(n10)
    top = n10 // (10**(d-1))
    print(ans + top + 9 * (d-1))
elif k == 3:
    n10 = n%(10**(digit-1))
    if n10 == 0:
        print(ans+1)
        exit()
    d10 = digits(n10)
    n100 = n10%(10**(d10-1))
    if n100 == 0:
        top = n10 // (10**(d10-1))
        print(ans + (top-1) * 9 * (d10-1))
        exit()
    d100 = digits(n100)
    top = n10 // (10**(d10-1))
    sec = n100 // (10**(d100-1))
    print(ans + sec + 9 * (d100-1) + (top-1)*9*(d10-1) + 9 * 9 * nCk(d10-1, 2))

Submission status: Wrong Answer

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = input()
    K = int(input())
    L = len(N)
    ans = 0
    if int(N) < 1000:
        for k in range(1,int(N)+1):
            if str(k).count("0") + K == len(str(k)):
                ans += 1
    else:
        if K == 1:
            ans = int(N[0])+9*(L-1)
        elif K == 2:
            ans = (int(N[0])-1)*9*(L-1)
            ans += 9*9*((L-1)*(L-2)//2)
            ans += 9*(L-2) + int(N[1])
        else:
            ans = (int(N[0])-1)*9*9*((L-1)*(L-2)//2)
            ans += 9*9*9*((L-1)*(L-2)*(L-3)//6)
#            ans += (int(N[1])-1)*9*(L-2)
            ans += 9*9*((L-1)*(L-2)//2)
    print(ans)

if __name__ == '__main__':
    main()

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)%(10**9+7)
    return nCr[(n,r)]


N=input()
K=int(input()) #0以外の個数
x=len(N) #Nの桁数
cnt=0 #0以外の数カウント
ans=0

for i in range(x-1):
    a=i+1
    k=K
    if a-k<0:
        continue
    s=cmb(a-1,a-k)*9**k
    ans+=s

i=-1
while (cnt<3 and i<=x-2):
    i+=1 #現在の桁位置
    init=int(N[i]) #桁取り出し
    
    if i>0:
        a=x-i-1
        k=K-cnt
        if a-k>=0 and k>=0 and a>0:
            s=cmb(a,a-k)*9**k
            ans+=s
    
    if init!=0:
        cnt+=1
        a=x-i-1
        k=K-cnt
        if a-k>=0 and k>=0:
            if i!=x-1:
                s=(init-1)*cmb(a,a-k)*9**k
                ans+=s
            else:
                s=init*cmb(a,a-k)*9**k
                ans+=s
print(ans)

Submission status: Wrong Answer

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

ans = 0
if K == 1:
    for i in range(1,len(N)+1):
        if i != len(N):
            ans += 9
        else:
            ans += (int(N) // (10 ** (i-1)))
elif K == 2:
    for i in range(2, len(N)+1):
        if i != len(N):
            ans += 9 * 9 * (i-1)
        else:
            s = 0
            n = int(N) // (10 ** (i-1))
            ans += (n-1) * 9 * (i-1)
            for j in range(1,len(N)):
                if s == 0 and int(N[j]) == 0:
                    continue
                elif s == 1:
                    ans += 9
                else:
                    ans += int(N[j])
                    s = 1
elif K == 3:
    for i in range(3, len(N)+1):
        if i != len(N):
            ans += 9 * 9 * (i-1)
        else:
            s = 0
            n = int(N) // (10 ** (i-1))
            ans += (n-1) * 9 * 9 * (((i-1) * (i-2)) // 2)
            for j in range(1,len(N)):
                if s == 0 and int(N[j]) == 0:
                    continue
                elif s == 1:
                    ans += 9 * 9 * (((len(N)-j) * (max(len(N)-j-1, 0))) // 2)
                    break
                else:
                    ans += (int(N[j])-1) * 9 * (len(N)-j-1)
                    for k in range(j+1,len(N)):
                        if s == 0 and int(N[k]) == 0:
                            continue
                        elif s == 1:
                            ans += 9
                        else:
                            ans += int(N[k])
                            s = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def read():
    N = str(input().strip())
    K = int(input().strip())
    return N, K

def nCk(n, k):
    return len(list(itertools.combinations(range(n), k)))

def solve(N, K):
    L = len(N)
    count = 0
    factor = [1, 9**1, 9**2, 9**3]
    nonzero_counts = [len(str(i)) - str(i).count('0') for i in range(1000)]
    for d in range(L):
        if d == 0:
            if K >= 1:
                for i in range(1, int(N[0:1])):
                    count += (K-nonzero_counts[i]) * factor[K-1]
            if K >= 2:
                for i in range(10, int(N[0:2])):
                    count += (K-nonzero_counts[i]) * factor[K-2]
            if K >= 3:
                for i in range(100, int(N[0:3])):
                    count += (K-nonzero_counts[i]) * factor[K-3]
            count += 1
        else:
            # [0][1-9][0]*[1-9][0]*[1-9][0]*
            count += nCk(L-d-1, K-1) * factor[K]
    return count


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
def out_order1(N):
    return(9 * (len((str(N))) - 1) + int(str(N)[0]))
def out_order2(N):
    if(len(str(N)) >= 3):
        out = 9 * 9 * (len(str(N)) - 1) * (len(str(N)) - 2) / 2
        out += (int(str(N)[0]) - 1) * (len(str(N)) - 1) * 9
        N = str(N)
        N = N[1:]
        out += out_order1(int(N))
    elif(len(str(N)) == 2):
        out = (int(str(N)[0]) - 1) * 9 + (int(str(N)[1]))
    else:
        out = 0
    return(out)

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

if K == 1:
    out = out_order1(N)
elif K ==2:
    out = out_order2(N)
elif K == 3:
    if(len(str(N)) >= 4):
        out = 9 * 9 * 9 * (len(str(N)) - 1) * (len(str(N)) - 2) * (len(str(N)) - 3) / 6
        out += (int(str(N)[0]) - 1) * (len(str(N)) - 1) * (len(str(N)) - 2) * 9 * 9 / 2
        N = str(N)
        N = N[1:]
        out += out_order2(int(N))
    elif(len(str(N)) == 3):
        out = (int(str(N)[0]))
        N = str(N)
        N = N[1:]
        out += out_order2(int(N))
    else:
        out = 0
    
print(out)

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())
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:
import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r==1 or n==r==0:
    return 1
  else:
    return 0
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    if not_zero==K:
      ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

l = list(str(n))
for i in range(len(l)):
    l[i] = int(l[i])

comb_list = list(itertools.combinations(range(len(l)), k))

ans = 0
for comb in comb_list:
    # 最大桁を含む場合
    if comb[0] != 0:
        temp = 9 ** len(comb)
        ans += temp
    else:
        renzoku_flag = 0
        for i in range(len(comb) - 1):
            if comb[i+1] - comb[i] != 1:
                renzoku_flag = i
        for i in range(len(comb)):
            temp = 9 ** (len(comb) - 1)
            # 最大桁を含む
            if i > renzoku_flag:
                ans += temp
                temp //= 9
                continue
            if i == len(comb) - 1:
                ans += l[comb[i]]
            else:
                ans += (l[comb[i]]-1) * temp
            temp //= 9
    print(comb)
    print(ans)

print(ans)

Submission status: Wrong Answer

Solution code:
def func(p):
    r=0
    for q in range(2,p-1):
        r+=q*(q-1)//2
    return r

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

n=len(str(N))
x=int(str(N)[0])
l=0
y=0
z=0
if n>=2:
    for i in range(1,n):
        if str(N)[i]==0:
            l+=1
        else:
            y=int(str(N)[i])
            if i<n-1:
                z=int(str(N)[i+1])

print(l,y)

s=0
if n-l-2>0:
    s=(n-l-1)*(n-l-2)//2

ans=0

if K==1:
    ans=x+9*(n-1)

elif K==2:
    ans=y+9*max(0,x-1)+9*max(0,n-l-2)+81*(n-2)*(n-1)//2

else:
    ans=y*z+x*81+x*81*s+729*func(n)

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

def main():
    n = input()
    k = int(input())

    num = int(n)

    if k == 1:
        ans = (len(n)-1) * 9
        ans += int(n[0])
        print(ans)
        return

    elif k == 2:
        if num < 100:
            print(num-10-(int(n[0])-1))
            return
        else:
            ans = 0
            ans = int(n[1])+9*(len(n)-2)
            ans += (int(n[0])-1) * 9 * (len(n)-1)
            ans += 9*9 * combinations_count(len(n)-1, 2)
            print(ans)
            return

    elif k == 3:
        if num < 111:
            print(0)
            return
        elif num < 1000:
            ans = (int(n[0])-1) * 81
            ans += (int(n[1])-1) * 9
            # ans += (int(n[2]))
            print(ans)
            return
        else:
            n_len = len(n)
            ans = 9*9*9 * combinations_count(n_len-1, 3) # 一桁めが０
            ans += (int(n[1])-1) * (9*(n_len-2)) + int(n[2])+(9*(n_len-3)) # 一桁めがmax & 二桁めが1-9
            ans += (9*9) * combinations_count(n_len-2, 2) # 一桁めがmax & 二桁めが0
            ans += (int(n[0])-1) * (9*9)*combinations_count(n_len-1, 2) # 一桁めが1-<max
            print(ans)
            return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def Pika(p,K):
    tmp = 1
    now = p
    for i in range(K):
        tmp *= now
        now -= 1
    now = 1
    for i in range(K):
        tmp //= now
        now += 1
    tmp *= 9**K
    return tmp

N = input()
K = int(input())
p = len(N)
def solve(N,K,p):
    if K==0:
        return 1
    elif N=='':
        return 0
    ans = 0

    ans += Pika(p-1,K)

    atama = int(N[0])
    ans += (atama-1)*Pika(p-1,K-1)
    ans += solve(N[1:],K-1,p-1)
    
    return ans
A = solve (N,K,p)
print(A)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
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)]
mozi = input()
n = int(mozi)
k = int(input())
keta = len(mozi)
total = 0
for i in range(k, keta):
    total += (9 ** k) * cmb(i - 1, k - 1)
for i in range(0, keta - k):
    x = int(mozi[i])
    if x > 1:
        total += (x - 1) * (9 ** (k - 1)) * cmb(keta - 1 - i, k - 1)
    else:
        x += 1 
print(total)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = input()
m = len(n)
K = I()

dp1 = [[0]*101 for _ in range(m+1)] #等しい
dp2 = [[0]*101 for _ in range(m+1)] #n未満
dp2[0][0] = 1
for i in range(m):
    for j in range(10):
        if j > int(n[i]) and i == 0:
            continue
        if j > int(n[i]) and i != 0:
            for k in range(100):
                dp2[i+1][k+1] += dp2[i][k]
        elif j == 0 and n[i] == '0':
            for k in range(101):
                dp1[i+1][k] += dp1[i][k]
                dp2[i+1][k] += dp2[i][k]
        elif j == 0 and n[i] != '0':
            for k in range(101):
                dp2[i+1][k] += dp1[i][k]
                dp2[i+1][k] += dp2[i][k]
        elif j == int(n[i]):
            for k in range(100):
                dp1[i+1][k+1] += dp1[i][k]
                dp2[i+1][k+1] += dp2[i][k]
        elif j < int(n[i]):
            for k in range(100):
                dp2[i+1][k+1] += dp1[i][k]
                dp2[i+1][k+1] += dp2[i][k]
ans = dp1[-1][K] + dp2[-1][K]
print(ans)

Submission status: Wrong Answer

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

l = [[0,0,0]]
p1 = 0
p2 = 0
p3 = 0

for i in range(1, 1000):
    m = len(str(i)) - str(i).count("0")
    if m == 3:
        p3 += 1
    elif m == 2:
        p2 += 1
    else:
        p1 += 1
    l.append([p1,p2,p3])
if n <= 999:
    ans = l[n][k-1]

else:
    l2 = [l[9], l[99], l[999]]
    sn = str(n)
    keta = len(sn)
    a = int(sn[0])
    a2 = int(sn[1])
    a3 = int(sn[2])
    a4 = int(sn[3])
    for i in range(keta - 4):
        p1 = l2[-1][0] + 9
        p2 = l2[-1][1] + 9 * l2[-1][0]
        p3 = l2[-1][2] + 9 * l2[-1][1]
        l2.append([p1,p2,p3])
    if k == 1:
        ans = l2[-1][0] + a
    elif k == 2:
        ans = l2[-1][1] + (a - 1)* l2[-1][0] + l2[-2][0] + a2
    else:
        if a2 != 0:
            ans = l2[-1][2] + (a - 1)* l2[-1][1] + l2[-2][1] + (a2 - 1)* l2[-2][0] + l2[-3][0] + a3
        else:
            ans = l2[-1][2] + (a - 1)* l2[-1][1]
print(ans)