TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
N=2*10**5+7
n,k=map(int,input().split())
List=list(map(float,input().split()))
for i in range(n):
    List[i]=(1+List[i])/2
for i in range(1,n):
    List[i]+=List[i-1]
ans=0.0
for i in range(0,n-k+1):
    ans=max(ans,List[i+k-1]-List[max(0,i-1)])
print(ans)


N=2*10**5+7
n,k=map(int,input().split())
List=list(map(float,input().split()))
for i in range(n):
    List[i]=(1+List[i])/2
for i in range(1,n):
    List[i]+=List[i-1]
ans=0.0
for i in range(0,n-k+1):
    #ans=max(ans,List[i+k-1]-List[max(0,i-1)])
    if i==0 :
        ans=max(ans,List[i+k-1])
    else :
        ans=max(ans,List[i+k-1]-List[i-1])
print("{:.12f}".format(ans))


Verdicts: Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
import sys

input = sys.stdin.readline
n, k = map(int, input().split())

p = list(map(lambda x: (x + 1) / 2, map(int, input().split())))

# 1 - pi
ans = k
init = p[0]
for i in range(k, len(p)):
    print(i)
    if init < p[i]:
        init = p[i]
        ans = i

exp = 0
for i in range(ans - k + 1, ans + 1):
    exp += p[i]
print('{:.12f}'.format(exp))


import sys
import numpy as np

input = sys.stdin.readline
n, k = map(int, input().split())

p = list(map(lambda x: (x + 1) / 2, map(int, input().split())))
# 1 - pi
# print(p)
p_cumsum = np.cumsum(p)
# print(p_cumsum)
ans = p_cumsum[k-1]

for i in range(0, n - k):
    
    cum = p_cumsum[i + k] - p_cumsum[i]
    ans = max(ans, cum)


print('{:.12f}'.format(ans))

Verdicts: Runtime Error

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
N, K = map(int, input().split())
p = list(map(int, input().split()))
p_sum = [0]
max = 0

for i in range(len(p)):
    p_sum.append(p_sum[i] + (p[i]+1)/2) 
print(p_sum)

for i in range(K,N+1):
    sum = p_sum[i] - p_sum[i-K]
    print(sum)
    if(max < sum):
        max = sum
print('{:.12f}'.format(max))


N, K = map(int, input().split())
p = list(map(int, input().split()))
p_sum = [0]
max = 0

for i in range(len(p)):
    p_sum.append(p_sum[i] + (p[i]+1)/2) 

for i in range(K,N+1):
    sum = p_sum[i] - p_sum[i-K]
    if(max < sum):
        max = sum

#     tmp = p[i]
#     # print("i:" + str(i))
#     for j in range(i+1,i+K):
#         tmp += p[j]

#     # print(tmp)
#     if(max < tmp):
#         max = tmp 
#         maxStartIndex = i
# ans = 0


#     ans += sum/p[i]
print('{:.12f}'.format(max))
# 1 2 3 
# 3 2 1


# n, n-1, n-2
# n(n + 1)/2 

Verdicts: Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    lis.append(cumSum2[K+i] - cumSum2[i])

print(int(max(lis)))

import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    print(i)
    lis.append(cumSum2[K+i] - cumSum2[i])

print('{:.08f}'.format(max(lis)))

import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    lis.append(cumSum2[K+i] - cumSum2[i])

print('{:.18f}'.format(int(max(lis))))

import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    print(i)
    lis.append(cumSum2[K+i] - cumSum2[i])

print(max(lis))

import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    lis.append(cumSum2[K+i] - cumSum2[i])

print('{:.08f}'.format(int(max(lis))))

import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]
numpy.set_printoptions(precision=16)

cumSum = numpy.cumsum(p)

print(p)
cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    lis.append(cumSum2[K+i] - cumSum2[i])

print('{:.12f}'.format(max(lis)))

import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]
numpy.set_printoptions(precision=16)

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    lis.append(cumSum2[K+i] - cumSum2[i])

print('{:.12f}'.format(max(lis)))

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
n,k=map(int,input().split())
p=list(map(int,input().split()))
l=sum([p[i] for i in range(k)])
ans=0
for i in range(n-k):
  l-=p[i]
  l+=p[i+k]
  ans=max(l,ans)
print('{:.7f}'.format((ans+k)/2))

n,k=map(int,input().split())
p=list(map(int,input().split()))
l=sum([p[i] for i in range(k)])
if n==k:
  ans=l
else:
  ans=0
for i in range(n-k):
  l-=p[i]
  l+=p[i+k]
  ans=max(l,ans)
print('{:.12f}'.format((ans+k)/2))

Verdicts: Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
N,K = map(int,input().split())
p = list(map(int,input().split()))

expectation=[]
E = []


for t in p:
    value = 0
    for x in range(t+1):
        value += x/t
    E.append(value)
print(E)

for t in range(N-(K-1)):
    value = 0
    for i in range(K):
        value += E[t+i]
    expectation.append(value)

output = sorted(expectation,reverse=True)
print(format(output[0],'.12f')) 


N,K = map(int,input().split())
p = list(map(int,input().split()))

E = []
value=0

for P_i in p:
    value += (1+P_i)/2
    E.append(value)

flag = E[K-1]

for k in range(K,N):
    S = E[k] - E[k-K]
    if flag < S:
        flag = S
print(format(flag,'.12f'))

Verdicts: Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
N, K = map(int, input().split())
p = list(map(int, input().split()))

exv = list()

for a in p:
    exv.append((1+a)/2)



N, K = map(int, input().split())
p = list(map(int, input().split()))

from collections import deque

exv = list()

for a in p:
    exv.append((1+a)/2)

sm = 0
mx = 0

q = deque()

for a in range(N):
    sm += exv[a]
    q.appendleft(exv[a])
    if len(q) > K:
        sm -= q.pop()
    if len(q) == K:
        mx = max(mx,sm)

print('{:.12f}'.format(mx))

Verdicts: Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
N,K = map(int,input().split())

def exp(n):
    if n % 2 == 0:
        s = (n+1)*n/2
    else:
        s = (n+1)*(n-1)/2+(n+1)/2
    ans = s / n
    return ans

p = list(map(int,input().split()))

M = 0
for i in range(N-K+1):
    S = float(0)
    for j in range(K):
        S += exp(p[i+j]) 
    print(S)       
    if M < S:
        M = S

print('{:.12f}'.format(M))

N,K = map(int,input().split())
p = list(map(int,input().split()))

def exp(n):
    if n % 2 == 0:
        s = (n+1)*n/2
    else:
        s = (n+1)*(n-1)/2+(n+1)/2
    ans = s / n
    return ans

q = []
for i in range(N):
    q.append(exp(p[i]))
#print(q)

S = sum([q[i] for i in range(K)])
M = S
#print(M)

for i in range(N-K):
    S = S - q[i] + q[K+i]
    #print(S)
    if S > M:
        M = S

print('{:.12f}'.format(M))

Verdicts: Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):
query=[int(x) for x in input().split()]
N = query[0]
K = query[1]
L = list()
L = [int(x) for x in input().split()]



def prob(x):
    out = 0.0
    for i in range(1, x + 1):
        out = out + (1 / x) * i

    return out


final = 0.0
answer=list()
for i in range(0, N):
    final=0.0
    for j in range(i, K+i):
        if K+i<N:
            div = L[j]
            final = final + prob(div)
    answer.append(final)

print("%14.12f"%max(answer))

query=[int(x) for x in input().split()]
N = query[0]
K = query[1]
L = list()
L = [int(x) for x in input().split()]



def prob(x):
    out = 0.0

    out = (1 / x) * (x*(x+1))/2

    return out


final = 0.0
answer=list()
for i in range(0, N):
    final=0.0
    for j in range(i, K+i):
        if K+i<=N:
            div = L[j]
            final = final + prob(div)
    answer.append(final)
print(answer)
print("%14.12f"%max(answer))

query=[int(x) for x in input().split()]
N = query[0]
K = query[1]
L = list()
L = [int(x) for x in input().split()]



def prob(x):
    out = 0.0

    out = (x+1)/2

    return out


# final = 0.0
# answer=list()

#     final=0.0
#     for j in range(i, K+i):
#         if K+i<=N:
#             div = L[j]
#             final = final + prob(div)
#     answer.append(final)
#
# print("%14.12f"%max(answer))


res=0.0
tres=0.0
for i in range(0,K):
    tres+=prob(L[i])
    res=max(res,tres)
rindex=K
lindex=0
while rindex<N:
    tres=tres-prob(L[lindex])+prob(L[rindex])
    rindex+=1
    res=max(res,tres)
    lindex+=1
print("%14.12f"%res)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.  We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Submission attempts (in order):

n, k = map(int, input().split())
p = list(map(int, input().split()))

e = [(i+1)/2 for i in p]

sume = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        sume[i] = e[i]
    else:
        sume[i] = sume[i-1]+e[i]

ans = []
for i in range(n-k+1):
    if i == 0:
        ans.append(sume[i])
    else:
        ans.append(sume[i+k-1]-sume[i-1])   

print(max(ans))
    

n, k = map(int, input().split())
p = list(map(int, input().split()))

e = [(i+1)/2 for i in p]

sume = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        sume[i] = e[i]
    else:
        sume[i] = sume[i-1]+e[i]

ans = []
for i in range(n-k):
    ans.append(sume[i+k]-sume[i])    
    
print(max(ans))
    


n, k = map(int, input().split())
p = list(map(int, input().split()))

e = [(i+1)/2 for i in p]

sume = [0 for _ in range(n)]
for i in range(n):
    if i == 0:
        sume[i] = e[i]
    else:
        sume[i] = sume[i-1]+e[i]

ans = []

if n == k:
    ans.append(sume[-1])
else:
    for i in range(n-k):
        ans.append(sume[i+k]-sume[i])

print("%.12f"%max(ans))
    

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 = 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])

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[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):
s = input()
K = int(input())
n =len(s)

dp = [[[0] * 2 for _ in range(4)] for _ in range(101)]

dp[0][0][0]=1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[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(d,k)
                print(i,j,k,dp[i][j][k])
                print(ni,nj,nk,dp[ni][nj][nk])
                [print(i) for i in dp]

ans=dp[n][K][0] + dp[n][K][1]
print(ans)
[print(i) for i in dp]

s=input()
n=len(s)

K=int(input())

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

for i in range(n):
    ni= int(s[i])

    for k in range(4):
            
            dp[i + 1][1][k + 1] += dp[i][1][k] * 9;  
            dp[i + 1][1][k] += dp[i][1][k];  

            
            
            
            if (ni > 0):
                dp[i + 1][1][k + 1] += dp[i][0][k] * (ni - 1)
                dp[i + 1][1][k] += dp[i][0][k]
                
            
            if (ni > 0) :
                dp[i + 1][0][k + 1] = dp[i][0][k]
            else:
                dp[i + 1][0][k] = dp[i][0][k]

ans=dp[n][0][K] + dp[n][1][K]
print(ans)

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

def comb(a, b):
    ans = 1
    for i in range(b):
        ans *= (a - i)
    for i in range(2, b + 1):
        ans //= i
    return ans

def solve_k1(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    ans += 9 * (len_N - 1)
    ans += int(N[0])
    return ans

def solve_k2(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    if len_N < 2:
        return 0
    ans = comb((len_N - 1), 2) * 9 ** 2 + (int(N[0]) - 1) * ((len_N - 1) * 9) + solve_k1(int(N[1:]))
    return ans

def solve_k3(N):
    ans = 0
    N = str(N)
    len_N = len(N)
    if len_N < 3:
        return 0
    ans = comb(len_N - 1, 3) * 9 ** 3 + (int(N[0]) - 1) * comb(len_N - 1, 2) * 9 ** 2 + solve_k2(int(N[1:]))
    return ans

N = int(input())
K = int(input())
ans = 0
if K == 1:
    ans = solve_k1(N)
elif K == 2:
    ans = solve_k2(N)
else:
    ans = solve_k3(N)
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 math

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

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

def count(num_str,k):
    digits = len(num_str)
    if digits == 0:
        return 0
    else:
        if k == 0:
            print(num_str,1)
            return 1
        if num_str[0] == '0':
            print(num_str,count(num_str[1:],k-1))
            return count(num_str[1:],k-1)
        else:
            if digits == 1 and k == 1:
                print(num_str,int(num_str))
                return int(num_str)
            elif digits == 1 and k > 1:
                print(num_str,0)
                return 0
            if digits >= k+1:
                count_0 = combinations_count(digits-1,k)*(9**k)
            else:
                count_0 = 0
            count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
            print(num_str,count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1))
        return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(n),k))

import math

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

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

def count(num_str,k):
    digits = len(num_str)
    if digits == 0:
        return 0
    else:
        if k == 0:
            # print(num_str,1)
            return 1
        if num_str[0] == '0':
            # print(num_str,count(num_str[1:],k-1))
            return count(num_str[1:],k)
        else:
            if digits == 1 and k == 1:
                # print(num_str,int(num_str))
                return int(num_str)
            elif digits == 1 and k > 1:
                # print(num_str,0)
                return 0
            if digits >= k+1:
                count_0 = combinations_count(digits-1,k)*(9**k)
            else:
                count_0 = 0
            count_1 = combinations_count(digits-1,k-1)*(9**(k-1))
            # print(num_str,count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1))
        return count_0 + count_1*(int(num_str[0])-1)+count(num_str[1:],k-1)

print(count(str(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):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    nstr = str(N)

    nl = len(str(N))

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

    for i in range(nl):
        max_digit = int(nstr[i])
        for smaller in range(2):
            for j in range(nl):
                range_digit = 9
                
                if not smaller:
                    range_digit = max_digit
                for x in range(range_digit + 1):
                    if x != 0:
                        if smaller == 1:
                            dp[i + 1][smaller][j + 1] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j + 1] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j + 1] += dp[i][smaller][j]
                    else:
                        if smaller == 1:
                            dp[i + 1][smaller][j] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j] += dp[i][smaller][j]

    ans = 0
    print(dp[nl][1][K])


if __name__ == '__main__':
    main()


import sys
from functools import lru_cache

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(n, k):
    if n < 10:
        if k == 1:
            return n
        elif k == 0:
            return 1
        else:
            return 0

    q, r = divmod(n, 10)

    return solve(q, k) + solve(q, k - 1) * r + solve(q - 1, k - 1) * (9 - r)


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

    print(solve(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):
n=input()
k=input()
sum=0
for i in range(1,k+1):
    a=list(str(i))
    if list.count(0)=k:
        sum+=1
print(sum)   

n=int(input())
k=int(input())
sum=0
for i in range(1,n+1):
    a=list(str(i))
    if a.count('0')==k:
        sum+=1

print(sum)

n=int(input())
k=int(input())
sum=0
for i in range(1,n+1):
    a=list(str(i))
    if a.count("0")==k:
        sum+=1

print(sum)

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 j in range(k+1):
        dp[i][1][j]+=dp[i-1][1][j] 
        if l!=0:
            dp[i][1][j]+=dp[i-1][0][j]  
        else:
            dp[i][0][j]+=dp[i-1][0][j]      
        if j-1>=0:
            dp[i][1][j]+=9*dp[i-1][1][j-1]
            if l!=0:
                dp[i][0][j]+=dp[i-1][0][j-1]
                dp[i][1][j]+=(l-1)*dp[i-1][0][j-1]
print(dp[m][0][k]+dp[m][1][k])

Verdicts: 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):
S = input()
N = len(S)
K = int(input())

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 rec(i, k, isSmaller):
    if i == N:
        if k == 0:
            return 1
        else:
            return 0
    
    if k == 0:
        return 1
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (S[i] - '1')
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))

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

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    if r == 1:
        return n
    elif r == 2:
        return n * (n-1) // 2
    else:
        return n * (n-1) * (n-2) // (3 * 2) 

def rec(i, k, isSmaller):
    if k == 0:
        return 1

    if i == N:
        return 0
    
    if isSmaller:
        return cmb(N-i, k) * pow(9, k)
    else:
        if S[i] == '0':
            return rec(i+1, k, False)
        else:
            zero = rec(i+1, k, True)
            between = rec(i+1, k-1, True) * (int(S[i]) - 1)
            same = rec(i+1, k-1, False)
            return zero + between + same

print(rec(0, K, False))


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

if len(n) <= k:
    cnt = 0
    for i in range(1,int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            cnt += 1
    print(cnt)
    exit()

cnt = 0
l = len(n)
def combi(n,k):
    ans = 1
    if k == 0:
        return ans
    for i in range(k):
        ans = ans * (n-i) // (i+1)
    return ans
flag = 0
for i in range(l):
    if flag > k:
        break
    if n[i] == '0':
        if i == l-1:
            cnt += 1
        continue
    flag += 1
    cnt += int(((int(n[i])-1)*9**(k-flag))*combi(l-i-1,k-flag) + 9**(k-flag+1)*combi(l-i-1,k-flag+1))
    print(cnt)

print(cnt)

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

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):
from collections import deque
n = input()
k = int(input())
a = [int(n[i]) for i in range(min(k, len(n)))]
n = len(n)

if k > n:
    ans = 0
elif k == 1:
    
    ans += a[0]
    
    ans += (n - 1)*9
elif k == 2:
    
    ans += a[1] + (n - 2)*9
    
    ans += (a[0] - 1)*(n - 1)*9
    
    ans += (n - 1)*(n - 2)*9*9//2
else:
    
    ans += a[2] + (n - 3)*9 + (n - 2)*(n - 3)*9*9//2
    if a[1] != 0:
        ans += (a[1] - 1)*(n - 2)*9
    
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
print(ans)

from collections import deque
n = input()
a = [int(i) for i in list(n)]
k = int(input())
n = len(n)
ans = 0

if k > n:
    ans = 0
elif k == 1:
    
    ans += a[0]
    
    ans += (n - 1)*9
elif k == 2:
    
    for i in range(1, n):
        if a[i] != 0:
            j = i
            break
    else:
        j = n - 1
    ans += a[j] + (n - j - 1)*9
    
    ans += (a[0] - 1)*(n - 1)*9
    
    ans += (n - 1)*(n - 2)*9*9//2
else:
    
    j, l= -1, n - 1
    for i in range(1, n):
        if a[i] != 0:
            if j == -1:
                j = i
            else:
                l = i
                break
    if j != -1 and j != n - 1:
        ans += a[l] + (n - l - 1)*9 + (a[j] - 1)*(n - j - 1)*9 + (n - j - 1)*(n - j - 2)*9*9//2
    
    ans += (a[0] - 1)*(n - 1)*(n - 2)*9*9//2
    
    ans += (n - 1)*(n - 2)*(n - 3)*9*9*9//6
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):
N=int(input())
K=int(input())

d=len(str(N)) 
a=int(str(N)[0]) 
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d=1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 
    m=(a-1)*9*(d-1) 
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

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

dpsm=[[0]*(K+1) for _ in range(len(N))] #dpsm[i][k]
dp=[[0]*(K+1) for _ in range(len(N))]

dpsm[0][0]=1
dpsm[0][1]=int(N[0])-1
dp[0][1]=1

for i in range(1,len(N)):
    for k in range(K-1,-1,-1):
        dpsm[i][k+1]+=dpsm[i-1][k]*9

    
    if N[i]=="0":
        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dp[i][k]+=dp[i-1][k]
    else:
        for k in range(K-1,-1,-1):
            dpsm[i][k+1]+=dp[i-1][k]*(int(N[i])-1)
            dp[i][k+1]+=dp[i-1][k]

        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dpsm[i][k]+=dp[i-1][k]
          
print(dp[-1][-1]+dpsm[-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):
from math import factorial as fac

def comb(n,r):
    if ( r<0 or r>n ):
        return 0
    return fac(n)/(fac(r)*fac(n-r))


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

nn=str(n)
keta=len(nn)

ans=0

if keta<k:
    print(0)
    exit()

zero=0

for i in range(keta):
    if int(nn[i])==0:zero+=1
    ans+=comb(keta-i-1,k-i+zero)*9**(k-i)
    if int(nn[i])-1>=0:
        ans+=(int(nn[i])-1)*comb(keta-i-1,k-i-1+zero)*9**(k-i-1+zero)

if keta-zero==k:ans+=1

print(int(ans))


from math import factorial as fac

def comb(n,r):
    if ( r<0 or r>n ):
        return 0
    return fac(n)/(fac(r)*fac(n-r))


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

nn=str(n)
keta=len(nn)

ans=0

if keta<k:
    print(0)
    exit()

zero=0



#     ans+=comb(keta-i-1,k-i+zero)*9**(k-i)
#     if int(nn[i])-1>=0:

#


def search(n,k):
    if k<=0:return
    global ans
    nn = str(n)
    keta = len(nn)
    ans += comb(keta - 1, k ) * 9 ** k
    if int(nn[0])-1>0:
        ans+=(int(nn[0])-1)*comb(keta-1,k-1)*9**(k-1)
    ne=n-int(nn[0])*10**(keta-1)
    search(ne,k-1)


search(n,k)
for i in range(keta):
    if nn[i]=="0":zero+=1
if keta-zero>=k:ans+=1
print(int(ans))

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())

n=str(N)
n_digi=len(n)

import math

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


if n_digi < K:
    print(0)

else:
    ans=0
    
    if n_digi>K:
        ans += permutations_count(n_digi-1,K)*9
    
    keta1=int(n[0])
    nokori=n[1:]
    
    if keta1 != 1 and K!=1:
        ans += (keta1-1)*ermutations_count(n_digi-2,K-1)*9
        
    elif keta1 != 1 and K==1:
        ans += (keta1-1)
        
    elif K==1 and int(nokori)==0:
        ans += 1
        
    else:
        noko_list = list(nokori)
        aa=1
        bb=sum(noko_list)
        for j in noko_list:
            aa *=j
             
        ans += aa-bb*(K-1)
        
            
        




from functools import lru_cache

N, K = map(int,input().split())
 
@lru_cache(None)
def F(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 += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    
    ret += F(q, K)
    return ret

 
print(F(N, K))


from functools import lru_cache

N=int(input())
K=int(input())
 
@lru_cache(None)
def F(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 += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    
    ret += F(q, K)
    return ret
 
# F(100, 1), F(25, 2), F(314159, 2)
 
print(F(N, 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):
n = list(map(int,list(input())))
k = int(input())
l = len(n)
count = 0 
lst = [[0]*(k+1) for _ in range(l+1)] 
for i in range(l):
    if count < k:
        lst[i+1][count] += 1
        lst[i+1][count+1] += n[i]-1
    if count == k:
        lst[i+1][count] += 1
    for j in range(k):
        lst[i+1][j] += lst[i][j]
        lst[i+1][j+1] += 9*lst[i][j]
    lst[i+1][k] += lst[i][k]
    if n[i] != 0:
        count += 1
if count == k:
    print(lst[l][k]+1)
else:
    print(lst[l][k])

n = list(map(int,list(input())))
k = int(input())
l = len(n)
count = 0 
lst = [[0]*(k+1) for _ in range(l+1)] 
for i in range(l):
    if count < k:
        if n[i] != 0:
            lst[i+1][count] += 1
            lst[i+1][count+1] += n[i]-1
    if count == k:
        if n[i] != 0:
            lst[i+1][count] += 1
    for j in range(k):
        lst[i+1][j] += lst[i][j]
        lst[i+1][j+1] += 9*lst[i][j]
    lst[i+1][k] += lst[i][k]
    if n[i] != 0:
        count += 1
if count == k:
    print(lst[l][k]+1)
else:
    print(lst[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,K=map(int,input().split())
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(N,K))

N,K=int(input()),int(input())
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(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):
n=input()
if n[0]=="0"ans=1/0
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n+1):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

n=input()
l=len(n)
k=int(input())
if l<6:
  n=int(n)
  ans=0
  for i in range(1,n):
    if len(str(i))-str(i).count("0")==k:ans+=1
  print(ans)
  exit()
if k==1:
  ans=((l-1)*9)+int(n[0])
  print(ans)
  exit()
if k==2:
  ans=((l-1)*(l-2)//2)*81
  ans+=(int(n[0])-1)*((l-1)*9)
  ans+=int(n[1])
  ans+=(l-2)*9
  print(ans)
if k==3:
  ans=int(n[2])+(l-3)*9
  ans+=(int(n[1])-1)*((l-2)*9)
  ans+=((l-2)*(l-3)//2)*81
  ans+=(int(n[0])-1)*((l-1)*(l-2)//2)*81
  ans+=((l-1)*(l-2)*(l-3)//6)*9*9*9
  print(ans)

n=input()
l=len(n)
k=int(input())
def f(n,k):
  l=len(n)
  if l<k:return 0
  if n[0]=="0":return f(n[1:],k)
  if k==1:
    ans=((l-1)*9)+int(n[0])
  if k==2:
    ans=((l-1)*(l-2)//2)*81+(int(n[0])-1)*((l-1)*9)
    ans+=f(n[1:],k-1)
  if k==3:
    ans=(int(n[0])-1)*((l-1)*(l-2)//2)*81+((l-1)*(l-2)*(l-3)//6)*9*9*9
    ans+=f(n[1:],k-1)
  return ans
print(f(n,k))

Verdicts: Runtime Error

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())

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)

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')
else:

    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)

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 math

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

digit_num = math.floor(math.log10(n)) + 1
count = [0 for _ in range(n)]

for i in range(digit_num-1):
    j = i + 1
    if j > k:
        temp = ((j*j + 3*j + 2) * 9^(j-2))  /2
        count[i] = temp

b = 0

for i in range(digit_num,k,-1):
    s = int(str(n)[i])
    if s > 1:
        temp = (s-1) * count[i+1]
        b = b + temp

ans = sum(count)+b

print(b)


from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = input()
    p = int(input())
    l = len(n)

    n_0 = int(str(n)[0])

    dp = [[[0] * 2 for _ in range(p + 2)] for __ in range(l)]
    dp[0][0][0] = 0
    dp[0][0][1] = 1
    dp[0][1][0] = 1
    dp[0][1][1] = (n_0 - 1)

    for i in range(l - 1):
        a = int(n[i + 1])
        if a != 0:
            for j in range(p + 1):
                dp[i + 1][j + 1][0] += dp[i][j][0]
                dp[i + 1][j + 1][1] += 9 * dp[i][j][1] + (a - 1) * dp[i][j][0]
                dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
        else:
            for j in range(p + 1):
                dp[i + 1][j + 1][1] += 9 * dp[i][j][1]
                dp[i + 1][j][0] += dp[i][j][0]
                dp[i + 1][j][1] += dp[i][j][1]

    print(dp[l - 1][p][0] + dp[l - 1][p][1])


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):
import math
n = int(input())
k = int(input())

b = len(str(n)) 


if b > k:
    a = math.factorial(b - 1) // math.factorial(k) // math.factorial(b - 1 - k)
    ans = a * pow(9, k)
else: 
    ans = 0

if k == 1:
    ans += int(str(n)[0])
elif k == 2:
    c = int(str(n)[0])
    for i in range(1, b): 
        for j in range(1, c + 1): 
            if j < c or i > 1:
                ans += 9
            else:
                #print(i, j, int(str(n)[i]))
                ans += int(str(n)[i])
else:
    c = [int(str(n)[i]) for i in range(b)] 分離
    d = 1 
    for i in range(1, b):
        if c[i] == 0:
            d += 1
        else:
            break
    if d < b: 
        ans += (c[0] - 1) * 81 * math.factorial(b - 1) // math.factorial(2) // math.factorial(b - 3) 
        if b - d > 2:
            ans += 81 * math.factorial(b - d - 1) // math.factorial(2) // math.factorial(b - d - 3) 
        ans += (c[d] - 1) * 9 * (b - d - 1) 
        #print(ans)
        
        for i in range(d + 1, b): 
            for j in range(1, 10): 
                e = ['0' for _ in range(b)]
                e[0] = c[0]
                e[d] = c[d]
                e[i] = j
                f = ''
                for k in range(b):
                    f += str(e[k])
                f = int(f)
                if f <= n:
                    ans += 1






print(ans)

n = int(input())
k = int(input())
l = len(str(n))
a = [int(str(n)[i]) for i in range(l)]

dp = [[[0, 0] for _ in range(k + 1)] for _ in range(l)] 

dp[0][0][0] = 1         
dp[0][0][1] = 0         
dp[0][1][0] = a[0] - 1  
dp[0][1][1] = 1         

#print(a)

for i in range(1, l):
    for j in range(k + 1):
        if j > 0 and a[i] != 0:
            
            
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9 \
                        + dp[i-1][j][1] * 1 \
                        + dp[i-1][j-1][1] * (a[i] - 1)
            
            dp[i][j][1] = dp[i-1][j-1][1] * 1

        elif j > 0 and a[i] == 0:
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j-1][0] * 9
            
            dp[i][j][1] = dp[i-1][j][1] * 1
        
        elif j == 0 and a[i] != 0:
            
            
            dp[i][j][0] = dp[i-1][j][0] * 1 \
                        + dp[i-1][j][1] * 1
            
            dp[i][j][1] = 0
        elif j == 0 and a[i] == 0:
            
            dp[i][j][0] = dp[i-1][j][0] * 1
            
            dp[i][j][1] = dp[i-1][j][1] * 1
            

#print(dp)
print(dp[l-1][k][0] + dp[l-1][k][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):
import math
N = len(str(input()))
K = int(input())
print((math.factorial(N) // (math.factorial(N-K) * math.factorial(K)))*(9**K))

import math
N = int(input())
l = len(str(N))
K = int(input())
def calc(a, b, c):
    t = 0
    if a-b-1>=0:
        t = (math.factorial(a-1) // (math.factorial(a-b-1) * math.factorial(b)))*(9**(b))
    if b==1:
        t2 = int(str(c)[0])
    else:
        t2 = (math.factorial(a-1) // (math.factorial(a-b) * math.factorial(b-1)))*(9**(b-1))*(int(str(c)[0])-1)
    t3 = 0
    try:
        n = int(str(c)[1:])
        if 2<=b<=len(str(n))+1:
            t3 = calc(len(str(n)), b-1, n)
    except:
        pass
    return t+t2+t3

if l>=K:
    print(calc(l, K, N))
else:
    print(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):
def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    z = N.count('0')
    o = N.count('1')
    f = 0
    if z + o == L:
      f = 1
    if f == 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(N[1:]),K - 1)
    else:
      if len(str(int(N[1:]))) != 1:
        return ans + top(str(int(N[1:])),K - 1)
      else:
        return ans

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

print(int(top(N,K)))

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    if int(N) % u * 10 ** (L-1) != 0 or u != 1:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(N[1:]),K - 1)
    else:
      return ans

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

print(int(top(N,K)))

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    if int(N) % u * 10 ** (L-1) != 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      return ans + top(str(N[1:]),K - 1)
    else:
      return ans

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

print(int(top(N,K)))

def nCr(n,r):
  ret = 1
  for i in range(r):
    ret *= n-i
    ret /= i+1
  return ret

def top(N,K):
  if K == 0:
    return 1
  L = len(N)
  ans = 0
  if L < K:
    return 0
  else:
    ans += nCr(L-1,K) * 9 ** K

    u = int(N[0])
    z = N.count('0')
    o = N.count('1')
    f = 0
    if z + o == L:
      f = 1
    if f == 0:
      ans += (u - 1) * nCr(L-1,K - 1) * 9 ** (K - 1)
      if L == 1:
        return ans + 1
      else:
        return ans + top(str(int(N[1:])),K - 1)
    else:
      if len(str(int(N[1:]))) != 1:
        return ans + top(str(int(N[1:])),K - 1)
      else:
        if o >= K:
          return ans + 1
        else:
          return ans

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

print(int(top(N,K)))

Verdicts: Wrong Answer

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):
    r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

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

digit = list(map(int, str(N)))
M = len(digit)

C = 0
if M >= K:
    for i in range(K):
        C += count(digit[i], M-i, K-i)

print(C)    


def factorial(a):
    r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

def COUNT(N,K):
    digit = list(map(int, str(N)))
    M = len(digit)
    C = count(digit[0], M, K)
    N_ = N % pow(10, M-1)
    return C, N_
    

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

C = 0
while (N>0) and (K>0):
    c, N = COUNT(N, K)
    C+= c
    K-= 1

print(C)    


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




dp0=[[0]*(k+1) for _ in range(keta)]
dp1=[[0]*(k+1) for _ in range(keta)]
dp0[0][0]=1
dp0[0][1]=int(n[0])-1
dp1[0][1]=1
for i in range(1,keta):
	if n[i]==0:
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j]
		dp0[i][0]=dp0[i-1][0]
		for j in range(k+1):
			dp0[i][j]=dp0[i-1][j-1]*9+dp0[i-1][j]
	else:
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(k+1):
			dp0[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(int(n[i])-1)+dp0[i-1][j-1]*9+dp0[i-1][j]
print(dp0[-1][-1]+dp1[-1][-1])





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




dp0=[[0]*(k+1) for _ in range(keta)]
dp1=[[0]*(k+1) for _ in range(keta)]
dp0[0][0]=1
dp0[0][1]=int(n[0])-1
dp1[0][1]=1
for i in range(1,keta):
	if n[i]=="0":
		for j in range(k+1):
			dp1[i][j]=dp1[i-1][j]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp0[i-1][j-1]*9+dp0[i-1][j]
	else:
		for j in range(1,k+1):
			dp1[i][j]=dp1[i-1][j-1]
		dp0[i][0]=dp0[i-1][0]
		for j in range(1,k+1):
			dp0[i][j]=dp1[i-1][j]+dp1[i-1][j-1]*(int(n[i])-1)+dp0[i-1][j-1]*9+dp0[i-1][j]
print(dp0[-1][k]+dp1[-1][k])





Verdicts: Wrong Answer

Accepted