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 = input()
k = int(input())

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

for i in range(100):
    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(100):
    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:
            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:

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

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

        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

Submission status: Runtime Error

Solution code:
from scipy.misc import comb
N = int(input())
K = int(input())
n = len(str(N))
ans = comb(n - 1, K) * 9 ** K
for i in range(K):
    ans += comb(n - 1 - i, K - 1 - i) * 9 ** (K - 1 - i) * (int(str(N)[i]) - 1)
    ans += comb(n - 1 - i, K - 2 - i) * 9 ** (K - 1 - i) * (int(str(N)[i + 1]) - 1)

 
print(ans + 1)

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] = 0
    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:
#整数値入力 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 += msd1 * calc2(n_given - msd1*(10**(ndigits-1),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
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

count = 0
for i in range(1,len(str(n))):
    if i >= k:
        count += 9*comb(i-1,k-1)*(9**(k-1))
        

if k == 1:
    count += int(str(n)[0])
    print(count)
    exit()
if k == 2:
    count += (int(str(n)[0])-1)*9*(len(str(n))-1)
    
    count2 = 0
    for i in range(1,len(str(n))-1):
        if i >= 1:
            count2 += 9*comb(i-1,0)*(9**(0))
    count += int(str(n)[1])    
    print(count+count2)
    exit()

if k == 3:
    count += (int(str(n)[0])-1)*comb(len(str(n))-1,2)*81
    for i in range(1,len(str(n))-1):
        if i >= 2:
            count += 9*comb(i-1,2-1)*(9**(2-1))
    count += (int(str(n)[1])-1)*9*(len(str(n))-2)
    
    count2 = 0
    for i in range(1,len(str(n))-2):
        if i >= 1:
            count2 += 9*comb(i-1,0)*(9**(0))
    count += int(str(n)[2])    
    print(count+count2)
    exit()

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)
    print(s_n)
    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:
import itertools as it
import math

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

keta = len(N)

ans = 0
num = "9" *K
def perm(n,k):
    return math.factorial(n)//math.factorial(n-k)

ans=0
if keta > K:
    ans += (9**K) * perm(keta-1, K)//math.factorial(K)
#print(ans)

if K>keta:
    ans = 0
elif K==1:
    ans += int(N[0])
elif K==2:
    ans += (int(N[0])-1) * 9 * (keta-1)#あたまが1小さい
    ans += int(N[1])#頭が同じ
    if keta >= 3:
        ans += 9 * (keta-2)
else:
    ans += (int(N[0]) - 1)*(9**2)*perm(keta-1, 2)//2 ##頭が1小さい
    ##頭が同じ
    ans += 9**2 * perm(keta-2, 2)//2
    if int(N[1])>0:#上2桁目-1
        ans += (int(N[1])-1)*9*(keta-2)
    #上2桁目まで同じ
    ans += 9*(keta-3)
    #上3桁目まで同じ
    ans += int(N[2])

# if K==1:
#     ans += int(N[0])
# elif K==2:
#     ans += int(N[0:2])
#     for i in range(keta-2):
#         ans += int(N[0]) * 9 
# else:
#     ans += int(N[0:3])
#     ans += int(N[0]) * 99 * perm(keta-2, 2)

print(ans)

Submission status: Runtime Error

Solution code:
def nC2(n):
    return n*(n-1)/2

def nC3(n):
    return n*(n-1)*(n-2)/2*3

def K1(s):
    while s[0]=="0" and len(s)>0:
        s=s[1:]

    ll=len(s)

    if ll==1:
        N=int(s[0])
    
    elif ll>1:
        N=int(s[0])+9*(ll-1)
    else:
        N=0

    return N


def K2(s):
    while s[0]=="0" and len(s)>0:
        s=s[1:]
    
    ll=len(s)

    if ll==1 or ll ==0:
        N=0
    elif ll==2:
        N=(int(s[0])-1)*9+int(s[1])
    else:
        N=K1(s[1:])+(int(s[0])-1)*(ll-1)*9+9*9*nC2(ll-1)

    return N


def K3(s):
    ll=len(s)

    if ll ==1 or ll==2:
        N=0
    elif ll==3:
        N=(int(s[0])-1)*9*9+int(s[1])*int(s[2])
    else:
        N=K2(s[1:])+(int(s[0])-1)*nC2(ll-1)*9*9+nC3(ll-1)*9*9*9
    
    return N

N=input()
K=input()

if K=="1":
    ans=K1(N)
elif K=="2":
    ans=K2(N)
elif K=="3":
    ans=K3(N)

print(int(ans))