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
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
k=int(input())
keta=len(str(n))
tmpn=int(str(n)[:k]+("0"*(len(str(n))-k)))
# print(tmpn)
if k==2 and n<11:
    print(0)
    quit()
if k==3 and n<111:
    print(0)
    quit()
nonzero=[]
cnt=0
for i in range(keta):
    if str(n)[i]!="0":
        nonzero.append([int(str(n)[i]),keta-i])
        cnt+=1
    if cnt==k:
        break
# print(nonzero)
    

ans=0
def combinations_count(n, r):
    if n<0 or r<0 or n-r<0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if k==1:
    ans+=int(str(n)[0])
    ans+=(keta-1)*9
if k==2:
    if len(nonzero)==2:
        ans+=nonzero[1][0]+(int(str(n)[0])-1)*9
        ans+=int(str(n)[0])*(nonzero[1][1]-1)*9
        ans+=combinations_count(keta-1,k)*81
        ans+=(int(str(n)[0])-1)*(keta-1)*9
    else:
        ans+=(int(str(n)[0])-1)*(keta-1)*9
        ans+=combinations_count(keta-1,k)*81
if k==3:
    if len(nonzero)==3:
        ans+=nonzero[2][0]+(nonzero[1][0]-1)*9+(int(str(n)[0])-1)*81
        ans+=int(str(n)[0])*nonzero[1][0]*(nonzero[2][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[2][1],2)*81
        ans+=combinations_count(keta-1,k)*81*9
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
    elif len(nonzero)==2:
        ans+=int(str(n)[0])*(nonzero[1][0]-1)*(nonzero[1][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[1][1]-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
    else:
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:
def anss(N,K):
    c=0
    for i in range(1,N+1):
        if len(str(i))-str(i).count('0') == K:
            c+=1
    return c
def solve(p,n,k):
    if p == 0:
        return 0
    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())

N=str(N)
NN = [i for i in list(N) if i != '0']
dig = len(N) - 1

if K == 2:
    if len(NN) == 1:
        n0 = int(N[0])
        ans= (solve(n0,dig,2))
    else:
        n0 = int(N[0])
        for inn,nn in enumerate(N[1:]):
            if nn != '0':
                n1 = int(nn)
                break
        ans= (solve(n0,dig,2) + solve(n1,dig-inn-1,1))
elif K == 3:
    if len(NN) == 1:
        n0 = int(NN[0])
        ans=solve((n0),dig,3)
    elif len(NN) == 2:
        n0 = int(NN[0])
        n1 = int(NN[1])
        ans=solve((n0),dig,3) + solve(n1,dig-1,2)
    else:
        n0 = int(N[0])
        n1 = int(N[1])
        n2 = int(N[2])
        ans=solve((n0),dig,3) + solve(n1,dig-1,2) + solve(n2,dig-2,1)
elif K == 1:
    ans=(solve(int(N[0]),dig,1))
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = [int(x) for x in input()]
    K = int(input())
    dp = np.zeros((len(n)+1, 2, K+1), dtype=np.int64)

    if len(n) < K:
        print(0)
        return

    dp[0, 0, 0] = 1

    for i in range(len(n)):
        for k in range(0, K+1):
            # use 0
            dp[i+1, 1, k] += dp[i, 0, k] + dp[i, 1, k]
            for smaller in [0, 1]:
                # use 1~9
                r = 9 if smaller == 1 else n[i]
                for x in range(1, r+1):
                    if k+1 <= K:
                        dp[i+1, int(smaller == 1 or x < n[i]), k+1] += dp[i, smaller, k]
    print(dp[len(n), 0, K] + dp[len(n), 1, K])


if __name__ == '__main__':
    main()

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] + l2[-3][1] + (a3 - 1)* l2[-3][0] + l2[-4][0] + a4
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) * (9**(K-1)) * binomial_coefficient(len(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:
import re

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

count = 0

for num in range(1,N+1):
    num_str = str(num)
    num_str = re.sub("0", "", num_str)
    str_num = int(num_str)
    str_len = len(num_str)
    if str_num < num and str_len==K:
        count = count + 1
    elif str_num < 10 and str_len==K:
        count = count + 1

print(count)

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 solve(k, m, i):
    if i >= len(dp):
        if k == 0:
            return 1
        else:
            return 0

    if i == 0:
        #n[i]
        ans = solve(k - 1, 1, i + 1)
        ans += (int(str(n)[i]) - 1) * solve(k - 1, 0, i + 1)
        return ans

    if k == 0 :
        return 1

    ans = 0
    if m == 1:
        if k > 0:
            ans = dp[i][2] * solve(k - 1, 0, i + 1)
            ans += solve(k - 1, 1, i + 1)
            ans += solve(k, 0, i + 1)
    else:
        if k > 0:
            ans = 9 * solve(k - 1, 0, i + 1)
            ans += solve(k, 0, i + 1)


    return ans

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

dp = [[0 for _ in range(3)] for _ in range(len(str(n)))]

# dp[i][0]...0のパターン
# dp[i][1]...1~9
# dp[i][2]...~n[i] - 1

for i in range(len(str(n))):
    dp[i][1] = 9
    dp[i][2] = int(str(n)[i]) - 1

ans = 0
ans += solve(k, 1, 0)
if len(str(n)) - 1 >= k:
    ans += combinations_count(len(str(n)) - 1, k) * 9 ** k

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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


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:

def Main(N, K):
    ans = 0
    D = len(N)
    if K == 1:
        ans = 9*(D-1) + int(N[0])
    elif K == 2:
        if(D >= 3):
            ans = 9*9*(D-1) + 9*(D-2) + int(N[0]) + int(N[1])
        else:
            ans = 9*(D-1) + int(N[0])
    else:
        if(D >= 4):
            ans = 9*9*9*(D-1) + 9*9*(D-2) + 9*(D-1) +int(N[0]) + int(N[1]) + int(N[2])   
        elif(D == 3):
            ans = 9*9*(D-1) + 9*(D-2) + int(N[0]) + int(N[1])
        else:
            ans = 9*(D-1) + int(N[0])
    return ans
            
        
        

def main():
    N = str(input())
    K = int(input())
    print(Main(N, K))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math

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

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

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

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

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

print(int(ans+t_ans))

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+w2)
                    else:
                        print(b*v)
                    exit()
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
k = int(input())
sn = str(n)
keta = len(sn)
if k > keta:
    print(0)
    exit()

def one(sn, keta):
    result = 0
    
    result = (keta-1)*9
    for i in range(1, int(sn[0])+1):
        if '0' in str(i):
            continue
        if len(str(i)) != 1:
            continue
        result += 1
    return result

def two(sn, keta):
    result = 0
    
    mult = keta - 2
    if mult < 0:
        pass
    else:
        for m in range(1, mult+1):
            result += m*9*9

    for i in range(1, int(sn[0])+1):
        result += (keta-2)*9
        
        if i < int(sn[0]):
            result += 9
        else:
            for _ in range(int(sn[1])):
                result += 1
    return result

def three(sn, keta):
    result = 0
    
    mult = keta - 3
    if mult < 0:
        pass
    else:
        for m in range(1, mult+1):
            result += cmb(m+1, 2)*9*9*9

    for i in range(1, int(sn[0])+1):
        if i != int(sn[0]):
            result += cmb(keta-1, 2)*9*9
        else:
            for j in range(1, int(sn[1])+1):
                if j != int(sn[1]):
                    result += (keta-2)*9
                else:
                    result += (keta-3)*9
                    result += int(sn[2])
        
    return result

if k==1:
    print(one(sn, keta))
elif k==2:
    print(two(sn, keta))
else:
    print(three(sn, keta))

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)
        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
from io import StringIO
import unittest
from itertools import combinations

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


    a=list(range(0, 100))
    t=0

    if k==3:
        xx = combinations(a, k)
        for p in xx:
            if n<(10**p[0]+10**p[1]+10**p[2]):
                continue
            elif n>=(10**p[0]*9+10**p[1]*9+10**p[2]*9):
                t+=9*9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                        for k in range(1,10):
                            if n>=(10**p[0]*i+10**p[1]*j+10**p[2]*k):
                                t+=1
    elif k==2:
        xx = combinations(a, k)
        for p in xx:
            if n<(10**p[0]+10**p[1]):
                continue
            elif n>=(10**p[0]*9+10**p[1]*9):
                t+=9*9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                            if n>=(10**p[0]*i+10**p[1]*j):
                                t+=1
    elif k==1:
        xx = combinations(a, k)
        for p in xx:
            if n<(10**p[0]):
                continue
            elif n>=(10**p[0]*9):
                t+=9
            else:
                for i in range(1,10):
                    for j in range(1,10):
                            if n>=(10**p[0]*i):
                                t+=1


    print(t)

    return

resolve()

Submission status: Wrong Answer

Solution code:
import itertools
#nCr
import math
def com(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n=input()
k=int(input())
m=len(n)
if k==1:
    x=int(n[0])
    print(9*(m-1)+x)
    exit()
ans=0
x=int(n[0])
ans+=9**k*com(m-1,k)+(x-1)*com(m-1,k-1)*9**(k-1)
# print(9**k*com(m-1,k),(x-1)*com(m-1,k-1)*9**(k-1))
i=1
while i<m and n[i]=="0":
    i+=1
if k==3:
    if m<3:
        print(0)
        exit()
    if i==1:
        x=int(n[1])
        ans+=9**2*com(m-2,2)+(x-1)*com(m-2,1)*9
        ans+=int(n[2])+9*(m-3)
    if i==2:
        if m>=4:
            x=int(n[2])
            ans+=9**2*com(m-3,2)+(x-1)*com(m-3,1)*9
            ans+=int(n[3])+9*(m-5)
elif k==2:
    if m==1:
        print(0)
        exit()
    if i==1:
        ans+=int(n[1])+9*(m-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),0))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


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

ans = 0

if K == 1:
    c = 10
    # 桁ごと
    while N >= c:
        ans += 9
        c *= 10

    # あまり
    ans += int(str(N)[0])

elif K == 2:
    i = 2
    c = 100

    if N < 11:
        print(0)
        exit()

    # 桁毎
    while N >= c:
        ans += 9 * (i - 1) * 9
        i += 1
        c *= 10

    print(ans)

    # あまり
    l = len(str(N))
    d1 = int(str(N)[0])
    d2 = int(str(N)[1])

    # 1桁目 1 - d1-1
    if d1 > 0:
        ans += (d1 - 1) * (l - 1) * 9

    # 1桁目 d1
    # 2桁目 0
    if l > 2:
        ans += (l - 2) * 9

    # 2桁目 1-d2
    ans += d2


elif K == 3:
    i = 3
    c = 1000

    if N < 111:
        print(0)
        exit()

    # 桁毎
    while N >= c:
        ans += 9 * ((i-1) * (i-2) // 2) * 9 * 9
        i += 1
        c *= 10

    # あまり
    l = len(str(N))
    d1 = int(str(N)[0])
    d2 = int(str(N)[1])
    d3 = int(str(N)[2])

    # 1桁目 1 - d1-1
    if d1 > 0:
        ans += (d1 - 1) * ((l - 1) * (l - 2) // 2) * 9 * 9

    # 1桁目 d1
    # 2桁目 0
    if l > 3:
        ans += ((l - 2) * (l-3) // 2) * 9 * 9

    # 2桁目 1 - d2-1
    if d2 >= 1:
        ans += (d2 - 1) * (l - 2) * 9

    # 2桁目 d2
    # 3桁目 0
    if l > 3:
        ans += (l - 2) * 9

    # 3桁目 1-d3
    ans += d3


print(ans)

Submission status: Wrong Answer

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

if K ==1:
    sN = str(N)
    keta = len(sN)
    ans = int(sN[0])+9*(keta-1)
    print(ans)
elif K == 2:
    if N < 11:
        print(0)
    else:
        sN = str(N)
        keta = len(sN)
        goukei = 0
        for i in range(keta):
            goukei += (i*9)*9
        if keta > 2:
            ssN = str(N - (N%10))
        else:
            ssN = sN
        
        goukei += int(ssN[0])*9*keta
        for s in sN:
            goukei += int(s)
        print(goukei)
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+=int(str(n)[0])*(nonzero[1][1]-1)*9
        ans+=combinations_count(keta-1,k)*81
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,1)*9
    else:
        ans+=combinations_count(keta-1,k)*81
if k==3:
    if len(nonzero)==3:
        ans+=nonzero[2][0]+(nonzero[1][0]-1)*9+(int(str(n)[0])-1)*81
        ans+=int(str(n)[0])*nonzero[1][0]*(nonzero[2][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[2][1],2)*81
        ans+=combinations_count(keta-1,k)*81*9
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
    elif len(nonzero)==2:
        ans+=int(str(n)[0])*(nonzero[1][0]-1)*(nonzero[1][1]-1)*9
        ans+=int(str(n)[0])*combinations_count(nonzero[1][1]-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
    else:
        ans+=(int(str(n)[0])-1)*combinations_count(keta-1,2)*81
        ans+=combinations_count(keta-1,k)*81*9
print(ans)

Submission status: Wrong Answer

Solution code:

# https://qiita.com/derodero24/items/91b6468e66923a87f39f
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 func1(keta, not_0):
    return cmb(keta, not_0) * (9**not_0)

def solve(keta, not_0, max_num):

    if keta < not_0 or keta <= 0:
        return 0
    ans = 0

    if int(max_num[-keta]) >= 2 and keta-1 >= 0 and not_0-1 >= 0:
        ans += (int(max_num[-keta]) - 1) * func1(keta-1, not_0-1)
    if keta-1 >= not_0 and keta-1 >= 0 and not_0 >= 0:
        ans += func1(keta-1, not_0)
    if not_0 >= 1:
        ans += solve(keta-1, not_0-1, max_num)
    return ans


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

n_len = len(n_str)

print(solve(n_len, k, n_str))

Submission status: Wrong Answer

Solution code:
# ABC154e


def main():
    import sys
    import math
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)
    # 再帰関数を使わない限りPypyで出すこと

    n = int(input())
    ns = str(n)
    k = int(input())
    keta = len(ns)
    # dp[i+1][smaller][j]=i桁目までで、未満フラグをsmaller、0の個数j
    dp = [[[0]*(keta+1) for i in range(2)]
          for j in range(keta + 1)]

    dp[0][0][0] = 1

    for i in range(keta):
        for smaller in range(2):
            for j in range(i+1):
                for x in range(10 if smaller == 1 else int(ns[i])+1):
                    # if i == 0 and x == 0:
                    #    continue
                    dp[i + 1][1 if smaller == 1 or x < int(ns[i])
                              else 0][j if x != 0 else j+1] += dp[i][smaller][j]
    # print(dp)
    # print(dp[keta][0][keta-k])
    #print(dp[keta][1][keta - k])
    print(dp[keta][0][keta-k]+dp[keta][1][keta - k])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = input()
L = len(N)
K = int(input())
if L < K:
    print(0)
elif L == K:
    if N == "10":
        res = 0
    elif int(N) >= 100 and int(N) <= 110:
        res = 0
    else:
        if L == 1:
            res = int(N)
        elif L == 2:
            if N[1] == "0":
                N = str(int(N) - 1)
            res = (int(N[0]) - 1) * 9 + int(N[1])
        elif L == 3:
            if N[1] == "0":
                if N[2] == "0":
                    N = str(int(N) - 1)
                else:
                    N = str(int(N) - int(N[2]) - 1)
            res = (int(N[0]) - 1) * 81 + (int(N[1]) - 1) * 9 + int(N[2])
    print(res)
else:
    if K == 1:
        res = (L - 1) * 9 + int(N[0])
    elif K == 2:
        res = (
            (((L - 1) * (L - 2)) // 2) * 81
            + (L - 1) * 9 * (int(N[0]) - 1)
            + (L - 2) * 9
            + int(N[1])
        )
    elif K == 3:
        if N[1] == "0":
            res = (
                (((L - 1) * (L - 2) * (L - 3)) // 6) * (9 ** 3)
                + (((L - 1) * (L - 2)) // 2) * 81 * (int(N[0]) - 1)
                + (((L - 2) * (L - 3)) // 2) * 81
                + (L - 3) * 9
                + int(N[2])
            )
        else:
            res = (
                (((L - 1) * (L - 2) * (L - 3)) // 6) * (9 ** 3)
                + (((L - 1) * (L - 2)) // 2) * 81 * (int(N[0]) - 1)
                + (((L - 2) * (L - 3)) // 2) * 81
                + (L - 2) * 9 * (int(N[1]) - 1)
                + (L - 3) * 9
                + int(N[2])
            )
    print(res)

Submission status: Wrong Answer

Solution code:
n=list(map(int,input()))
l=len(n)
k=int(input())
#print(n)
ans=0
if k==1:
	#最上位に0でない数字
	ans=n[0]+9*(l-1)
elif k==2:
	if k<=l: #lは2以上
		if n[1]!=0:
			#最上位にn[0]次に0以外
			ans+=n[1]
		#最上位にn[0]次に0
		ans+=9*(l-2)
		#最上位にn[0]以外
		ans+=(n[0]-1)*9*(l-1)
		#最上位は0
		ans+=81*(l-1)*(l-2)//2
elif k==3:
	if k<=l: #lは3以上
		if n[1]!=0:
			#最上位にn[0]次にn[1]
			ans+=n[2]+9*(l-3)
			#最上位にn[0]次にn[1]以外
			ans+=(n[1]-1)*9*(l-2)
		#最上位にn[0]次に0
		ans+=81*(l-2)*(l-3)//2
		#最上位にn[0]以外
		ans+=(n[0]-1)*81*(l-1)*(l-2)//2
		#最上位はなし
		ans+=729*(l-1)*(l-2)*(l-3)//6
print(ans)

Submission status: Wrong Answer

Solution code:
def cmb(a,b):
    if b == 0:
        ans=1
    elif a<b:
        ans = 0
    else:
        Nu = 1
        Di = 1
        for i in range(b):
            Nu = Nu*(a-i)
            Di = Di*(b-i)
        ans = Nu/Di
    return ans


def f(a,keta,K):
    ans = cmb(keta,K)*9**K
    if K == 1:
        ans += a
    else:
        ans += cmb(keta, K-1)*9**(K-1)*(a-1)
    return ans



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

    ans = 0
    while K>0 and N>0:
        keta = len(str(N))-1
        a = int(N/(10**(keta)))
        if keta + 1 < K: break
        if keta == 0:
            if K==1 :ans += N
        else:
            ans += f(a,keta,K)
        N -= a*10**keta
        K -= 1
        #print(a,keta,ans)
    print(int(ans))
    return

if __name__=="__main__":
    main()

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 itertools

N = input()
K = int(input())
lN = len(N)


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

elif K == 2:
    not0 = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0 = i
            break

    ans = 0
    n = [i for i in range(lN)]

    for v in itertools.combinations(n,2):
        #print(v)
        if v[0] != 0:
            ans += 9*9
        else:
            if not0 == v[1]:
                ans += max(0,int(N[0])-1)*9 + int(N[not0])
            elif not0 < v[1]:
                ans += int(N[0])*9
    print(ans)

else:
    not0f = 1000
    not0s = 1000
    for i in range(1,lN):
        if int(N[i]) != 0:
            not0f = i
            break
    for i in range(not0f+1,lN):
        if int(N[i]) != 0:
            not0s = i
            break
    ans = 0
    n = [i for i in range(lN)]
    for v in itertools.combinations(n,3):
        if v[0] != 0:
            ans += 9*9*9
        else:
            if not0f == v[1]:
                if not0s == v[2]:
                    ans += max(0,int(N[0])-1)*9*9
                    ans += max(0,int(N[not0f])-1)*9
                    ans += int(N[not0s])
                elif not0s < v[2]:
                    ans += int(N[0])*int(N[not0f])*9
            elif not0f < v[1]:
                ans += int(N[0])*9*9
    print(ans)