Problem:


Score : 500 points

Problem Statement

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

1 \leq N < 10^{100}

1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

19

The following 19 integers satisfy the condition:

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Sample Input 2

25
2

Sample Output 2

14

The following 14 integers satisfy the condition:

11,12,13,14,15,16,17,18,19,21,22,23,24,25

Sample Input 3

314159
2

Sample Output 3

937

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300



Sample input:
100
1


Sample output:
19

Submission status: Wrong Answer

Solution code:
def resolve():
    s = input()
    N = int(s)
    K = int(input())
    ans = 0
    d = len(s)
    if d < K:
        print(ans)
        return
    for i in range(1, d):
        if i < K:
            continue
        else:
            if i == 1 and K == 1:
                ans += 9
            elif i == 2 and K == 2:
                ans += 9*9
            elif i == 3 and K == 3:
                ans += 9*9*9
            else:
                if K == 1:
                    ans += 9
                elif K == 2:
                    ans += 9*9*(i-1)
                else:
                    ans += 9*9*9*(i-1)*(i-2)//2
    # print(ans)
    if K == 1:
        ans += int(s[0])
    elif K == 2:
        ans += int(s[1])
        if int(s[0]) > 1:
            ans += (int(s[0])-1)*9
        if d > K and int(s[1]) > 0:
            ans += int(s[0])*(d-2)*9
    else:
        ans += int(s[2])
        if int(s[1]) > 1:
            ans += (int(s[1])-1)*9
            if int(s[0]) > 1:
                ans += (int(s[0])-1)*9*9
        if d > K:
            if int(s[1]) > 0:
                ans += int(s[1])*(d-3)*9
                if int(s[0]) > 1:
                    ans += (int(s[0])-1)*9*(d-3)*9
            if int(s[2]) > 0:
                ans += int(s[1])*(d-3)*9
                if int(s[0]) > 1:
                    ans += (int(s[0])-1)*9*(d-3)*9
            if d > K+1 and int(s[1]) > 0 and int(s[2]) > 0:
                ans += int(s[0])*9*9*(d-3)*(d-4)//2
    print(ans)
resolve()

Submission status: Wrong Answer

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

from itertools import combinations


def get_n(maxv, ln):
    n = 0

    if ln == 3:
        for i0 in range(1, 10):
            if i0 > maxv//100:
                continue
            for i1 in range(1, 10):
                for i2 in range(1, 10):
                    v = i0 * 100
                    v += i1 * 10
                    v += i2
                    if v <= maxv:
                        n += 1

    if ln == 2:
        for i0 in range(1, 10):
            for i1 in range(1, 10):
                v = i0 * 10
                v += i1
                if v <= maxv:
                    n += 1

    if ln == 1:
        for i0 in range(1, 10):
            v = i0
            if v <= maxv:
                n += 1
    return n


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

    d_n = len(N)
    c_list = [i for i in range(d_n)]

    combs = list(combinations(c_list, K))

    total = 0

    for comb in combs:

        if comb == (0, 1, 2):
            maxv = int(N[int(comb[0])]+N[int(comb[1])]+N[int(comb[2])])
            n = get_n(maxv, 3)

        elif comb[0:2] == (0, 1):
            if len(comb) == 3:
                maxv = int(N[int(comb[0])]+N[int(comb[1])]+"9")
            else:
                maxv = int(N[int(comb[0])]+N[int(comb[1])])
            n = get_n(maxv, len(comb))

        elif comb[0] == 0:
            maxv = int(N[int(comb[0])]+"9"*(len(comb)-1))
            n = get_n(maxv, len(comb))

        else:
            n = 9 ** len(comb)

        total += n

    print(total)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def gcd(x, y):
    while(y): 
        x, y = y, x % y 
    return x
def NcR(n, r): 
    p = 1
    k = 1
    if (n - r < r): 
        r = n - r 
  
    if (r != 0):  
        while (r): 
            p *= n 
            k *= r 
            m = gcd(p, k) 
            p //= m 
            k //= m  
            n -= 1
            r -= 1
    else: 
        p = 1
    return p

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#import itertools
#import numpy as np
import math

n = int(input())
k = int(input())
sn = str(n)
l = len(sn) # 10^(l-1) < n < 10^l
ans = 0
z = 0

def combinations_count(n, r):
    x = 1
    for y in range(n-r+1, n+1):
        x *= y
    for z in range(1, r+1):
        x //= z
    return x
    
if k <= l-1:
    ans += combinations_count(l-1, k) * (9 ** k)

    # l桁の整数について
    if k == 1:
        z = int(sn[0])
        
    elif k == 2:
        z = (int(sn[0])-1) * (l-1)*9
        z += int(sn[1])
        z += (l-2) * 9
        
    else:
        z = (int(sn[0])-1) * combinations_count(l-1, 2)*81
        for i in range(l-2):
            z += int(sn[i+1]) * sum(list(map(int, list(sn[i+2:]))))

print(ans + z)

Submission status: Wrong Answer

Solution code:
def resolve():
    s = input()
    N = int(s)
    K = int(input())
    ans = 0
    d = len(s)
    if d < K:
        print(ans)
        return
    for i in range(1, d):
        if i < K:
            continue
        else:
            if i == 1 and K == 1:
                ans += 9
            elif i == 2 and K == 2:
                ans += 9*9
            elif i == 3 and K == 3:
                ans += 9*9*9
            else:
                if K == 1:
                    ans += 9
                elif K == 2:
                    ans += 9*9*(i-1)
                else:
                    ans += 9*9*9*(i-1)*(i-2)//2
    # print(ans)
    if K == 1:
        ans += int(s[0])
    elif K == 2:
        ans += int(s[1])
        if int(s[0]) > 1:
            ans += (int(s[0])-1)*9
        if d > K:
            ans += int(s[0])*(d-2)*9
    else:
        ans += int(s[2])
        if int(s[1]) > 1:
            ans += (int(s[1])-1)*9
            if int(s[0]) > 1:
                ans += (int(s[0])-1)*9*9
        if d > K:
            if int(s[1]) > 0:
                ans += int(s[1])*(d-3)*9
                if int(s[0]) > 1:
                    ans += (int(s[0])-1)*9*(d-3)*9
            if int(s[2]) > 0:
                ans += int(s[1])*(d-3)*9
                if int(s[0]) > 1:
                    ans += (int(s[0])-1)*9*(d-3)*9
            if d > K+1 and int(s[1]) > 0 and int(s[2]) > 0:
                ans += int(s[0])*9*9*(d-3)*(d-4)//2
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

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


def main():
    n = II()
    k = II()
    keta = []
    l = n
    while True:
        amari = l % 10
        keta.append(amari)
        l = l // 10
        if l < 1:
            break

    if len(keta) < k:
        print(0)
        return

    ans = 0
    for i in range(1, len(keta)):
        if i < k:
            continue
        ans += cmb(i - 1, k - 1) * pow(9, k)
    ans += cmb(len(keta) - 1, k - 1) * pow(9, k-1) * (keta[-1] - 1)
    if k == 1:
        print(ans + 1)
    elif k == 2:
        for i in range(len(keta)-1):
            if sum(keta[i+1:-1]) == 0:
                ans += keta[i]
            else:
                ans += 9
        print(ans)


    else:
        for i in range(len(keta)-1):
            for j in range(i+1, len(keta)-1):
                print(i, j)
                if sum(keta[j+1:-1]) == 0:
                    if keta[j] == 0:
                        continue

                    ans += (keta[j] - 1) * 9
                    if sum(keta[i+1:j]) == 0:
                        ans += keta[i]
                    else:
                        ans += 9
                    print(ans)
                else:
                    ans += 81

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    s = input()
    N = int(s)
    K = int(input())
    ans = 0
    d = len(s)
    if d < K:
        print(ans)
        return
    for i in range(1, d):
        if i < K:
            continue
        else:
            if i == 1 and K == 1:
                ans += 9
            elif i == 2 and K == 2:
                ans += 9*9
            elif i == 3 and K == 3:
                ans += 9*9*9
            else:
                if K == 1:
                    ans += 9
                elif K == 2:
                    ans += 9*9*(i-1)
                else:
                    ans += 9*9*9*(i-1)*(i-2)//2
    # print(ans)
    if K == 1:
        ans += int(s[0])
    elif K == 2:
        ans += int(s[1])
        if int(s[0]) > 1:
            ans += (int(s[0])-1)*9
        if d > K:
            ans += int(s[0])*(d-2)*9
    else:
        ans += int(s[2])
        if int(s[1]) > 1:
            ans += (int(s[1])-1)*9
            if int(s[0]) > 1:
                ans += (int(s[0])-1)*9*9
        if d > K:
            if int(s[1]) > 0:
                ans += int(s[1])*(d-3)*9
                if int(s[0]) > 1:
                    ans += (int(s[0])-1)*9*(d-3)*9
            if int(s[2]) > 0:
                ans += int(s[1])*(d-3)*9
                if int(s[0]) > 1:
                    ans += (int(s[0])-1)*9*(d-3)*9
            if d > K+1:
                ans += int(s[0])*9*9*(d-3)*(d-4)//2
    print(ans)
resolve()

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 * 9 * (((i-1) * (i-2)) // 2)
        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 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
    if point2 == 99:
        print(ans)
        exit()
    for i in range(point2,100):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0
    if point3 == 999:
        print(ans)
        exit()
    for i in range(point3,1000):
        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
n = int(input())
k = int(input())
keta = len(str(n))
from math import factorial
if k <= keta:
    diff = 0
    if k == 2:
        diff += (9-int(str(n)[0]))*9*(keta-1)
        diff += 9-int(str(n)[1])
    elif k == 3:
        if keta == 3:
            c = 1
        else:
            c = (factorial(keta-1) / factorial(k) / factorial(keta-1 - k))
        diff += (9-int(str(n)[0]))*81*c
        if keta == 3:
            c = 1
        else:
            c = (factorial(keta-2) / factorial(k) / factorial(keta-2 - k))
        diff += (9-int(str(n)[1]))*9*c
        if int(str(n)[1]) != 0:
            diff += 9-int(str(n)[2])
    elif k == 1:
        diff += 9-int(str(n)[0])
    al = (factorial(keta) / factorial(k) / factorial(keta - k)) * (9**k)
    ans = int(al-diff)
    if ans >= 0:
        print(ans)
    else:
        print(0)
else:
    print(0)

Submission status: Wrong Answer

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

from math import factorial as f
def ncr(n,r):
  return f(n)//(f(r)*f(n-r)) if n>=r else 0

cnt = 1
l = []
for i in n:
  if int(i) > 0:
    l.append([len(n)-cnt,int(i)-1])
    if len(l) > 2:
      break
  cnt += 1

ans = 1
ans += ncr(l[0][0],k)*(9**k) + l[0][1]*ncr(l[0][0],k-1)*(9**(k-1))
if k>1 and len(l)>1:
  ans += ncr(l[1][0],(k-1))*(9**(k-1)) + l[1][1]*ncr(l[1][0],k-2)*(9**(k-2))
if k>2 and len(l)>2:
  ans += ncr(l[2][0],(k-2))*(9**(k-2)) + l[2][1]*ncr(l[2][0],k-3)*(9**(k-3))
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 and int(str(i)+str(j))<100:
                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 and int(str(i)+str(j)+str(k))<1000:
                    b+=1
                elif int(str(i)+str(j)+str(k))<z*100+100 and int(str(i)+str(j)+str(k))<1000:
                    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)*b
                        w2=combinations_count(len(n)-2,2)*c
                        print(a*v+(729-a)*w+w1+w2)
                    else:
                        print(a*v)
                    exit()
else:
    print(0)

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+=(nonzero[1][1]-1)*9
        ans+=(int(str(n)[0])-1)*(keta-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
    elif len(nonzero)==2:
        ans+=int(str(n)[0])*(nonzero[1][0]-1)*(nonzero[1][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[1][1]-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
    else:
        ans+=(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:
# coding: utf-8

from math import factorial as fact
# import copy

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

digit = len(str(N))

if len(str(N)) < K:
    print(0)
else:
    ans = 0
    while K > 0:
        for i in range(K, digit):  # i: 桁数
            ans += (fact(i-1) * (9**K)) // (fact(i-K) * fact(K-1))
            # print(ans)

        # print(ans)

        # 桁数がdigitのときのみ限界が存在
        str_n = str(N)

        # 最大の桁の数がhead-1までは同様
        ans += ((int(str_n[0])-1) * fact(digit-1) * (9**(K-1))) // (fact(digit-K) * fact(K-1))
        # print(int(str_n[0])-1)
        # print(fact(digit-1))
        # print((9**(K-1)))
        # print(ans)

        # def rec(i, extract, num, head, digit):
        #     global ans

        #     if len(extract) == num:
        #         tmp = 1
        #         for ext in extract:
        #             tmp *= ext
        #         ans += tmp
        #     elif i >= digit:
        #         pass
        #     else:
        #         new_extract = copy.copy(extract)
        #         new_extract.append(int(str_n[i]))
        #         rec(i+1, new_extract, num, head, digit)  # use
        #         rec(i+1, extract, num, head, digit)  # not use

        # rec(1, [], K-1, int(str_n[0]), digit)
        # print(str_n)
        if len(str_n) == 1:
            break
        N = int(str_n[1:])
        K -= digit - len(str(N))
        digit = len(str(N))

    print(ans+1)

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 and int(str(i)+str(j))<100:
                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,10):
        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 and int(str(i)+str(j)+str(k))<1000:
                    b+=1
                elif int(str(i)+str(j)+str(k))<z*100+100 and int(str(i)+str(j)+str(k))<1000:
                    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)*b
                        w2=combinations_count(len(n)-2,2)*c
                        print(a*v+(729-a)*w+w1+w2)
                    else:
                        print(a*v)
                    exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
def comb(n,k):
  if n == 0:
    return 0
  if n == k:
    return 1
  
  num = 1
  for i in range(n-k+1,n+1):
    num *= i
    
  for i in range(2,k+1):
    num //= i
    

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  print('tmp:', n,k,ans)
  return ans


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

print(syou(n, k))

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 += (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:
def resolve():
    s = input()
    N = int(s)
    K = int(input())
    ans = 0
    d = len(s)
    if d < K:
        print(ans)
        return
    for i in range(1, d):
        if i < K:
            continue
        else:
            if i == 1 and K == 1:
                ans += 9
            elif i == 2 and K == 2:
                ans += 9*9
            elif i == 3 and K == 3:
                ans += 9*9*9
            else:
                if K == 1:
                    ans += 9
                elif K == 2:
                    ans += 9*9*(i-1)
                else:
                    ans += 9*9*9*(i-1)*(i-2)//2
    # print(ans)
    if K == 1:
        ans += int(s[0])
    elif K == 2:
        ans += int(s[1])
        if int(s[0]) > 1:
            ans += (int(s[0])-1)*9
        if d > K:
            ans += int(s[0])*(d-2)*9
    else:
        ans += int(s[2])
        if int(s[1]) > 1:
            ans += (int(s[1])-1)*9
            if int(s[0]) > 1:
                ans += (int(s[0])-1)*9*9
        if d > K:
            if int(s[1]) > 0:
                ans += int(s[0])*int(s[1])*(d-3)*9
            if int(s[2]) > 0:
                ans += int(s[0])*int(s[1])*(d-3)*9
            if d > K+1:
                ans += int(s[0])*9*9*(d-3)*(d-4)//2
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
N=input()
n=int(N)
k=int(input())
ans=0
if k==1:
    for i in range(len(N)):
        if i>=2:
            ans+=1
        else:
            ans+=min(n,9)

elif k==2:
    for i in range(len(N)):
        if i<1:
            continue
        elif i==1:
            if n<100:
                ans=n-9-int(N[0])
            else:
                ans+=81
        elif i==len(N)-1:
            ans+=int(N[0])*9*(i-2)+int(N[0])*int(N[1])
        else:
            ans+=81*i
                



print(ans)

Submission status: Wrong Answer

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

dp1 = [ [ i+1 for i in range(9) ] for i in range(201)]
dp2 = [ [ 0 for i in range(9) ] for i in range(201)]
dp3 = [ [ 0 for i in range(9) ] for i in range(201)]

for i in range(200):
    for j in range(9):
        if j == 0:
            dp1[i+1][j] = dp1[i][-1] + 1
        else:
            dp1[i+1][j] = dp1[i+1][j-1] + 1

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp3[i+1][j] = dp3[i][-1] + 81 * i*(i-1)//2
        else:
            dp3[i+1][j] = dp3[i+1][j-1] + 81 * (i+1) * i //2


def solve(s, x):
    if s[0] == "0":
        return 0
        


    if x == 1:
        if len(s) == 1:
            return dp1[0][int(s) - 1]

        return  dp1[len(s)-1][int(s[0]) - 1]
    elif x == 2:
        if len(s) == 1:
            return dp2[0][int(s) - 1]
        return  dp2[len(s)-1][int(s[0]) - 1] + solve(s[1:], 1)
    elif x == 3:
        if len(s) == 1:
            return dp3[0][int(s) - 1]
        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

Submission status: Wrong Answer

Solution code:
''' Hey stalker :) '''
INF = 10**10
def main():
    #print = out.append
    ''' Cook your dish here! '''
    n = list(input())
    k = get_int()
    ln = len(n)
    ans = 0
    def solve(nz, ind, locked = False):
        if nz == 0: return 1
        if ind>=ln: return 0
        num = int(n[ind])
        ans = 0
        for index in range(ind,ln):
            if locked and ind==index:
                if num==0: return 0
                ans += solve(nz-1, index+1, True)
                ans += solve(nz-1, index+1)*(num-1)
            else: ans += solve(nz-1, index+1)*9
        #print(nz, ind, locked, ans)
        return ans

    ans = solve(k,0, True)
    print(ans)





''' Pythonista fLite 1.1 '''
import sys
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right
#from functools import reduce
import math
#input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()
#[main() for _ in range(int(input()))]
print(*out, sep='\n')

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)*b
                        w2=combinations_count(len(n)-2,2)*c
                        print(a*v+(729-a)*w+w1+w2)
                    else:
                        print(a*v)
                    exit()
else:
    print(0)

Submission status: Wrong Answer

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

d = len(str(n))

dp = [[[0]*10 for i in range(4)] for j in range(110)]
dp[0][0][0] = 1
dp[1][0][0] = 1

for i in range(1, 110):
  for j in range(1, 4):
    for p in range(10):
      if p != 0:
        dp[i][j][p] = sum(dp[i-1][j-1])
      else:
        dp[i][j][p] = sum(dp[i-1][j]) 
      
#print(dp[0])
#print(dp[1])
#print(dp[2])
#print(dp[6])

n_ = str(n)
ans = 0

for i in range(d):
  a = d - i #桁
  b = int(n_[i])
  for x in range(b):
    ans += dp[a][max(k-i, 0)][x]
  #print(ans)
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
            if n[1]>0:
                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()