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: Runtime Error

Solution code:

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

keta1=len(str(N))
maxN=int(str(N)[0])
keta2=len(str(int(str(N)[1:])))
secN=int(str(int(str(N)[1:]))[0])
keta3=len(str(int(str(int(str(N)[1:]))[1:])))
thiN=int(str(int(str(int(str(N)[1:]))[1:]))[0])
only1=0
only2=0
if secN==0:
    only1=1
if str(int(str(int(str(N)[1:]))[0]))[0]==0:
    only2=1
import math

if keta1<K:
    print(0)
else:
    if K==1:
        print(maxN+9*(keta1-1))
    if K==2:
        if keta1-2!=0:
            if only1:
                print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2)
            else:
                if keta2-1!=0:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN+(keta2-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN)
        else:
            print((maxN-1)*(keta1-1)*9+secN)
    if K==3:
        if keta1-3!=0:
            if only1:
                print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1))
            else:
                if keta2-2!=0:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)+(secN-1)*9*2+(keta3-1)*9+thiN)
                else:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)+(secN-1)*9*2+thiN)
        else:
            if only1:
                print((maxN-1)*(keta1-1)*9)
            else:
                print((maxN-1)*(keta1-1)*9+(secN-1)*9+thiN)

Submission status: Runtime Error

Solution code:
import math

x = int(input())
K = int(input())

N = str(x)
n = len(N)

keta = [0] * n


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


for i in range(n):
    if int(N[i]) == 0:
        keta[i] = 9
    else:
        keta[i] = int(N[i])

Sum = 0

if K == 1:
    Sum += keta[0]
    Sum += 9 * (n - 1)

elif K == 2:
    for j in range(1, n):
        if j == 1:
            Sum += ((keta[0] - 1) * 9) + keta[j]
        else:
            Sum += ((keta[0] - 1) * 9) + 9

    Sum += 81 * com(n - 1, 2)

elif K == 3:
    for j in range(1, n - 1):
        for k in range(j + 1, n):
            if j == 1:
                #a = Sum
                if k == 2:
                    Sum += ((keta[0] - 1) * 81) + ((keta[j] - 1) * 9) + keta[2]
                else:
                    Sum += ((keta[0] - 1) * 81) + ((keta[j] - 1) * 9) + 9
                #print(Sum - a)
            else:
                Sum += ((keta[0] - 1) * 81) +((keta[j] - 1) * 9) + keta[k]

    Sum += (9**3) * com(n - 1, 3)

print(Sum)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
ans=0
a=int(math.log10(N))
if a<K-1:
    ans=0
else:
    if a>=K:
        ans+=(math.factorial(a)//(math.factorial(a-K)*math.factorial(K)))*(9**K)
    n=str(N)
    if K==1:
        ans+=int(n[0])
    elif K==2:ans+=(int(n[0])-1)*9+int(n[0])*(len(n)-2)*9+int(n[1])
    else:ans+=(int(n[0])-1)*81+(int(n[1])-1)*9+int(n[2])+int(n[0])*((math.factorial(len(n)-2)//(math.factorial(K-1)*math.factorial(len(n)-K-1)))-1)*81

print(ans)

Submission status: Runtime Error

Solution code:
import sys
def combination(a, b):
    if b == 1:
        return a
    if b == 2:
        return (a*(a-1))//2
    if b == 3:
        return (a*(a-1)*(a-2))//6
def main():
    N = input()
    K = int(input())
    ans = 0
    for k in range(K):
        n = N[k:]
        L = len(n)
        s = K-k
        ans += combination(L-1,s)*(9**(s))
        if s-1 > 0:
            ans += (int(N[0])-1)*combination(L-1,s-1)*(9**(s-1))
    ans += int(N[K-1])
    print(int(ans))
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def check(n):
  m = 0
  for i in range(len('n')):
    if str(n)[i] != '0'
      m = m + 1
    else:
      continue
  if m == K:
    return 1
  else:
    return 0

def count(n):
  return count(n - 1) + check(n -1)

print(count(N))

Submission status: Runtime Error

Solution code:

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

keta1=len(str(N))
maxN=int(str(N)[0])
keta2=len(str(int(str(N)[1:])))
secN=int(str(int(str(N)[1:]))[0])
keta3=len(str(int(str(int(str(N)[1:]))[1:])))
thiN=int(str(int(str(int(str(N)[1:]))[1:]))[0])
only1=0
only2=0
if secN==0:
    only1=1
if str(int(str(int(str(N)[1:]))[0]))[0]==0:
    only2=1
import math

if keta1<K:
    print(0)
else:
    if K==1:
        print(maxN+9*(keta1-1))
    if K==2:
        if keta1-2!=0:
            if only1:
                print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2)
            else:
                if keta2-1!=0:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN
                        +(keta2-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN)
        else:
            print((maxN-1)*(keta1-1)*9+secN)
    if K==3:
        if keta1-3!=0:
            if only1:
                print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1))
            else:
                if keta2-2!=0:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)
                        +(secN-1)*9*2+(keta3-1)*9+thiN)
                else:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)
                        +(secN-1)*9*2+thiN)
        else:
            if only1:
                print((maxN-1)*(keta1-1)*9)
            else:
                print((maxN-1)*(keta1-1)*9+(secN-1)*9+thiN)

Submission status: Runtime Error

Solution code:
from math import log10
n=input()
k=int(input())

#ないときも後で
l=len(n)
ans1=0
if l>k:
    if k==1:
        ans1=l-1
    elif k==2:
        ans1=(l-1)*(l-2)//2
    else:
        ans1=(l-1)*(l-2)*(l-3)//6
ans1*=9**k
if l>=k:
    if k==1:
        ans=0
    elif k==2:
        ans=(l-1)
    else:
        ans=(l-1)*(l-2)//2
ans*=(int(n[0])-1)*9**(k-1)

dp=[[0]*3 for _ in range(l-1)]
dp[-1][0]=1
n=list(n)
n.reverse()
for i,c in enumerate(n[:-1]):
    c=int(c)
    dp[i][0]=1
    dp[i][1]=dp[i-1][1]+dp[i-1][0]*c
    dp[i][2]=dp[i-1][2]+dp[i-1][1]*c
ans+=dp[-1][k-1]
print(ans+ans1)

Submission status: Runtime Error

Solution code:
#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

#選び方（コンビネーション nCr）
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)]


def calc2(n,k):
    n_given = n
    k_given = k

    ans = 0
    ndigits = len(str(n_given))
    if k_given == 1:
        msd = n_given
        while msd >= 10:
            msd //=10
        
        ans = (ndigits-1)*9+msd

    elif k_given == 2:
        if ndigits < 2:
            ans = 0
        else:
            msd1 = n_given
            while msd1 >= 100:
                msd1 //=10
            msd2 = msd1%10
            msd1 = msd1//10
            
            if(ndigits > 2):
                ans += cmb(ndigits-1,2)*pow(9,2)
            ans += (msd1-1)*(ndigits-1)*9
            ans += (ndigits-2)*9+msd2

    return ans

n_given = input_one_number()
k_given = input_one_number()

ans = 0
ndigits = len(str(n_given))
if k_given == 1:
    msd = n_given
    while msd >= 10:
        msd //=10

    ans = (ndigits-1)*9+msd

elif k_given == 2:
    if ndigits < 2:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 100:
            msd1 //=10
        msd2 = msd1%10
        msd1 = msd1//10

        if(ndigits > 2):
            ans += cmb(ndigits-1,2)*pow(9,2)
        ans += (msd1-1)*(ndigits-1)*9
        ans += (ndigits-2)*9+msd2

else:
    if ndigits < 3:
        ans = 0
    else:
        msd1 = n_given
        while msd1 >= 1000:
            msd1 //=10
        msd3 = msd1%10
        msd1 = msd1//10
        msd2 = msd1%10
        msd1 = msd1//10
        
        if(ndigits > 3):#XX XO
            ans += cmb(ndigits-1,3)*pow(9,3)
        if(ndigits > 3 and msd2 > 0):#OX
            ans += cmb(ndigits-2,2)*pow(9,2)*(msd1)
        if(ndigits > 3 and msd ==0):
            ans += calc2(n_given - msd1*(10**ndigits),2)
        if(ndigits > 3 and msd2 > 0):#OO
            ans += (ndigits-3)*msd1*msd2*9
        ans += (msd1-1) * 81 + msd2*msd3

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
x=math.floor(math.log10(N))+1
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if x<K:
  print(0)
  exit(0)
if K==1:
  ans=(x-1)*9
  ans+=(N//10**(x-1))
  print(ans)
elif K==2:
  for i in range(2,x):
    ans+=(9**2)*(i-1)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  ans+=(f-1)*9*(x-1)
  ans+=9*(s_n-1)
  ans+=s
  print(ans)
else:
  for i in range(3,x):
    ans+=(9**3)*combinations_count(i-1,2)
  f=(N//10**(x-1))
  n=str(N)
  s_n=0
  s=0
  t_n=0
  t=0
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  for i in range(x-s_n+1,x):
    if n[i]!='0':
      t_n=x-i
      t=int(n[i])
      break
  if s_n<2:
    ans+=(f-1)*9**2*combinations_count(x-1,2)
    if s>0:
      ans+=(s-1)*9*(s_n-1)
    if t_n!=0:
      ans+=9*(t_n-1)
    ans+=t
  else:
    ans+=(f-1)*9**2*combinations_count(x-1,2)
    ans+=9**2*combinations_count(s_n-1,2)
    ans+=(s-1)*9*(s_n-1)
    if t_n!=0:
	    ans+=9*(t_n-1)
    ans+=t
  print(ans)

Submission status: Runtime Error

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_s = input()
N_l = len(N_s)
N = int(N_s)
K_s = input()
K_l = len(K_s)
K = int(K_s)

s = 0

for i in range(K_l, N_l):
  s += 9**K * cmb(i-1,K-1)

#N制限
start = 10**(N_l)
end = N
c = int(end/(10**(N_l-1)))
if K == 1:
  s += c


print(s)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
#base = comb(5, 3, exact=True)
n=int(input())
k=int(input())

l=n
l=str(l)
keta=len(l)
num=[0 for i in range(keta)]
ans=0
m=n
for i in range(keta):
  num[i]=m%10
  m//=10
#print(num)
if k==1:
  ans+=num[-1]+(keta-1)*9
if k==2:
  ans+=(num[-1]-1)*(keta-1)*9
  for i in range(keta-1):
    if i!=keta-2:
      ans+=9
    else:
      ans+=num[i]
  if keta>=3:
    ans+=comb(keta-1,2,exact=True)*81
if k==3:
  ans+=comb(keta-1,3,exact=True)*729
  ans+=(num[-1]-1)*comb(keta-1,2,exact=True)*81
  ans+=(num[-2]-1)*(keta-2)*9
  for i in range(keta-2):
    ans+=num[i]
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
count = 0
for i in range(1,N+1):
  _i = str(i).strip("0")
  if len(_i) == K:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
from scipy.special 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: Runtime Error

Solution code:
def combination(a, b):
    if b == 1:
        return a
    if b == 2:
        return (a*(a-1))//2
    if b == 3:
        return (a*(a-1)*(a-2))//6
N = input()
K = int(input())
ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    ans += combination(L-1,s)*(9**(s))
    if s-1 > 0:
        ans += (int(N[0])-1)*combination(L-1,s-1)*(9**(s-1))
ans += int(N[K-1])
print(int(ans))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
for i in range(1,N+1):
  _i = str(i).strip("0")
  if len(_i) == K:
    count += 1
print(count)

Submission status: Runtime Error

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

List = list(str(N))

L = len(List)
a = int(List[0])

ans = 0
stop = 0

def cul2(L,a,stop,List):
  if L < 2:
    ans = 0
  elif L == 2:
    b = int(List[1])
    ans = int((a-1)*9+b)
  else:
    b = int(List[1])
    c = int(List[2])
    L = L - 1
    if b == 0:
      b = c
    ans = (a-1) * (9+9*(L-1)) + (b+(9*(L-1)))
    while stop == 0:
      L = L -1
      ans = int( ans + 9*(9+9*(L-1)) )
      if L == 0:
        stop = 1
  return ans 

if K == 1:
  ans = int(a + 9 * (L-1))
elif K == 2:
  if L < 2:
    ans = 0
  elif L == 2:
    ans = int((a-1)*9+b)
  else:
    b = int(List[1])
    c = int(List[2])
    L = L - 1
    if b == 0:
      b = c
    ans = (a-1) * (9+9*(L-1)) + (b+(9*(L-1)))
    while stop == 0:
      L = L -1
      ans = int( ans + 9*(9+9*(L-1)) )
      if L == 0:
        stop = 1
        
else:
  if L < 3:
    ans = 0
  else:
    b = int(List[1])
    c = int(List[2])
    d = int(List[3])
    L = L - 1
    
    e = int ( b * (10**(L-1)) + c * (10**(L-2)) + d * (10**(L-3)) )
    ee = list(str(e))
      
    ans = int ( (a-1) * cul2(L,a,stop,List) + cul2(len(ee),int(ee[0]),stop,ee) )
    while stop == 0:
      L = L -1
      List.pop(0)
      ans = int( ans + cul2(L,9,stop,List) )
      if L == 0:
        stop = 1   
    
print(ans)

Submission status: Runtime Error

Solution code:

import math
from functools import reduce
import itertools

nstr = input()
n = int(nstr)
k = int(input())
l = len(nstr)
narr = [int(a) for a in nstr]

combnum = (lambda n, r: math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))

result = 0
if l > k:
  result = combnum(l-1, k) * 9**k
  
result += combnum(l-1, k-1) * ((narr[0]-1) * 9**(k-1))
if k == 1:
  result += 1
else:
  result += sum([reduce(lambda a, b: a*b, c) for c in itertools.combinations(narr[1:], k-1)])
print(result)

Submission status: Runtime Error

Solution code:
import math

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

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

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

for i in range(9):
    i = 9 - i
    num = i * 10**(len(str(N))-1)
    if num > N:
        continue
    ans += comb(len(str(N))-1, K-1) * 9**(K-1) * (i-1)
    break

if K == 1:
    if num <= N:
        ans += 1

if K == 2:
    for i in range(len(str(N))-1):
        for j in range(1, 10):
            num2 = num + j * 10**i
            if num2 <= N:
                ans += 1

if K == 3:

    for i in range(99):
        i = 99 - i
        num = i * 10**(len(str(N))-2)
        if num > N:
            continue
        ans += comb(len(str(N))-2, K-2) * 9**(K-2) * (i-1)
        break

    for i in range(len(str(N))-2):
        for j in range(1, 10):
            num2 = num + j * 10**i
            if num2 <= N:
                ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
for i in range(1,N+1):
  _i = i.remove(0)
  if len(_i) == K:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
import math

x = int(input())
K = int(input())

N = str(x)
n = len(N)

keta = [0] * n


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


for i in range(n):
    if int(N[i]) == 0:
        keta[i] = 9
    else:
        keta[i] = int(N[i])

Sum = 0

if K == 1:
    for i in range(n):
        Sum += keta[i]

elif K == 2:
    for j in range(1, n):
        if j == 1:
            Sum += ((keta[0] - 1) * 9) + keta[j]
        else:
            Sum += ((keta[0] - 1) * 9) + 9

    Sum += 81 * com(n - 1, 2)

elif K == 3:
    for j in range(1, n - 1):
        for k in range(j + 1, n):
            if j == 1:
                #a = Sum
                if k == 2:
                    Sum += ((keta[0] - 1) * 81) + ((keta[j] - 1) * 9) + keta[2]
                else:
                    Sum += ((keta[0] - 1) * 81) + ((keta[j] - 1) * 9) + 9
                #print(Sum - a)
            else:
                Sum += ((keta[0] - 1) * 81) +((keta[j] - 1) * 9) + keta[k]

    Sum += (9**3) * com(n - 1, 3)

print(Sum)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
def comb(a, b):
    if b == 1:
        return a
    if b == 2:
        return (a*(a-1))//2
    if b == 3:
        return (a*(a-1)*(a-2))//6
N = input()
K = int(input())
ans = 0
for k in range(K):
    n = N[k:]
    L = len(n)
    s = K-k
    ans += comb(L-1,s)*(9**(s))
    if s-1 > 0:
        ans += (int(N[0])-1)*comb(L-1,s-1)*(9**(s-1))
ans += int(N[K-1])
print(int(ans))

Submission status: Runtime Error

Solution code:
def main():
    
    for i in range(N+1):
        s = 0
        list_i = list(str(i))
        for j in range(1,10):
            s += list_i.count(str(j))
        if s == K:
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
if keta-1>=k:
                if third!=0:
                    answer+=third
                else:
                    swit=0
                    keta2=0
                    kaz=0
                    for zl in zlist:
                        if zl[0]>=3 and swit<=1:
                            swit+=1
                            keta2=zl[0]
                            kaz=zl[1]
                    if swit>1:
                        answer+=(keta-keta2-1)*9
                        answer+=1
            else:
                if third!=0:
                    answer+=third

Submission status: Runtime Error

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
    xx = combinations(a, 3)

    if k==3:
    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
    else k==2:
        if n<(10**p[0]+10**p[1]):
            continue
        elif n>=(10**p[0]*9+10**p[1]*9):
            t+=9*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
    else k==1:
        if n<(10**p[0]):
            continue
        elif n>=(10**p[0]*9):
            t+=9*9*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: Runtime Error

Solution code:
if k==1:
    ans=9*(p-1)+q
if k==2:
    if int(n)>9:
        q2=int(n[1])
        ans=int(81*0.5*(p-1)*(p-2))
        ans+=9*(p-1)*(q-1)
        ans+=q2+9*(p-2)
    else:
        ans=0
    
if k==3:
    if int(n)>110:
        q2=int(n[1])
        q3=int(n[2])
        ans=int(729*((p-1)*(2*p-3)*(p-2)-3*(p-1)*(p-2))/12)
        ans+=81*(q-1)*(p-1)*(p-2)/2
        ans+=81*(p-2)*(p-3)/2
        ans+=9*(p-3)*q2
        ans+=(q2-1)*9
        ans+=q3
    else:
        ans=0

print(int(ans))

Submission status: Runtime Error

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

keta = len(n)
ans = 0
if k == 1:
    ans += 9 * (keta-1) + int(n[0])
    
if k == 2:
    ans +=int(n[0])*9*(keta-1) - (9-int(n[1]))*(keta-1) + 81*(keta-2)*(keta-1)/2

if k == 3:
    if keta < 3:
        ans = 0
    else:
        ans += int(n[0])*81*(keta-1)*(keta-2)/2 - (10-int(n[1]))*9 + (int(n[2]))
        for i in range(keta-2):
            ans += 729*(keta-i-2)*(keta-i-3)/2



print(int(ans))

Submission status: Runtime Error

Solution code:
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[99-i])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[i])-1)
    print(counter)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())
import math
x=math.floor(math.log10(N))+1
def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans=0
if x<K:
  print(0)
  exit(0)
if K==1:
  ans=(x-1)*9
  ans+=(N//10**(x-1))
  print(ans)
elif K==2:
  for i in range(2,x):
    ans+=(9**2)*(i-1)
  f=(N//10**(x-1))
  n=str(N)
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  ans+=(f-1)*9*(x-1)
  ans+=9*(s_n-1)
  ans+=s
  print(ans)
else:
  for i in range(3,x):
    ans+=(9**3)*combinations_count(i-1,2)
  f=(N//10**(x-1))
  n=str(N)
  s_n=0
  t_n=0
  for i in range(1,x):
    if n[i]!='0':
      s_n=x-i
      s=int(n[i])
      break
  for i in range(x-s_n+1,x):
    if n[i]!='0':
      t_n=x-i
      t=int(n[i])
      break
  if s_n==2:
    ans+=(f-1)*9**2*combinations_count(x-1,2)
    ans+=(s-1)*9*(s_n-1)
    if t_n!=0:
      ans+=9*(t_n-1)
    ans+=t
  else:
    ans+=(f-1)*9**2*combinations_count(x-1,2)
    ans+=9**2*combinations_count(s_n-1,2)
    ans+=(s-1)*9*(s_n-1)
    if t_n!=0:
	    ans+=9*(t_n-1)
    ans+=t
  print(ans)

Submission status: Runtime Error

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)
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: Runtime Error

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

if n_num < k:
    print('0')
    return

dp = [[[0] * (n_num + 1) for _ in range(2)]for _ in range(n_num + 1)]

dp[0][0][0] = 1
for i in range(n_num):
    for smaller in range(2):
        for j in range(n_num):
            lim = 9 if smaller else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = smaller | (x < n_list[i])
                dp[i + 1][nlt][ns] += dp[i][smaller][j]
ans = dp[n_num][0][k] + dp[n_num][1][k]
print(ans)

Submission status: Runtime Error

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	K = II()

	def comb(n, r):
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
	digits = len(str(N))
	ans = 0
	if(digits < K):
		print(0)
	else:
		for i in range(digits-1, K-1, -1):
			ans += comb(i-1,K-1) * (9**K)
		for i in range(0,K):
			a = int(str(N)[i])
			if(i==0 and a!=0):
				ans += comb(digits-i-1,K-i-1) * (9**(K-1-i)) * (a-1)
			elif(a!=0):
				ans += comb(digits-i-1,K-i-1) * (9**(K-1-i)) * (a-1)
				ans += comb(digits-i-1,K-i) * (9**(K-i))
		cnt = 0
		for s in str(N):
			if(s!='0'):cnt+=1
		if(cnt==K):ans+=1
		if(K<digits):ans+=1
		print(ans)


main()

Submission status: Runtime Error

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

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

#if n_num < k:
#    print('0')
#    return

dp = [[[0] * (n_num + 1) for _ in range(2)]for _ in range(n_num + 1)]

dp[0][0][0] = 1
for i in range(n_num):
    for smaller in range(2):
        for j in range(n_num):
            lim = 9 if smaller else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = smaller | (x < n_list[i])
                dp[i + 1][nlt][ns] += dp[i][smaller][j]
ans = dp[n_num][0][k] + dp[n_num][1][k]
print(ans)

Submission status: Runtime Error

Solution code:
# E
import numpy as np
import math
N = int(input())
K = int(input())

log_ind = int(np.log10(N))
if log_ind > K -1:
    ans1 = math.factorial(log_ind+K-1) / \
        math.factorial(log_ind-1)/math.factorial(K)*9
else:
    ans1 = 0
ans2 = len([1 for i in range(10**log_ind, N+1)
            if str(i).count("0") == log_ind+1-K])

print(int(ans1+ans2))

Submission status: Runtime Error

Solution code:
N = input()
d_num = len(N) #ケタ数
K = int(input())
ans = 0

if(K == 1):
 top = int(N[0]) #最高位
 ans += (d_num-1)*9  
 ans += top

elif(K == 2):
 top, semi = int(N[0]), int(N[1]) #最高位, 準最高位
 if(d_num >= 2): 
   #Top以外2つ選んだ場合
     ans += (((d_num-1)*(d_num-2))//2)*9*9 #nC2*9*9  
   #Top含む2つ
    #Top<top を選んだ場合
     ans += 1*(d_num-1)*(top-1)*9
    #Top==top + Semi を選んだ場合
     ans +=  1*1*1*(semi)
    #Top==top + Semi以外 を選んだ場合
     ans +=  1*(d_num-2)*1*9

elif(K == 3):
 top, s1, s2 = int(N[0]), int(N[1]), int(N[2]) #最高位, 準最高位,準々最高位
 if(d_num >= 3): 
   #Top以外3つ選んだ場合
     ans += (((d_num-1)*(d_num-2)*(d_num-3))//6)*9*9*9 #nC3*9*9  
   #Top含む3つ
    #Top<top を選んだ場合
     ans += 1*(((d_num-1)*(d_num-2))//2)*(top-1)*9*9
    #Top==top + S1 を選んだ場合
     #S1 < s1 のとき
     ans += 1*1*(d_num-2)*1*(s1-1)*9
     #S1 = s1のとき
      #S2を選んだ場合
     ans += 1*1*1*1*1*s2
      #S2以外を選んだ場合
     ans += 1*1*(d_num-3)*1*1*9
    #Top==top + S1以外 を選んだ場合
     ans +=  1*(((d_num-2)*(d_num-3))//2)*1*9*9

print(ans)

Submission status: Runtime Error

Solution code:
from math import floor, log10
N = int(input())
K = int(input())
ans = 0
def X(num):
    return floor(log10(num)+1)

def solve_k1(num):
    return 9*(X(num)-1)+int(str(num)[0])

def mitukeru_not_zero(num):
    for i in range(len(str(num))):
        if i != 0 and str(num)[i] != "0":
            return i
    else:
        return -1 

if K == 1:
    print(solve_k1(N))
elif K == 2:
    ans = int(0.5*(X(N)-1)*(X(N)-2)*81) + 9*(X(N)-1)*(int(str(N)[0])-1)
    if mitukeru_not_zero(N) != -1:
        print(ans + solve_k1(int(str(num)[mitukeru_not_zero(num):])))
else:
    raise TypeError

Submission status: Runtime Error

Solution code:
# coding: utf-8

from math import factorial as fact
# import copy

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

digit = len(str(N))

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)

    # 桁数が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(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 -= 1
    digit -= 1

print(ans+1)

Submission status: Runtime Error

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

    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)
    # print(ans)
    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):
                if sum(keta[j+1:-1]) == 0:
                    ans += (max(keta[j]-1, 0)) * 9
                    if sum(keta[i+1:j]) == 0:
                        ans += keta[i]
                    else:
                        ans += 9
                else:
                    ans += 81

        print(ans)


if __name__ == '__main__':
    main()