TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Submission attempts (in order):
from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
    
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    
    m, r = divmod(N,10)
    ans = 0
        
        ans += solver(m, K-1) * r
        ans += solver(m-1, K-1) * (9-r)
    ans += solver(m, K)
    return ans


n = int(input())
k = int(input())
print(solver(n,k)


from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    m, r = divmod(N,10)
    ans = 0
    if K >= 1:
        ans += solver(m, K-1) * r
        ans += solver(m-1, K-1) * (9-r)
    ans += solver(m, K)
    return ans


n = int(input())
k = int(input())
print(solver(n,k))


Verdicts: Runtime Error

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

Submission attempts (in order):
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])


n=input()
k=int(input())
l=len(n)

dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]

dp[0][1][1]=int(n[0]-1)
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=n[i]
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
print(dp[l-1][k][0]+dp[l-1][k][1])

n=input()
k=int(input())
l=len(n)
dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
for i in range(1,L):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now=0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=dp[b][j][1]*9
  dp[i][1][1]+=9
print(dp[l-1][k][0]+dp[l-1][k][1])
           

n=input()
k=int(input())
l=len(n)

dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]

dp[0][1][1]=int(n[0]-1)
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=n[i]
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])


n=input()
k=int(input())
l=len(n)

dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]

dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

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

Submission attempts (in order):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    
    dp_1 = [[0] * (10) for _ in range(length)]

    
    dp_2 = [[0] * (10) for _ in range(length)]

    dp_1[0][0] = 1
    dp_1[0][1] = int(N[0]) - 1

    dp_2[0][1] = 1

    for i in range(1, length):
        
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        
        if N[i] == "0":
            for i in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()


import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    
    dp_1 = [[0] * (10) for _ in range(length)]

    
    dp_2 = [[0] * (10) for _ in range(length)]

    dp_1[0][0] = 1
    dp_1[0][1] = int(N[0]) - 1

    dp_2[0][1] = 1

    for i in range(1, length):
        
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        
        if N[i] == "0":
            for k in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()


Verdicts: Runtime Error

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

Submission attempts (in order):
#!python3

from math import factorial

iim = lambda: map(int, input().rstrip().split())

def cmb(a, b):
    c = a - b
    if c < b:
        b = c
    if b == 0: return 1

    ans = 1
    for i in range(b):
        ans *= a - i

    return ans // factorial(b)

def cnt(N, K):
    if K == 0:
        return 1

    n10 = 10 ** (K-1)
    if N < n10:
        return 0

    n10 *= 10
    k1 = K - 1
    n9 = 9 ** K
    n91 = 9 ** k1

    ans = 0
    a = n10
    i = 0
    while a < N:
        a *= 10; i += 1
    a //= 10; i -= 1
    if i > 0:
        ans = cmb(i+K, K) * n9
        #print(f"{i+K}C{K}", ans)

    n, b = divmod(N, a)
    if n > 1:
        ans += (n - 1) * cnt(a-1, K - 1)
    ans += cnt(b, K - 1)


    return ans

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

    print(cnt(N, K))

if __name__ == "__main__":
    resolve()


#!python3


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = list(map(int, input()))
    K = int(input())
    size = len(N)

    if size < K:
        print(0)
        return

    dp = [[[0]*(size+1) for j in range(2)] for i in range(size+1)]

    dp[0][0][0] = 1
    for i in range(size):
        for k in range(min(i+1, K+1)):
            dp0, dp1 = dp[i], dp[i+1]

            dp1[1][k+1] += 9 * dp0[1][k]
            dp1[1][k]   +=     dp0[1][k]

            x, y = N[i], dp0[0][k]
            if x == 0:
                dp1[0][k] += y
            else:
                dp1[1][k] += y
                dp1[0][k+1] += y
                dp1[1][k+1] += (x-1) * y
        #print(dp1)

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

if __name__ == "__main__":
    resolve()


Verdicts: Wrong Answer

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

Submission attempts (in order):
N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): 
        if k -1 >= 0:
            if l != 0: 
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: 
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: 
            if l != 0: 
                #dp[i][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + dp[i - 1][0][k] 
            else: 
                dp[i][0][k] = dp[i - 1][0][k] 
                dp[i][1][k] = dp[i - 1][1][k] # =1

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

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

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): 
        if k -1 >= 0:
            if l != 0: 
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: 
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: 
            dp[i][0][k] = 0 
            dp[i][1][k] = 1 

#print(dp)
print(dp[m][0][K] + dp[m][1][K])

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

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): 
        if k == 0: 
            dp[i][0][k] = 0 
            dp[i][1][k] = 1 
        else k -1 >= 0:
            if l != 0: 
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: 
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]

#print(dp)
print(dp[m][0][K] + dp[m][1][K])

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

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): 
        if k == 0: 
            dp[i][0][k] = 0 
            dp[i][1][k] = 1 
        else: 
            if l != 0: 
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: 
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]

#print(dp)
print(dp[m][0][K] + dp[m][1][K])


Verdicts: Runtime Error

Runtime Error

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

Submission attempts (in order):
from operator import mul
from functools import reduce

def com(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 run():
  N = int(input())
  K = int(input())
  Nnum = len(str(N))
  #1
  all1 = com(Nnum, K)*9**K
  #2
  all2 = (9-int(str(N)[0]))*com(Nnum-1, K-1)*9**(K-1)
  if K == 1:
    print(all1-all2)
  #3
  elif K == 2:
    all3 = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        all3 += 9-N2
        break
      all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
  #4
  else:
    all3 = 0
    count = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        if count == 0:
          all3 += (9-N2)*com(Nnum-n-1, 1)*9
        elif count == 1:
          all3 += 9-N2
        count += 1
        if count == 2:
          break
      elif count == 0:
        all3 += 9*(Nnum-n-1)*9
      else:
        all3 += 9
    else:
      if count == 0:
        all3 = com(Nnum-1, 2)*9*9
      else
        all3 = (Nnum-1)*9
    print(all1-all2-all3)
    
  

if __name__ == '__main__':
    run()

def run():
  N = list(map(int, list(input())))
  K = int(input())
  Nlen = len(N)
  dp = [[[0]*(K+2) for _ in range(2)] for n in range(Nlen+1)]
  dp[0][0][0] = 1
  for nlen in range(Nlen):
    dN = N[nlen]
    for d in range(10):
      for j in range(2):
        for k in range(K+2):
          flagj = j or d < dN
          if (flagj == 0) and (d > dN): continue
          flagk = min(K+1, k+(d != 0))
          dp[nlen+1][flagj][flagk] += dp[nlen][j][k]
  print(dp[-1][0][K]+dp[-1][1][K])
  
if __name__ == '__main__':
    run()

Verdicts: Runtime Error

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

Submission attempts (in order):
N, K = map(int, input().split())
P = list(map(int, input().split()))
Pe = [(i+1)/2 for i in P]

maxsum = -1
cur = sum(Pe[0:K])
maxsum = cur
for i in range(1, N-K+1):
    cur = cur - Pe[i-1] + Pe[i+K-1]
    if cur > maxsum:
        maxsum = cur

print(maxsum)

from collections import defaultdict
from functools import lru_cache

N = input().strip()
K = int(input().strip())
lenN = len(N)


@lru_cache(maxsize=None)
def f(keta, flag, k):
    if keta == lenN-1:
        if k == K:
            return 1
        else:
            return 0
    #if keta in memo and flag in memo[keta] and k in memo[keta][flag]:
    #    return memo[keta][flag][k]
    nketa = keta + 1
    maxi = int(N[nketa]) if flag else 9
    res = 0
    for i in range(maxi+1):
        nflag = flag and (int(N[nketa]) == i)
        nk = k if i == 0 else k + 1
        if nk > K:
            continue
        res += f(nketa, nflag, nk)
    #memo[keta][flag][k] = res
    return res

print(f(-1, True, 0))


Verdicts: Runtime Error

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

Submission attempts (in order):
from functools import lru_cache
@lru_cache(None)
n=int(input())
k=int(input())
def cal(n,k):
  if n<10:
    if k==0: return 1
    if k==1: return n
    return 0
  q,r=divmod(n,10)
  ret=0
  if k>=1:
    ret+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))

from functools import lru_cache
n=int(input())
k=int(input())
@lru_cache(None)
def cal(n,k):
  if n<10:
    if k==0: return 1
    if k==1: return n
    return 0
  q,r=divmod(n,10)
  ret=0
  if k>=1:
    ret+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))

Verdicts: Runtime Error

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

Submission attempts (in order):
##toketenaiiiiiiii!!!!!

def f(i,k):
    if i == 0:
        return 0
    num = int(s[-i])
    if k == 0: return 1
    if num==0:
        return ncr(i-1,k)*9**k
    return (num-1)* ncr(i-1,k-1)*9**(k-1)+ncr(i-1,k)*9**k


def g(i,k):
    if i == 0:
        if k==0:return 1
        else:return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 1
        else:return 0

    if num==0:
        return f(i-1,k) +g(i-1,k)
    else:
        return f(i-1,k-1) + g(i-1,k-1)



def ncr(n,r):
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
    return x//y

s = input()
k = int(input())
l= len(s)
print(f(l,k)+g(l,k))



def f(i,k):
    if i == 0:
        return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 0
        else: return 1
    if num==0:
        return 0
    return (num-1)* ncr(i-1,k-1)*9**(k-1)+ncr(i-1,k)*9**k


def g(i,k):
    if i == 0:
        if k==0:return 1
        else:return 0
    num = int(s[-i])
    if k == 0:
        if num ==0:return 1
        else:return 0

    if num==0:
        return f(i-1,k) +g(i-1,k)
    else:
        return f(i-1,k-1) + g(i-1,k-1)



def ncr(n,r):
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
    return x//y

s = input()
k = int(input())
l= len(s)
print(f(l,k)+g(l,k))


Verdicts: Wrong Answer

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

Submission attempts (in order):
n = input()
k = int(input())
l = len(n)

dp = [[[0 for a in range(k+1)] for b in range(2)] for c in range(l+5)]

dp[0][0][0] = 1
#print(dp)

for a in range(l) :
    for b in range(2) :
        for c in range(k+1) :
            for d in range(10) :
                na = a
                nb = b
                nc = c
                if b == 0 :
                    if d > int(n[a]) :
                        continue
                    if d < int(n[a]) :
                        nb = 1
                if c == k and d > 0 :
                    continue
                if d != 0 :
                    nc += 1
                #print(a,b,c,na,nb,nc)
                dp[na+1][nb][nc] += dp[a][b][c]


print(dp[l][0][k])
print(dp[l][1][k])
print(dp[l][0][k]+dp[l][1][k])


import math

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

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

ans = 0

for i in range(k, len(str(n))) :
    if k == i or k == 1:
        ans += 9**(k)
        continue
    ans += combinations_count(i-1, k) * 9**(k)

print(ans)


n = input()
k = int(input())
l = len(n)

dp = [[[0 for a in range(k+1)] for b in range(2)] for c in range(l+5)]

dp[0][0][0] = 1
#print(dp)

for a in range(l) :
    for b in range(2) :
        for c in range(k+1) :
            for d in range(10) :
                na = a
                nb = b
                nc = c
                if b == 0 :
                    if d > int(n[a]) :
                        continue
                    if d < int(n[a]) :
                        nb = 1
                if c == k and d > 0 :
                    continue
                if d != 0 :
                    nc += 1
                #print(a,b,c,na,nb,nc)
                dp[na+1][nb][nc] += dp[a][b][c]

#print(dp[l][0][k])
#print(dp[l][1][k])
print(dp[l][0][k]+dp[l][1][k])


Verdicts: Wrong Answer

Wrong Answer

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

Submission attempts (in order):
from scipy.misc import comb
N=input()
K=int(input())
if len(N)<K:
    print(0)
    exit()
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += (int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*(len(N)-2)+int(N[1])
else:
    ans += int(N[2])+(len(N)-3)*9+(int(N[1])-1)*(len(N)-2)*9+comb(len(N)-2,2)*81
print(ans)

from scipy.misc import comb
import math
N=input()
K=int(input())
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += max(0,int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*max(0,len(N)-2)+int(N[1])
else:
    ans += int(N[2])+max(0,len(N)-3)*9+max(0,int(N[1])-1)*max(0,len(N)-2)*9+comb(len(N)-2,2)*81
print(math.ceil(ans))

from scipy.misc import comb
N=input()
K=int(input())
if len(N)<K:
    print(0)
    exit()
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += (int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*(len(N)-2)+int(N[1])
else:
    ans += int(N[2])+(len(N)-3)*9+(int(N[1])-1)*(len(N)-2)*9+comb(len(N)-2,2)*81
print(int(ans))

from scipy.misc import comb
import math
N=input()
K=int(input())
if len(N)<K:
    print(0)
    exit()
if K !=1:
    ans = 0
elif len(N)<2:
    print(int(N))
    exit()
else:
    ans = 9
for i in range(2,len(N)):
    ans += 9*comb(i-1,K-1)*(9**(K-1))
ans += max(0,int(N[0])-1)*comb(len(N)-1,K-1)*9**(K-1)
if K==1:
    ans += 1
elif K==2:
    ans += 9*max(0,len(N)-2)+int(N[1])
else:
    ans += int(N[2])+max(0,len(N)-3)*9+max(0,int(N[1])-1)*max(0,len(N)-2)*9+comb(len(N)-2,2)*81
print(math.ceil(ans))

N=input()
K=int(input())
dp_0 = [[0]*(len(N)) for i in range(K+1)]
dp_1 = [[0]*(len(N)) for i in range(K+1)]
dp_0[0][0]=1
dp_0[1][0]=int(N[0])-1
dp_1[1][0]=1
for i in range(len(N)-1):
    for j in range(K+1):
        if j==K:
            dp_0[j][i+1] += dp_0[j][i]
        elif j==0:
            dp_0[j][i+1] =dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        else:
            dp_0[j][i+1] += dp_0[j][i]
            dp_0[j+1][i+1] += dp_0[j][i]*9
        if j != K and N[i+1] != '0':
            dp_0[j+1][i+1] += (int(N[i+1])-1)*dp_1[j][i]
            dp_0[j][i+1] += dp_1[j][i]
            dp_1[j+1][i+1] = dp_1[j][i]
        elif N[i+1] =='0':
            dp_1[j][i+1] = dp_1[j][i]
        else:

            dp_0[j][i+1] += dp_1[j][i]

print(dp_0[K][len(N)-1]+dp_1[K][len(N)-1])

Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

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

Submission attempts (in order):
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))

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:
    r = n[-1]
    m = n[:-1]
    m2 = m.copy()
    m2[-1] = m2[-1] - 1
    for i in range(len(m)):
      if m2[-i] < 0:
        m2[-i] += 10
        m2[-i-1] = m2[-i-1] - 1
    if k == 1:
      m = n[:-1]
      return f(m,1) + 9
    else:
      return f(m,k) + f(m,k-1) * r + f(m2,k-1) * (9-r)
    
print(f(N,K))

Verdicts: Wrong Answer

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

Submission attempts (in order):
N=input()
K=int(input())
l=len(N)
dp=[[0]*(l+1) for i in range(K+1)]
dp[0][0]=1
x=0
for i,n in enumerate(N):
    n=int(n)
    dp[0][i+1]=1
    if n==0:
        for j in range(1,K+1):
            dp[j][i+1]=dp[j][i]+dp[j-1][i]*9
    else:
        for j in range(1,K+1):
        dp[j][i+1]=dp[j][i]+dp[j-1][i]*9 if i-j>-1 else 0 if i-j<-1 else n if i==0 else (dp[j-1][i]-1)*9+n
print(dp[-1][-1])

N=input()
K=int(input())
l=len(N)
dp=[[0]+[1]*l]+[[0]*(l+1) for i in range(K)]
dp2=[[1]+[0]*l]+[[0]*(l+1) for i in range(K)]
for i,n in enumerate(N):
    n=int(n)
    for j in range(K):
        dp[j+1][i+1]=dp[j][i]*9+dp[j+1][i]+(dp2[j][i]*(n-1)+dp2[j+1][i] if n>0 else 0)
        dp2[j+1][i+1]=dp2[j][i] if n>0 else dp2[j+1][i]
print(dp[-1][-1]+dp2[-1][-1])

Verdicts: Runtime Error

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

Submission attempts (in order):
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())
@lru_cache(None)
def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))

# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7   
N = readline().decode().rstrip()
K = int(readline())
L = len(N)

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
    for j in range(4):
        for k in range(2):
            nd = int(N[i])
            for d in range(10):
                ni = i + 1; nj = j; nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
print(dp[L][K][0]+dp[L][K][1])

Verdicts: Runtime Error

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

Submission attempts (in order):
def func(p):
    r=0
    for q in range(2,p-1):
        r+=q*(q-1)//2
    return r

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

n=len(str(N))
x=int(str(N)[0])
l=0
y=0
z=0
if n>=2:
    for i in range(1,n):
        if str(N)[i]==0:
            l+=1
        else:
            y=int(str(N)[i])
            if i<n-1:
                z=int(str(N)[i+1])

print(l,y)

s=0
if n-l-2>0:
    s=(n-l-1)*(n-l-2)//2

ans=0

if K==1:
    ans=x+9*(n-1)

elif K==2:
    ans=y+9*max(0,x-1)+9*max(0,n-l-2)+81*(n-2)*(n-1)//2

else:
    ans=y*z+x*81+x*81*s+729*func(n)

print(ans)






#WA



N=str(input())
K=int(input())
L=len(N)


DP=[[[0]*5 for index1 in range(2)] for index2 in range(L+1)]

DP[0][0][0]=1



for i in range(1,L+1):
    #smaller=1->smaller=1
    DP[i][1][4]+=DP[i-1][1][4]*10+DP[i-1][1][3]*9
    DP[i][1][3]+=DP[i-1][1][3]+DP[i-1][1][2]*9
    DP[i][1][2]+=DP[i-1][1][2]+DP[i-1][1][1]*9
    DP[i][1][1]+=DP[i-1][1][1]+DP[i-1][1][0]*9
    DP[i][1][0]+=DP[i-1][1][0]

    n=int(N[i-1])

    #smaller=0->smaller=1
    
    
    if n==1:
        DP[i][1][4]+=DP[i-1][0][4]
        DP[i][1][3]+=DP[i-1][0][3]
        DP[i][1][2]+=DP[i-1][0][2]
        DP[i][1][1]+=DP[i-1][0][1]
        DP[i][1][0]+=DP[i-1][0][0]
    elif n>=2:
        DP[i][1][4]+=DP[i-1][0][4]*n+DP[i-1][0][3]*(n-1)
        DP[i][1][3]+=DP[i-1][0][3]+DP[i-1][0][2]*(n-1)
        DP[i][1][2]+=DP[i-1][0][2]+DP[i-1][0][1]*(n-1)
        DP[i][1][1]+=DP[i-1][0][1]+DP[i-1][0][0]*(n-1)
        DP[i][1][0]+=DP[i-1][0][0]

    #smaller=0->smaller=0
    
    if n==0:
        DP[i][0][4]+=DP[i-1][0][4]
        DP[i][0][3]+=DP[i-1][0][3]
        DP[i][0][2]+=DP[i-1][0][2]
        DP[i][0][1]+=DP[i-1][0][1]
        DP[i][0][0]+=DP[i-1][0][0]
    else:
        DP[i][0][4]+=DP[i-1][0][4]+DP[i-1][0][3]
        DP[i][0][3]+=DP[i-1][0][2]
        DP[i][0][2]+=DP[i-1][0][1]
        DP[i][0][1]+=DP[i-1][0][0]

print(DP[L][0][K]+DP[L][1][K])



Verdicts: Wrong Answer

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

Submission attempts (in order):
N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = 0
ans = 0
for i in range(n):
    if k > K:
        break
    x = int(S[i])
    y = n - 1 - i
    z = K - k
    if i == 0:
        ans += (x-1)*(9**(y-z))*c(y,z)
        continue
    if x == 0:
        k += 1
        continue
    if x == 1:
        if k == K:
            continue
        else:
            ans += (9**(y-z+1))*c(y,z-1)
            continue
    ans += (x-2)*(9**(y-z))*c(y,z)
    if k < K:
        ans += 9**(y-z+1)*c(y,z-1)
print(ans)

N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
    if i == n-1:
        if k == 0:
            ans += 1
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

N = int(input())
K = int(input())
S = str(N)
n = len(S)
def c(x,y):
    X = 1
    Y = 1
    for i in range(y):
        X *= (x-i)
        Y *= (y-i)
    return X//Y
k = K
ans = 0
for i in range(n):
    if k < 0:
        break
    x = int(S[i])
    y = n - 1 - i
    if i == 0:
        k -= 1
        ans += (x-1)*(9**k)*(c(y,k))
        continue
    if x == 0:
        continue
    k -= 1
    if k >= 0:
        ans += (x-1)*(9**k)*(c(y,k))
    ans += (9**(k+1))*c(y,(k+1))
if i == n-1:
    if k == 0:
        ans += 1
for i in range(1,n):
    if i < K:
        continue
    ans += (9**K)*c(i-1,K-1)
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

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

Submission attempts (in order):

n = list(map(int, list(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)]

for i in range(1, l+1):
    dp0[i][0] = 1

dp1[0][0] = 1

for i in range(l):
    for j in range(k):

        if n[i] > 0:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1] + dp1[i][j+1] + (n[i]-1)*dp1[i][j]
            dp1[i + 1][j + 1] = dp1[i][j]
        else:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1]
            dp1[i + 1][j + 1] = dp1[i][j + 1]



print(dp1[l][k])
print(dp0[l][k] + dp1[l][k])



n = list(map(int, list(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)]

for i in range(1, l+1):
    dp0[i][0] = 1

dp1[0][0] = 1

for i in range(l):
    for j in range(k):

        if n[i] > 0:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1] + dp1[i][j+1] + (n[i]-1)*dp1[i][j]
            dp1[i + 1][j + 1] = dp1[i][j]
        else:

            dp0[i+1][j+1] = \
                9*dp0[i][j] + dp0[i][j+1]
            dp1[i + 1][j + 1] = dp1[i][j + 1]



# print(dp1[l][k])
print(dp0[l][k] + dp1[l][k])


Verdicts: Wrong Answer

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

Submission attempts (in order):
rom math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

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

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

    ans = func(N, K)

    print(ans)

def func(N, K):
    if len(N) < K:
        return 0

    if K == 0:
        return 1

    n = int(N[0])

    if len(N) == 1:
        if K > 1:
            return 0
        else:
            return n

    ret = 0
    if K > 1:
        ret += func(N[1:], K-1)
    else:
        ret += 1
    l = len(N[1:])

    ret += (n - 1) * func('9' * l, K - 1)
    ret += func('9'* l, K)

    
    

    return ret
    

if __name__ == '__main__':
    main()

from math import factorial


def nCr(n, r):
    if r <= 0:
        return 0

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

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

def rec(n, k, smaller):
    n = n.lstrip('0')

    if k == 0:
        return 1

    if len(n) < k:
        return 0

    if k == 1:
        if len(n) == 1:
            return int(n)


    if smaller:
        return nCr(len(n), k) * 9 ** k


    ret = 0
    ret += rec(n[1:], k-1, False)
    ret += rec('9'*(len(n)-1), k-1, True) * (int(n[0]) - 1)
    ret += rec('9'*(len(n)-1), k, True)

    return ret
    
ans = rec(N, K, False)
print(ans)



Verdicts: Runtime Error

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

Submission attempts (in order):
import sys
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()
length = 0
for i in range(1, 100):
    if 10 ** i > N:
        length = i
        break

c = factorial(length) // factorial(K) // factorial(lenght-K)
c_1 = factorial(length-1) // factorial(K-1) // factorial(lenght-K-1)
print(c)
answer = 0
top = int(str(N)[0])
answer = factorial(length-1) // factorial(K) // factorial(lenght-K-1) * 9 ** K 
answer += factorial(length) // factorial(K) // factorial(lenght-K) * (top-1) * 9 ** K 
print(answer)

# coding: utf-8
import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
K = ir()

@lru_cache(None)
def solve(N, K):
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    q, r = divmod(N, 10)
    ret = 0
    if K > 0:
        ret += solve(q, K-1) * r
        ret += solve(q-1, K-1) * (9-r)
    ret += solve(q, K)  
    return ret

answer = solve(N, K)
print(answer)


Verdicts: Runtime Error

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

Submission attempts (in order):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    K = int(input())
    if N <= 1000:
        count = 0
        for i in range(1, N + 1):
            d = 0
            ci = i
            while ci > 0:
                d += (1 if ci % 10 > 0 else 0)
                ci //= 10
            if d == K: count += 1
    else:
        strN = str(N)
        dig = len(strN)
        DPsmall = [[0 for j in range(K + 1)] for i in range(dig)]
        DPsmall[0][0] = 1
        DPsmall[0][1] = int(strN[0]) - 1
        for i in range(1, dig):
            DPsmall[i][0] = 1
            for j in range(1, K + 1):
                DPsmall[i][j] += DPsmall[i-1][j-1] * 9 + DPsmall[i-1][j]
            
        DPlarge = [[0 for j in range(K + 1)] for i in range(dig)] 
        DPlarge[0][0] = 1
        for i in range(1, dig):
            if strN[i] == "0": DPlarge[i][0] = DPlarge[i-1][0]
            else: DPlarge[i][0] = DPlarge[i-1][0] + 1
            for j in range(1, K + 1):
                if DPlarge[i-1][0] == j - 1: DPlarge[i][j] += (int(strN[i]) - 1 if strN[i] != "0" else 0)
                if DPlarge[i-1][0] == j: DPlarge[i][j] += (1 if strN[i] != "0" else 0)

                DPlarge[i][j] += DPlarge[i-1][j] 
                if j > 1: DPlarge[i][j] += DPlarge[i-1][j-1] * 9 

        ans = DPsmall[dig-1][K] + DPlarge[dig-1][K]
        if DPlarge[dig-1][0] == K: ans += 1
        print(ans)   
        #print(DPsmall)
        #print(DPlarge)

    return 0

if __name__ == "__main__":
    solve()

import sys

def solve():
    input = sys.stdin.readline
    N = input().strip("\n")
    K = int(input())
    dig = len(N)
    DP = [[0] * (K + 1) for _ in range(dig)]
    DP[0][0] = 1
    DP[0][1] = int(N[0]) - 1
    for i in range(1, dig):
        DP[i][1] = 9
        if N[i] != "0": 
            DP[i][0] = DP[i-1][0] + 1
            if DP[i-1][0] <= K: DP[i][DP[i-1][0]] += 1
            if DP[i-1][0] <= K - 1: DP[i][DP[i-1][0] + 1] += int(N[i]) - 1     
        else: DP[i][0] = DP[i-1][0]
        for j in range(1, K): DP[i][j+1] += DP[i-1][j] * 9
        for j in range(1, K + 1): DP[i][j] += DP[i - 1][j]
    if DP[dig - 1][0] == K: DP[dig - 1][K] += 1
    print(DP[dig - 1][K])
    #print(DP)

            
    return 0

if __name__ == "__main__":
    solve()

Verdicts: Wrong Answer

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

Submission attempts (in order):
import numpy as np
n=input()
k=int(input())
dp=np.zeros((len(n)+1,k+1,2))
dp[0][0][0]=1
for i in range(1,len(n)+1):
    for j in range(int(n[i-1])):
        if j==0:
            dp[i][1]+=dp[i-1][0]
        else:
            dp[i][1][1:]+=dp[i-1][0][:-1]
    for j in range(10):
        if j==0:
            dp[i][1]+=dp[i-1][1]
        else:
            dp[i][1][1:]+=dp[i-1][1][:-1]
    if int(n[i-1])==0:
        dp[i][0]+=dp[i-1][0]
    else:
        dp[i][0][1:]+=dp[i-1][0][:-1]
print(dp[-1][0][-1]+dp[-1][1][-1])


n=input()
k=int(input())
dp=[[[0]*(k+1)for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0]=1
for i in range(1,len(n)+1):
    for j in range(int(n[i-1])):
        if j==0:
            for h in range(k+1):
                dp[i][1][h]+=dp[i-1][0][h]
        else:
            for h in range(k):
                dp[i][1][h+1]+=dp[i-1][0][h]
    for j in range(10):
        if j==0:
            for h in range(k+1):
                dp[i][1][h]+=dp[i-1][1][h]
        else:
            for h in range(k):
                dp[i][1][h+1]+=dp[i-1][1][h]
    if int(n[i-1])==0:
        for h in range(k+1):
            dp[i][0][h]+=dp[i-1][0][h]
    else:
        for h in range(k):
            dp[i][0][h+1]+=dp[i-1][0][h]
print(dp[-1][0][-1]+dp[-1][1][-1])

Verdicts: Wrong Answer

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

Submission attempts (in order):
MOD = 10**9+7
fac = [1, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * pow(fac[r], mod-2, mod) * pow(fac[n-r], mod-2, mod) % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def g(x, y):
    return ((y+2) * modcmb(x+y+2, x, MOD) - (x+1)) * pow(x+1, MOD-2, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = g(r2, c2) - g(r1-1, c2) - g(r2, c1-1) + g(r1-1, c1-1)
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


def f(n, k):
    
    # dp[i][smaller][j]
    
    
    n = str(n)
    L = len(n)

    dp = [[[0]*(k+2) for i in range(2)] for j in range(L+1)]
    dp[0][0][0] = 1

    for i in range(L):
        D = int(n[i])
        for smaller in range(2):
            for j in range(k+1):
                for d in range((9 if smaller else D)+1):
                    dp[i+1][smaller or (d < D)][j + (d != 0)] += dp[i][smaller][j]

    return dp[L][0][k] + dp[L][1][k]


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

    print(f(N, K))


if __name__ == "__main__":
    main()


Verdicts: Runtime Error

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

Submission attempts (in order):
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 0
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

n = int(input())
k = int(input())
print(solve(n,k))

def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

n = int(input())
k = int(input())
print(solve(n,k))


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

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1):
        dp[i][1][k] += dp[i - 1][1][k]
        if l != 0:
            dp[i][1][k] += dp[i - 1][0][k]
        else:
            dp[i][0][k] += dp[i - 1][0][k]
        if k - 1 >= 0:
            dp[i][1][k] += 9 * dp[i - 1][1][k - 1]
            if l != 0:
                dp[i][0][k] += dp[i - 1][0][k - 1]
                dp[i][1][k] += (l - 1) * dp[i - 1][0][k - 1]

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


Verdicts: Wrong Answer

Runtime Error

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

Submission attempts (in order):
N = int(input())
K = int(input())

def c(n,k):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k == 2:
		return n*(n-1)//2
	else:
		return n*(n-1)*(n-2)//6
def f(N, K):
	if N == 0:
		return 0
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit-1, K) * (9 ** K)
	a = 10**(digit-1)
	d = N // a
	ret += (d-1) * c(digit-1, K-1) * (9 ** (K-1))
	ret += f(N - d*a, K-1)

	return ret

print(f(N,K))

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

def c(n,k):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k == 2:
		return n*(n-1)//2
	else:
		return n*(n-1)*(n-2)//6
def f(N, K):
	if N == 0 and K > 0:
		return 0

	if K == 0:
		return 1
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit-1, K) * (9 ** K)
	a = 10**(digit-1)
	d = N // a
	ret += (d-1) * c(digit-1, K-1) * (9 ** (K-1))
	ret += f(N - d*a, K-1)

	return ret

print(f(N,K))


Verdicts: Wrong Answer

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

Submission attempts (in order):
N = int(input())
K = int(input())
L = len(str(N))

def solve(num_str, k, smaller):
    if k > 0 and len(num_str) == L:
        return 0
    if k == 0 or num_str == "":
        return 1

    elif smaller:
        keta = len(num_str)
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

N = int(input())
K = int(input())
L = len(str(N))

def solve(num_str, k, smaller):
    if num_str == "" and k > 0:
        return 0
    if k == 0 or num_str == "":
        return 1

    elif smaller:
        keta = len(num_str)
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

Verdicts: Wrong Answer

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

Submission attempts (in order):
n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	for f in range(2):
		for j in range(k+1):
			for l in range(10 if f else int(c)+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])

n=input()
k=int(input())
dp=[[[0]*(k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0]=1
for i,c in enumerate(n):
	c=int(c)
	for f in range(2):
		for j in range(k+1):
			for l in range(10*f or c+1):
				dp[i+1][f or l<c][j+(l>0)]+=dp[i][f][j]
print(dp[-1][0][k]+dp[-1][1][k])

Verdicts: Runtime Error

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

Submission attempts (in order):
def comb(n, k):
  if 0 <= k <= n:
    c = 1
    for i in range(k):
      c *= n-i
      c //= i+1
    return c
  else:
    return 0

n = [int(i) for i in input()]
l = len(n)
k = int(input())
count = 0
for i in range(min(l, k+1)):
  count += 9 ** (k-i) * comb(l-i-1, k-i)
  count += 9 ** (k-i-1) * comb(l-i-1, k-i-1) * (n[i]-1)
print(count)

def comb(n, k):
  if 0 <= k <= n:
    c = 1
    for i in range(k):
      c *= n-i
      c //= i+1
    return c
  else:
    return 0

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1 and n[i] > 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  if n[i] > 0:
    k -= 1
  if k < 0:
    break
print(count)

def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1 and n[i] > 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  else:
    break
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  if n[i] > 0:
    k -= 1
print(count)

def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
if l == k:
  count = 1
else:
  count = 0
for i in range(l):
  print(i, count)
  # n[:i] 0 {1..9}*k 0*(l-i-1-k)
  count += 9 ** k * comb(l-i-1, k)
  # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
  if k >= 1:
    count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
  else:
    break
  # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
  k -= 1
print(count)

def comb(n, k):
  c = 1
  for i in range(k):
    c *= n-i
    c //= i+1
  return c

n = [int(i) for i in input()]
l = len(n)
k = int(input())
count = 0
for i in range(l):
  if n[i] > 0:
    # n[:i] 0 {1..9}*k 0*(l-i-1-k)
    count += 9 ** k * comb(l-i-1, k)
    # n[:i] {1..(n[i]-1)} {1..9}*(k-1) 0*(l-i-1-k)
    if k >= 1:
      count += 9 ** (k-1) * comb(l-i-1, k-1) * (n[i]-1)
    else:
      break
    # Next is n[:i+1] {1..9}*(k-1) 0*(l-i-k)
    k -= 1
  if i == l-1 and k == 0:
    count += 1
print(count)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

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

Submission attempts (in order):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

n, k = map(int, read().split())


@lru_cache(None)
def check(n, k):
    a, b = divmod(n, 10)
    cnt = 0
    if k >= 1:
        cnt += check(a, k - 1) * b
        cnt += check(a - 1, k - 1) * (9 - b)
    cnt += check(a, b)
    return cnt


if n < 10:
    if k == 1:
        print(n)
    else:
        print(0)
else:
    print(check(n, k))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

n, k = map(int, read().split())


@lru_cache()
def check(n, k):
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    a, b = divmod(n, 10)
    cnt = 0
    if k >= 1:
        cnt += check(a, k - 1) * b
        cnt += check(a - 1, k - 1) * (9 - b)
    cnt += check(a, k)
    return cnt


print(check(n, k))


Verdicts: Runtime Error

Accepted