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:
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]

## dp1:top   dp2:under
dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+(dp1[i-1][j])

print(dp1[-1][-2]+dp2[-1][-2])

Submission status: Wrong Answer

Solution code:
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]

## dp1:top   dp2:under
dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

cnt=0
for i in range(1,x):
    if l[i]>0:
        cnt+=1
    if cnt<=k:
        dp1[i][cnt]=1
for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp2[i][0]=1
        else:
            dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))+(dp1[i-1][j])
#print(dp1)
#print(dp2)
print(dp1[-1][-2]+dp2[-1][-2])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
def e(): exit()
n="0"+input()
x=len(n)
k=int(input())
l=[int(i) for i in n]

## dp1:top   dp2:under
dp1=[[0]*(k+2) for i in range(x)]
dp2=[[0]*(k+2) for i in range(x)]

dp1[0][0]=1
dp1[0][1]=0
dp2[0][0]=0
dp2[0][1]=0

for i in range(1,x):
    for j in range(k+1):
        if j==0:
            dp1[i][0]=0
            dp2[i][0]=1
        else:
            dp1[i][j]=dp1[i-1][j]
            if i==j:
                dp1[i][j]=1
            #    dp2[i][j]+=max(0,l[i-1]-1)
            #dp2[i][j]=dp2[i-1][j-1]*9+max(0,dp1[i-1][j]*l[i-1]-1)+dp2[i-1][j]
            dp2[i][j]=(dp2[i-1][j-1]*9)+(dp2[i-1][j])+(dp1[i-1][j-1]*max(0,l[i]-1))
#print(dp1)
#print(dp2)
print(dp1[-1][-2]+dp2[-1][-2])

Submission status: Wrong Answer

Solution code:
n=input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp1=[[0]*(k+2) for i in range(x+1)]
dp2=[[0]*(k+2) for i in range(x+1)]
dp1[1][1]=1
for i in range(2,x+1):
    for j in range(1,k+1):
        #dp1[i][j]=dp1[i-1][j]+l[i-1]
        #if j>0: dp1[i][j]=dp1[i-1][j]+l[i-1]
        #if j>i: continue
        #if j>0: dp1[i][j]=dp1[i-1][j]+([dp1[i-1][j-1]*9,1][j==i])
        if j==i: dp1[i][j]=1
        elif j<=i: dp1[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*9
        #elif j>0: dp1[i][j]=dp1[i-1][j]+([dp1[i-1][j-1]*9,1][j==i])
dp2[0][0]=1
dp2[1][0]=1
dp2[1][1]=l[0]-1
for i in range(2,x+1):
    for j in range(k+1):
        dp2[i][j]=dp2[i-1][j]+(dp2[i-1][j-1]*9)
print(dp1[x][k]+dp2[x][k])

Submission status: Wrong Answer

Solution code:
n=input()
x=len(n)
k=int(input())
l=[int(i) for i in n]
dp1=[[0]*(k+2) for i in range(x+1)]
dp2=[[0]*(k+2) for i in range(x+1)]
dp1[0][0]=1
dp1[1][0]=1
dp1[1][1]=1
for i in range(2,x+1):
    for j in range(k+1):
        dp1[i][j]=dp1[i-1][j]+l[i-1]
dp2[0][0]=1
dp2[1][0]=1
dp2[1][1]=l[0]-1
for i in range(2,x+1):
    for j in range(k+1):
        dp2[i][j]=dp2[i-1][j]+(dp2[i-1][j-1]*9)
print(dp1[x][k]+dp2[x][k])

Submission status: Wrong Answer

Solution code:

def dyn(n,d00,d01,d02,d03,d10,d11,d12,d13):
    D00 = d00 + d10*int(n != 0)
    D10 = d10*int(n==0)
    D01 = d00*9 + d10*(n-1+int(n==0)) + d01 + d11*int(n!=0)
    D11 = d10*(int(n!=0)) + d11*(int(n==0))
    D02 = d01*9 + d11*(n-1+int(n==0)) + d02 + d12*int(n!=0)
    D12 = d11*(int(n!=0)) + d12*(int(n==0))
    D03 = d02*9 + d11*(n-1+int(n==0)) + d03 + d13*int(n!=0)
    D13 = d12*(int(n!=0)) + d13*(int(n==0))
    return D00,D01,D02,D03,D10,D11,D12,D13

N = str(input())
K = int(input())
S = len(N)
D00=0
D01=0
D02=0
D03=0
D10=1
D11=0
D12=0
D13=0

for i in range(S):
    [D00,D01,D02,D03,D10,D11,D12,D13] = dyn(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)
    print(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)
if K == 1:
    print(D01+D11)
elif K==2:
    print(D02+D12)
else:
    print(D03+D13)

Submission status: Wrong Answer

Solution code:

def dyn(n,d00,d01,d02,d03,d10,d11,d12,d13):
    D00 = d00 + d10*int(n != 0)
    D10 = d10*int(n==0)
    D01 = d00*9 + d10*(n-1+int(n==0)) + d01 + d11*int(n!=0)
    D11 = d10*(int(n!=0)) + d11*(int(n==0))
    D02 = d01*9 + d11*(n-1+int(n==0)) + d02 + d12*int(n!=0)
    D12 = d11*(int(n!=0)) + d12*(int(n==0))
    D03 = d02*9 + d11*(n-1+int(n==0)) + d03 + d13*int(n!=0)
    D13 = d12*(int(n!=0)) + d13*(int(n==0))
    return D00,D01,D02,D03,D10,D11,D12,D13

N = str(input())
K = int(input())
S = len(N)
D00=0
D01=0
D02=0
D03=0
D10=1
D11=0
D12=0
D13=0
#print(D00,D01,D02,D10,D11,D12)
for i in range(S):
    [D00,D01,D02,D03,D10,D11,D12,D13] = dyn(int(N[i]),D00,D01,D02,D03,D10,D11,D12,D13)
if K == 1:
    print(D01+D11)
elif K==2:
    print(D02+D12)
else:
    print(D03+D13)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
n0 = int(N[0])

# 数値Nから,1の位の位置をp1とする[keta]桁の部分数値が全て0であるか
def if_part_zero (N, p1, keta):
  if keta < 1:
    return False
  partnum = 0
  beki = keta - 1
  for i in range(p1 - keta + 1, p1 + 1):
    if int(N[i]) > 0:
      return False
  return True


t = 0
if (K == 1):
  t = n0 + (len(N) - 1) * 9

if (K == 2):
  enough = 0
  for i in range(0, len(N) - 1):
    if i > 0:
      pattern1 = 9
      enough = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N)):
      if enough == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
      else:
        pattern2 = int(N[j])
      # print ("i=" + str(i) + " j=" + str(j) + " p=" + str((pattern1 - 1) * 9 + pattern2))
      t += (pattern1 - 1) * 9 + pattern2
    
if (K == 3):
  enough1 = 0
  enough2 = 0
  for i in range(0, len(N) - 2):
    if i > 0:
      pattern1 = 9
      enough1 = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N) - 1):
      if enough1 == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
        enough2 = 1
      else:
        pattern2 = int(N[j])
      if pattern1 == 1 and pattern2 == 0:
        continue
      for k in range(j + 1, len(N)):
        if enough1 == 1 or enough2 == 1 or if_part_zero(N, k - 1, k - j - 1) == False:
          pattern3 = 9
        else:
          pattern3 = int(N[k])
        
        # print ("1=" + str(pattern1) + " 2=" + str(pattern2) + " 3=" + str(pattern3) + " p=" + str(((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3))
        t += ((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3

print (t)

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
n0 = int(N[0])

# 数値Nから,1の位の位置をp1とする[keta]桁の部分数値が全て0であるか
def if_part_zero (N, p1, keta):
  partnum = 0
  beki = keta - 1
  for i in range(p1 - keta + 1, p1 + 1):
    if int(N[i]) > 0:
      return False
  return True


t = 0
if (K == 1):
  t = n0 + (len(N) - 1) * 9

if (K == 2):
  enough = 0
  for i in range(0, len(N) - 1):
    if i > 0:
      pattern1 = 9
      enough = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N)):
      if enough == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
      else:
        pattern2 = int(N[j])
      # print ("i=" + str(i) + " j=" + str(j) + " p=" + str((pattern1 - 1) * 9 + pattern2))
      t += (pattern1 - 1) * 9 + pattern2
    
if (K == 3):
  enough1 = 0
  enough2 = 0
  for i in range(0, len(N) - 2):
    if i > 0:
      pattern1 = 9
      enough1 = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N) - 1):
      if enough1 == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
        enough2 = 1
      else:
        pattern2 = int(N[j])
      if pattern1 == 1 and pattern2 == 0:
        continue
      for k in range(j + 1, len(N)):
        if enough1 == 1 or enough2 == 1 or if_part_zero(N, k - 1, k - j - 1) == False:
          pattern3 = 9
        else:
          pattern3 = int(N[k])
        
        print ("1=" + str(pattern1) + " 2=" + str(pattern2) + " 3=" + str(pattern3) + " p=" + str(((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3))
        t += ((pattern1 - 1) * 9 + pattern2 - 1) * 9 + pattern3

print (t)

Submission status: Wrong Answer

Solution code:
from itertools import product
N=input()
K=int(input())

dp=[[[0 for _ in range(K+1)] for _ in range(2)] for _ in range(len(N)+1)]

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

for i in range(len(N)):
    for smaller in range(2):
        for j in range(K+1):
            for x in range(1 if j==K else int(N[i])+1 if smaller==0 else 10):
                dp[i+1][smaller or (x < int(N[i]))][j+x!=0]+=dp[i][smaller][j]
print(dp[len(N)][1][K]+dp[len(N)][0][K])

Submission status: Wrong Answer

Solution code:
N = input()
K = int(input())
n0 = int(N[0])

# 数値Nから,1の位の位置をp1とする[keta]桁の部分数値が全て0であるか
def if_part_zero (N, p1, keta):
  partnum = 0
  beki = keta - 1
  for i in range(p1 - keta + 1, p1 + 1):
    if int(N[i]) > 0:
      return False
  return True


t = 0
if (K == 1):
  t = n0 + (len(N) - 1) * 9

if (K == 2):
  enough = 0
  for i in range(0, len(N) - 1):
    if i > 0:
      pattern1 = 9
      enough = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N)):
      if enough == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
      else:
        pattern2 = int(N[j])
      # print ("i=" + str(i) + " j=" + str(j) + " p=" + str((pattern1 - 1) * 9 + pattern2))
      t += (pattern1 - 1) * 9 + pattern2
    
if (K == 3):
  enough1 = 0
  enough2 = 0
  for i in range(0, len(N) - 2):
    if i > 0:
      pattern1 = 9
      enough1 = 1
    else:
      pattern1 = n0
    for j in range(i + 1, len(N) - 1):
      if enough1 == 1 or if_part_zero(N, j - 1, j - i - 1) == False:
        pattern2 = 9
        enough2 = 1
      else:
        pattern2 = int(N[j])
      for k in range(j + 1, len(N)):
        if enough1 == 1 or enough2 == 1 or if_part_zero(N, k - 1, k - j - 1) == False:
          pattern3 = 9
        else:
          pattern3 = int(N[k])
        # print ("i=" + str(i) + " j=" + str(j) + " k=" + str(k) + " p=" + str((pattern1 - 1) * 81 + (pattern2 - 1) * 9 + pattern3))
        t += (pattern1 - 1) * 81 + (pattern2 - 1) * 9 + pattern3

print (t)

Submission status: Wrong Answer

Solution code:
N = list(map(int,input()))
K = int(input())

def f(n,k):
  if len(n) == 1:
    if k == 1:
      return n[0]
    else:
      return 0
  else:
    if k == 1:
      m = n[:-1]
      return f(m,1) + 9
    else:
      r = n[-1]
      m = n[:-1]
      m2 = m.copy()
      if all(elem == 0 for elem in m):
        pass
      else:
        m2[-1] = m2[-1] - 1
        for i in range(len(m)):
          if m2[-i] < 0:
            m2[-i] = 9
            m2[-i-1] = m2[-i-1]
      return f(m,k) + f(m,k-1) * r + f(m2,k-1) * (9-r)
    
print(f(N,K))

Submission status: Wrong Answer

Solution code:
N = list(map(int,input()))
K = int(input())

def f(n,k):
  if k == 1:
    if len(n) == 1:
      return n[0]
    else:
      r = n[-1]
      m = n[:-1]
      return f(m,1) + 9
  else:
    if len(n) == 1:
      return 0
    else:
      r = n[-1]
      m = n[:-1]
      m2 = m.copy()
      if all(elem == 0 for elem in m):
        pass
      else:
        m2[-1] = m2[-1] - 1
        for i in range(len(m)):
          if m2[-i] < 0:
            m2[-i] = 9
            m2[-i-1] = m2[-i-1]
      return f(m,k) + f(m,k-1) * r + f(m2,k-1) * (9-r)
    
print(f(N,K))

Submission status: Wrong Answer

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

def f(n,k):
  if k == 1:
    if n < 10:
      return n
    else:
      r = n%10
      m = (n-r)/10
      return f(m,1) + 9
  else:
    if n < 10:
      return 0
    else:
      r = n%10
      m = (n-r)/10
      return f(m,k) + f(m,k-1) * r + f(m-1,k-1) * (9-r)
    
print(f(N,K))

Submission status: Wrong Answer

Solution code:
N=input()
K=input()
list=[]
#mist=[]
nist=[]
for i in range(int(N)):
    list.append(str(i+1))
import re
for i in range(int(N)):
#    mist.append('0')
    nist.append('A')
#    j=re.search('0',list[i])
#    if j!=None:
        #文字列.replace('変換元','変換後')
#        mist[i]=list[i].replace('0','A')
for i in range(int(N)):
    nist[i]=len(list[i])-list[i].count('0')
judge=0
print(nist)
for i in range(int(N)):
    if nist[i]==int(K):
        judge+=1
print(judge)
print(K)

Submission status: Wrong Answer

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

dp0 = [[0] * (K + 1) for _ in range(L + 1)]
dp1 = [[0] * (K + 1) for _ in range(L + 1)]

dp0[0][0] = 1

n = []
for i in N:
    n.append(int(i))

for i in range(L):
    D = n[i]
    for j in range(K + 1):
        if D == 0:
            dp0[i + 1][j] += dp0[i][j]
            dp1[i + 1][j] += dp1[i][j]
            if j < K:
                dp1[i + 1][j + 1] = dp1[i][j] * 9
        else:
            dp1[i + 1][j] += (dp0[i][j] + dp1[i][j])
            if j < K:
                dp0[i + 1][j + 1] += dp0[i][j]
                dp1[i + 1][j + 1] += (D - 1) * dp0[i][j]
                dp1[i + 1][j + 1] += 9 * dp1[i][j]

print(dp0)
print(dp1)
print(dp0[L][K] + dp1[L][K])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=len(str(n))
k=int(input())
dp=[[[0]*(k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][1][0]=1
for pos in range(l):
  num=int(str(n)[pos])
  for i in range(10):
    if i==0:
      for count in range(k+1):
        dp[pos+1][0][count]+=(dp[pos][0][count]+dp[pos][1][count])
    elif i<num:
      for count in range(k):
        dp[pos+1][0][count+1]+=(dp[pos][0][count]+dp[pos][1][count])
    elif i==num:
      for count in range(k):
        dp[pos+1][1][count+1]+=dp[pos][1][count]
        dp[pos+1][0][count+1]+=dp[pos][0][count]
    else:
      for count in range(k):
        dp[pos+1][0][count+1]+=dp[pos][0][count]
print(dp[l][0][k]+dp[l][1][k])

Submission status: Wrong Answer

Solution code:
def CountNotZero(n):
    NotZero=0
    while n>0:
        if (n%10)!=0:
            NotZero+=1
        n=int(n/10)  
    return NotZero

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

def main(n):
    answer=0
    while n>0: 
        if CountNotZero(n)==K:
            answer+=1
        n-=1
    return answer

main(N)

Submission status: Wrong Answer

Solution code:

from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N))) #桁数
ans = 0
k = K
l = len(S) #桁数

def C(n,r): #組み合わせ
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

if K > len(S):
    print(0)
    exit()

for i in range(l):
    if int(S[i]) != 0:
        if int(S[i-1]) == 0 or k == 1 or k < l:
            ans = ans + int(S[i]) + D(l-1,k)
        else:
            ans = ans + (int(S[i]-1))*D(l-1,k-1) + D(l-1,k)            
        k -= 1
        l -= 1
    else:
        if K == len(S):
            print(0)
            exit() 
        l -= 1
    if k < 1:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N))) #桁数
ans = 0
k = K
l = len(S) #桁数

def C(n,r): #組み合わせ
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

if K > len(S):
    print(0)
    exit()

for i in range(l):
    if k >= 1 and l != 1:
        if int(S[i]) != 0:
            ans = ans + (int(S[i])-1)*D(l-1,k-1) + D(l-1,k)
            k -= 1
            l -= 1
        else:
            if K == len(S):
                print(0)
                exit()
            else:
                l -= 1
    elif k == 1 and l == 1:
        ans = ans + int(S[i]) + D(l-1,k)
        k -= 1
        l -= 1
    else:      
        break

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N))) #桁数
ans = 0
k = K
l = len(S) #桁数

def C(n,r): #組み合わせ
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

if K > len(S):
    print(0)
    exit()

for i in range(l):
    if k > 1:
        if int(S[i]) != 0:
            ans = ans + (int(S[i])-1)*D(l-1,k-1) + D(l-1,k)
            k -= 1
            l -= 1
        else:
            if K == len(S):
                print(0)
                exit()
            else:
                l -= 1
    elif k == 1:
        ans = ans + int(S[i]) + D(l-1,k)
        k -= 1
        l -= 1
    else:      
        break

print(ans)

Submission status: Wrong Answer

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

l = len(str(n))

if l < k:
    t = 0
elif k == 1:
    r = int(str(n)[0])
    t = 9 * l - (9 - r)
elif k == 2:
    r, s = int(str(n)[0]), int(str(n)[1])
    t = 81 * l * (l-1) // 2 - 9 * (9-r) * (l-1) - (9-s)
else:
    r, s, u = int(str(n)[0]), int(str(n)[1]), int(str(n)[2])
    t = 729 * l * (l-1) * (l-2) // 6 - 81 * (9-r) * (l-1) * (l-2) // 2 - 9 * (9-s) * (l-2) - (9-u)
print(t)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N))) #桁数
ans = 0
k = K
l = len(S) #桁数

def C(n,r): #組み合わせ
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

if K > len(S):
    print(0)
    exit()

for i in range(l):
    if k >= 1 and int(S[i])!=0:
        ans = ans + (int(S[i])-1)*D(l-1,k-1) + D(l-1,k)
        k -= 1
        l -= 1
    elif k >= 1 and int(S[i])==0:
        if K == len(S):
            print(0)
            exit()
        else:
            l -= 1
    else:      
        break

ans += 1
print(ans)

Submission status: Wrong Answer

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

l = len(str(n))

if l < k:
    t = 0
elif k == 1:
    r = int(str(n)[0])
    t = 9*(l-1)+r
elif k == 2:
    r, s = int(str(n)[0]), int(str(n)[1])
    t = 81*(l-1)*(l-2)//2 + 9*(r-1)*(l-1) + s + 9*(l-2)
else:
    r, s, u = int(str(n)[0]), int(str(n)[1]), int(str(n)[2])
    t = 729*(l-1)*(l-2)*(l-3)//6 + 81*(r-1)*(l-1)*(l-2)//2 + 81*(l-2)*(l-3)//2 + 9*(s-1)*(l-2) + 9*(l-3) + u
print(t)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N))) #桁数
ans = 0
k = K
l = len(S) #桁数

def C(n,r): #組み合わせ
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

if K > len(S):
    print(0)
    exit()

for i in range(l):
    if k >= 1 and int(S[i])!=0:
        ans = ans + (int(S[i])-1)*D(l-1,k-1) + D(l-1,k)
        k -= 1
        l -= 1
    elif k >= 1 and int(S[i])==0:
        l -= 1
    else:  
        break

ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N))) #桁数
ans = 0
k = K
l = len(S) #桁数

def C(n,r): #組み合わせ
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

if K > len(S):
    print(0)
    exit()

for i in range(l):
    if k >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,k-1) + D(l-1,k)
        k -= 1
        l -= 1
    else:
        break

ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))
ans = 0
k = K
l = len(S)

def C(n,r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if k >= 1:
        #print('K:',k,',l:',l)
        #print((int(S[i])-1)*D(l-1,k-1)) #exa 3の時は1と2
        #print(D(l-1,k)) #S[0]==0の時の計算
        ans = ans + (int(S[i])-1)*D(l-1,k-1) + D(l-1,k)
        k -= 1
        l -= 1
    else:
        #ans += 1
        break

#print(K,len(S))
if K <= len(S):
    ans += 1

print(ans)

#https://atcoder.jp/contests/abc154/submissions/10100329

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))
ans = 0
l = len(S)

def C(n,r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        break

if ans != 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))
ans = 0
l = len(S)

def C(n,r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        ans += 1
        break

if ans != 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N)))
ans = 0
l = len(S)

def C(n,r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        break

if K <= len(S):
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
S = list(map(int,str(N)))
ans = 0
l = len(S)

def C(n,r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        break

if K <= l:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = input()
K = int(input())
lt,eq = 0,1
dp = np.zeros((101,2,5))

dn = len(N)
dp[0][eq][0] = 1
for i in range(dn):
    di = ord(N[i]) - ord('0')
    for k in range(4):
        dp[i+1][lt][k] = dp[i][lt][k] * 1 + dp[i][eq][k] * (1 if di == 1 else 0)
        if k: dp[i+1][lt][k] += dp[i][lt][k-1] * 9 + dp[i][eq][k-1] * max(0,di-1)
        if dp[i][eq][k]: dp[i+1][eq][k+(di>0)] = 1

print(int(dp[dn][lt][K] + dp[dn][eq][K]))

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))
ans = 0
l = len(S)

def C(n,r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        break
ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))
ans = 0
l = len(S)

def C(n,r):
    if n>r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

def D(i,j): 
    return (9**j)*C(i,j)

for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n = onem()
k = onem()

s = str(n)

dp0 = [[0 for j in range(4)] for i in range(len(str(n))+1)]
dp1 = [[0 for j in range(4)] for i in range(len(str(n))+1)]

po = 0

dp0[0][0] = 0
dp1[0][0] = 1

for i in range(1,len(str(n))+1):
    point = i - 1
    np = int(s[point])
    po += 1 if np == 0 else 0

    dp0[i][0] = 1
    dp1[i][0] = 0

    dp0[i][1] = dp1[i-1][0]*(max(0,np-1)) + dp0[i-1][0]*9 + dp0[i-1][1] + dp1[i-1][1]
    dp1[i][1] = 1 if i == 1 + po else 0

    dp0[i][2] = dp1[i-1][1] * (max(0,np-1)) + dp0[i-1][1] * (9) + dp0[i-1][2] + dp1[i-1][2]
    dp1[i][2] = 1 if i == 2 + po else 0

    dp0[i][3] = dp1[i-1][2] * (max(0,np-1)) + dp0[i-1][2] * (9) + dp0[i-1][3] + dp1[i-1][3]
    dp1[i][3] = 1 if i == 3 + po else 0
    


print(dp0[-1][k]+dp1[-1][k])

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[0])
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[0])
            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[0])
            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) * (len(N)-j-1)) // 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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n = onem()
k = onem()

s = str(n)

dp0 = [[0 for j in range(4)] for i in range(len(str(n))+1)]
dp1 = [[0 for j in range(4)] for i in range(len(str(n))+1)]


for i in range(1,len(str(n))+1):
    point = i - 1
    np = int(s[point])

    dp0[i][0] = 1
    dp1[i][0] = 0

    dp0[i][1] = dp1[i-1][0] + dp0[i-1][1]
    dp1[i][1] = 1 if i == 1 else 0

    dp0[i][2] = dp1[i-1][1] * (max(0,np-1)) + dp0[i-1][1] * (9) + dp0[i][2]
    dp1[i][2] = dp1[i-1][1] if i == 2 else 0

    dp0[i][3] = dp1[i-1][2] * (max(0,np-1)) + dp0[i-1][2] * (9) + dp0[i][3]
    dp1[i][3] = dp1[i-1][2] if i == 3 else 0


print(dp0[-1][k]+dp1[-1][k])

Submission status: Wrong Answer

Solution code:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

def listintinput():
    return list(map(int,input().split()))

def splitintinput():
    return map(int,input().split())

N = str(intinput())
K = intinput()
s = len(str(N))
flag = 0
dp = [[[0] * 3 for i in range(5)] for j in range(150)]
dp[0][0][0] = 1
dp[1][1][1] += int(N[0])-1
if s > 1:
    dp[2][2][1] += int(N[1])-1
if s > 2:
    dp[3][3][1] += int(N[2])-1
for h in range(1,s+1):
    dp[h][0][0] = 0
    dp[h][0][1] = 1
    for i in range(1,4):
        dp[h][i][0] += dp[h-1][i-1][0]
        dp[h][i][1] +=  dp[h-1][i-1][1] * 9 + dp[h-1][i][0] + dp[h-1][i][1]

print(dp[s][K][0]+dp[s][K][1])

Submission status: Wrong Answer

Solution code:
n=int(input())
k=int(input())
c=0
res=0
for i in range(1,n+1):
  for j in str(i):
    if j!=0:
      c+=1
  if c==k:
    res+=1
print(res)