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):
import sys 
N = list(input())
K = int(input())

L = len(N)
if K>L:
    print(0)
    sys.exit()
#%%
def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        L2 -= 1
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)* int((L2-1)>0)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    print(i,L2,K2,ans)
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == K:
    ans += 1
print(int(ans))

import sys 
N = list(input())
K = int(input())

L = len(N)
if K>L:
    print(0)
    sys.exit()
#%%
def cmb(l,k):
    if k<0 or l<0:
        return 0
    if k>L:
        return 0
    elif k==0 or l==0:
        return 1
    
    ret = l
    for i in range(k-1):
        ret *= (l-i-1)
    for i in range(k):
        ret //= (1+i)
    return ret


ans = 0
K2 = K
L2 = L
for i in range(L):
    if K2 < 0 or L2 < 0:
        break
    if N[i]=='0':
        L2 -= 1
        continue
    elif N[i]=='1':
        ans += 9**K2 * cmb(L2-1,K2)* int((L2-1)>0)
    else:
        ans += 9**K2 * cmb(L2-1,K2) * int((L2-1)>0)
        t = int(N[i])
        ans += (t-1)* 9**(K2-1) * cmb(L2-1,K2-1)
    K2 -= 1
    L2 -= 1

ttmp = 0
for a in N:
    if a!='0':
        ttmp+=1
if ttmp == 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 = str(input())
k = int(input())
dp = [[[0 for i in range(len(n))+1] for i in range(2)] for i in range(len(n))]
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if n[a] > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if n[a] > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if n[a] == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if n[a] == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
print(dp)           

n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
    if k == 1:
 		print(int(n))  
    if k >= 2:
      print(0)
else:
  print(dp[-1][0][k] + dp[-1][1][k])


n = input()
k = int(input())
dp = [[[0 for i in range(k+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(k+1):
      for i in range(10):
        if b ==1:
          if c ==k:  
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
          else:
            if i == 0:
              dp[a+1][1][c] += dp[a][1][c]
            else:
              dp[a+1][1][c+1] += dp[a][1][c]
        else:
          if int(n[a]) > i:
            if c == k:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][1][c] += dp[a][0][c]
              else:
                dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i:
            if c == k:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
            else:
              if i == 0:
                dp[a+1][0][c] += dp[a][0][c]
              else:
                dp[a+1][0][c+1] += dp[a][0][c]
            
            
print(dp[-1][0][-1] + dp[-1][1][-1])
        

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):
print(1)

print(2)

s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) 
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) = 0:
    print(tasumae)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

print(0)

s = input()
l = len(s)
K = int(input())
def com(x,y):
    child = 1
    mother = 1
    for i in range(y):
        child = child * (x-i)
        mother = mother * (i+1)
    if x == 1 and y >=2:
        return 0
    else:    
        return int(child / mother)
tasumae = (9**K)*com(l-1,K) 
li = list(s)
doko = []
if l < K:
    print(0)
    exit()
if K == 1:
    print(tasumae+int(li[0]))
    exit()
for i in range(1,l):
    if li[i] != "0":
        doko.append(i)
if K == 2:
    if not doko:
        print(tasumae)
        exit()
    ans = int(li[doko[0]]) + 9*(l-1-doko[0]) + tasumae + (int(li[0])-1)*com(l-1,1)*9
    print(ans)
    exit()
if len(doko) == 0:
    print(tasumae)
    exit()
if len(doko) == 1:
    ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + com(l-1-doko[0],2)*(9**2) + tasumae
    print(ans)
    exit()
ans = (int(li[0])-1)*com(l-1,2)*(9**2) + (int(li[doko[0]])-1) * 9 * (l-1-doko[0]) + int(li[doko[1]]) + 9*(l-1-doko[1]) + com(l-1-doko[0],2)*(9**2) + tasumae
print(ans)

Verdicts: Wrong Answer

Wrong Answer

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


# tmp = N

# while tmp >= 10:
#     tmp //= 10



if K > len(str(N)):
    print(0)
    exit()

if K == 1:  # done
    N = str(N)
    ans = (len(N)-1) * 9
    ans += int(N[0])
    print(ans)

elif K == 2:
    N = str(N)
    
    ans = (len(N)-1) * (len(N)-2) * 9 * 9 // 2
    
    ans += 1 * int(N[1])
    
    ans += (int(N[0])-1) * 9
    
    ans += int(N[0]) * (len(N)-2) * 9
    print(ans)
elif K == 3:
    N = str(N)
    
    ans = (((len(N)-1) * (len(N)-2) * (len(N)-3)) // 6) * (9**3)  # done
    
    
    ans += 1 * 1 * int(N[2])  
    ans += 1 * 1 * (len(N)-3)*9  , 3桁目は選ばない
    ans += 1 * (int(N[1])-1) * (len(N)-2) * 9  
    
    ans += (int(N[0])-1) * 9 * (len(N)-2)*9
    
    ans += int(N[0]) * (len(N)-2) * (len(N)-3) // 2 * (9**2)
    print(ans)


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

for i in range(len(N)):
    x = int(N[i])  
    for j in range(K):
        
        dp[i+1][j+1][0] += dp[i][j][0]*9  
        dp[i+1][j][0] += dp[i][j][0]  
        
        if x > 0:
            dp[i+1][j][0] += dp[i][j][1]  
            dp[i+1][j+1][0] += dp[i][j][1]*(x-1)  
            dp[i+1][j+1][1] += dp[i][j][1]  
        else:
            
            dp[i+1][j][1] += dp[i][j][1]  
    dp[i+1][K][0] += dp[i][K][0]
    dp[i+1][K][not x>0] += dp[i][K][1]
print(sum(dp[len(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 math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    ret = 0
    for c in n:
        if c != '0':
            ret += 1
    return ret

ans = 0
# if len(n) == k and cnt(n) == k:
#     ans +=1

for i in range(min(len(n), k)):
    if int(n[i]) == 0:
        continue
    if len(n)-i > k:
        print(calc(i, k))
        ans += calc(i, k)
    k -= 1
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)
    if k == 0:
        ans += 1
print(ans)


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

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    ret = 0
    for c in n:
        if c != '0':
            ret += 1
    return ret

ans = 0
if len(n) == k and cnt(n) == k:
    ans +=1

for i in range(len(n)):
    if len(n)-i > k:
        ans += calc(i, k)
    if int(n[i]) == 0:
        continue
    k -= 1
    if k < 0:
        break
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)

print(ans)


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

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

def cnt(n):
    cnt = 0
    for c in n:
        if c != "0":
            cnt += 1
    return cnt

ans = 0
if cnt(n) == k:
    ans += 1


for i in range(len(n)):
    if int(n[i]) == 0:
        continue
    if len(n)-i > k:
        ans += calc(i, k)
    k -= 1
    if k < 0:
        break
    if len(n)-i > k:
        ans += (int(n[i]) - 1) * calc(i, k)
print(ans)


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

from scipy.misc import comb
from math import factorial

n_d = len(str(n))
digits = str(n)

def get_num(top, k_val, d_num):
  #print(top, k_val, d_num)
  if d_num>n_d:
    return 1
  elif k_val==0:
    return 1
  elif top:
    below1 = get_num(True, k_val-1, d_num+1)
    below2 = (int(digits[d_num])-1) * get_num(False, k_val-1, d_num+1)
    below3 = get_num(False, k_val, d_num+1)
    return below1 + below2 + below3
  else:
    return factorial(n_d-d_num) / factorial(k_val) / factorial(n_d - d_num - k_val) * 9**(k_val)
    #return comb(n_d-d_num, k_val) * 9**(k_val)



if k<n_d :
  #a = comb(n_d-1, k)
  a = factorial(n_d-1) / factorial(k) / factorial(n_d-1 - k)
else:
  a = 0
a *= 9**k

c1 = get_num(True, k-1, 1)
c2 = (int(digits[0]) - 1) * get_num(False, k-1, 1)

#print(a, c1, c2)
print(int(a+c1+c2))

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

from math import factorial

str_n = str(N)
len_n = len(str(str_n))

def conb(n, r):
    return factorial(n)//factorial(r)//factorial(n-r)
    
def get_num(top, k_val, depth):
    if k_val==0:
        return 1
    elif k_val>(len_n-depth+1):
        return 0
    elif top:
        if int(str_n[depth - 1])==0:
            return get_num(top, k_val, depth + 1)
        else:
            b1 = get_num(top, k_val - 1, depth + 1)
            b2 = (int(str_n[depth-1])-1) * get_num(False, k_val-1, depth+1)
            b3 = get_num(False, k_val, depth + 1)
            return b1+b2+b3
    else:
        return 9**(k_val) * conb(len_n - depth + 1, k_val)
    
    
a1 = get_num(True, K-1, 2)
a2 = (int(str_n[0])-1)*get_num(False, K-1, 2)
a3 = get_num(False, K, 2)

#print(a1, a2, a3)
print(a1+a2+a3)

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
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))
ans = 0
l = len(S)

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

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

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

if ans != 0:
    ans += 1

print(ans)

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

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

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

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

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

print(ans)

from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))

def C(n,r): 
    return factorial(n) // (factorial(n - r) * factorial(r))

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

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


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

def D(i,j): 
    if i >= j:
        return (9**j) * (factorial(i) // (factorial(i - j) * factorial(j)))
    else:
        return 0

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

for i in range(digit):
    digit -= 1
    if int(S[i]) == 0:
        if K == len(S):
            print(0)
            exit()
        continue
    ans += D(digit,k)
    k -= 1
    if k == 0:
        ans += S[i]
        break
    ans += (int(S[i]-1))*D(digit,k)
print(ans)


Verdicts: Wrong Answer

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

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

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

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



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

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

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


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
read = sys.stdin.read
n, k = map(int, read().split())


def count(digit, k):
    elif k == 0:
        return 1
    elif k == 1:
        return digit
    elif k == 2:
        return digit * (digit - 1) // 2
    else:
        return digit * (digit - 1) * (digit - 2) // 6


def solve(n, k):
    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
    res += solve(mod, k - 1)
    return res


print(solve(n, k))


import sys
read = sys.stdin.read
n, k = map(int, read().split())


def count(digit, k):
    if k == 0:
        return 1
    elif k == 1:
        return digit
    elif k == 2:
        return digit * (digit - 1) // 2
    else:
        return digit * (digit - 1) * (digit - 2) // 6


def solve(n, k):
    if k == 0:
        return 1
    digit = len(str(n))
    res = 0
    if digit > k:
        res += count(digit - 1, k) * (9 ** k)
    pow10 = 10 ** (digit - 1)
    d, mod = n // pow10, n % pow10
    res += count(digit - 1, k - 1) * (9 ** (k - 1)) * (d - 1)
    res += solve(mod, k - 1)
    return res


print(solve(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()
K = int(input())

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
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int,read().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))

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=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r==1 or n==r==0:
    return 1
  else:
    return 1
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    print(ans)
    if not_zero==K:
      ans+=1
      break
print(ans)
  

import math
N=list(input())
K=int(input())
ans=0
not_zero=0
def cmb(n, r):
  if n-r>=1 and n>=1 and r>=1: 
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  elif n==r or n==r:
    return 1
  elif r==0:
    return 1
  else:
    return 0
for i in range(len(N)):
  if N[i]!="0":
    ans+=cmb(len(N[i+1:]),K-not_zero) * (9**(K-not_zero))
    ans+=cmb(len(N[i+1:]), K-not_zero-1) *(int(N[i])-1)* (9**(K-not_zero-1))
    not_zero+=1
    #print(ans)
    if not_zero==K:
      ans+=1
      break
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 functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

def g(m, k):
    if k == 0:
        return 1
    if k == 1:
        return m * 9
    if k == 2:
        return m * (m-1) // 2 * 81
    if k == 3:
        return m * (m-1) * (m-2) // 6 * 729

@lru_cache(maxsize=None)
def f(n, k):
    if n == 0: return 0
    if k == 0: return 1
    S = str(n)
    t = int(S[0])
    m = len(S)
    return f(int("0" + S[1:]), k-1) + ((t-1) * g(m-1, k-1) if t else 0) + g(m-1, k)

N = int(input())
K = int(input())
print(f(N, K))

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

def g(m, k):
    if k == 0:
        return 1
    if k == 1:
        return m * 9
    if k == 2:
        return m * (m-1) // 2 * 81
    if k == 3:
        return m * (m-1) * (m-2) // 6 * 729

@lru_cache(maxsize=None)
def f(n, k):
    if n == 0 and k:
        return 0
    if k == 0:
        return 1
    S = str(n)
    t = int(S[0])
    m = len(S)
    return f(int("0" + S[1:]), k-1) + ((t-1) * g(m-1, k-1) if t else 0) + g(m-1, k)

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

S = str(N)
keta = len(S)


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


i = int(S[0])
dp[0][0][0] = 1

for n in  range(0,keta):
    
    for k in range(0, K + 1):
        num = int(S[n])  
        num_to_9  = 9 - num  
        num_hiku1_to_1 = max(0,num - 1) 
        
        

        dp[1][k+ 1 ][n + 1] += dp[1][k][n] * 9
        
        dp[1][k][n + 1] += dp[1][k][n] * 1  
        
        
        
        dp[1][k + 1][n + 1] += dp[0][k][n] * num_hiku1_to_1 
        dp[1][k][n + 1] += dp[0][k][n] * 1 

        
        if num == 0: 
            dp[0][k][n + 1] += dp[0][k][n]
        else: 
            dp[0][k + 1][n + 1] += dp[0][k][n]

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




import math
N = int(input())
K = int(input())

S = str(N)
keta = len(S)


dp1 = [ [ 0 ]* (keta + 1)  for _ in range(100) ] 
dp2 = [  [ 0 ]* (keta + 1)  for _ in range(100) ] 


i = int(S[0])
dp2[0][0] = 1 

for n in  range(0,keta):
    
    for k in range(0, K + 1):
        num = int(S[n])  
        num_to_9  = 9 - num  
        num_hiku1_to_1 = max(0,num - 1) 
        
        

        if num == 0:
            dp1[k + 1][n + 1] += dp1[k][n] * 9 # 1~ 9
            dp1[k][n + 1] += dp1[k][n] 
            # dp1[k][n + 1] += dp2[k][n]
            dp2[k][n + 1] += dp2[k][n] 

        else:
            dp1[k + 1][n + 1] += dp1[k][n] * 9 
            dp1[k + 1][n + 1] += dp2[k][n] * (num - 1)  
            dp2[k + 1][n + 1] += dp2[k][n] 

            
            dp1[k][n + 1] += dp1[k][n] 
            

            dp1[k][n + 1] += dp2[k][n] 
            
        


print(dp1[K][keta] + dp2[K][keta])




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):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
k = ii()
n2 = n

n_keta = 1
while n2:
    n2 = n2 //10
    if n2 == 0:
        break
    n_keta += 1

from math import factorial as fc
def func(keta,kazu,ima):
    ans = 0
    n = n_keta - keta -1
    r =  k - kazu
    if n-r <0:
        return 0
    ans += (ima-1) *fc(n) //fc (r)//fc(n-r)  * (9 **(k-kazu))
    print(ans)
    if n - r -1 >= 0: ans += fc(n) // fc (r+1) // fc(n-r-1) *(9**(k-kazu +1))
    print(ans)
    return ans
n_in = str(n)
kk = 0
lis = []

for i in range(n_keta):
    if n_in[i] != 0:
        lis.append([i,kk+1,int(n_in[i])]) 
        kk += 1
    if kk ==k:
        break
anss = 0
for lil in lis:
    anss += func(lil[0],lil[1],lil[2])
print(int(anss+1))


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

s = input()
k = ii()


n = len(s)
dp = [[0]*(n) for _ in range(4)]
dp[0][0] = 1
for i in range(1,n):
    
    dp[0][i] = dp[0][i-1] 
    
    dp[1][i] = dp[0][i-1] * 9 + dp[1][i-1]
    
    dp[2][i] = dp[1][i-1]*9 + dp[2][i-1]
    dp[3][i] = dp[2][i-1]*9 + dp[3][i-1]

ans = 0
for i in range(n):
    ima = int(s[i])
    if i ==-1 :
        ans += (ima -1) * dp[k-1][n-1-i]
        k -= 1
    else:
        if ima != 0:
            ans += (ima -1) * dp[k-1][n-1-i] + dp[k][n-1-i]
            k -= 1
    if k == 0:
        ans += 1
        break
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):
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (K+1) for _ in range(2)] for _ in range(n)
]


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

for i in range(1, n):
  for k in range(K):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (K+2) for _ in range(2)] for _ in range(n)
]


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

for i in range(1, n):
  for k in range(K+1):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][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())
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][1][K])

n=input()
K=int(input())
m=len(n)

DP=[[[0]*(K+2) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(K+1):
            for k in range(num+1):
                if k==0:DP[i][flag or k<num][j] +=DP[i-1][flag][j]
                else:DP[i][flag or k<num][j] +=DP[i-1][flag][j-1]

print(DP[m][0][K]+DP[m][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())
import math
ans=0
n=str(N)
a=len(n)
print(a)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
        print(ans)
    if K==1:
        ans+=int(n[0])
    elif K==2:ans+=int(n[0])*(a-2)*9+(int(n[0])-1)*9+int(n[1])
    else:ans+=(int(n[0])-1)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*(int(n[1])-1)+int(n[2])+(a-3)*9

print(ans)

N=9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
K=3
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if int(n[i])==0:
        return 0
    else:
        return int(n[i])-1


if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:ans+=mi(0)*(a-1)*9+(a-2)*9+int(n[1])
    elif a==3 : ans+=mi(0)*81*(combi(a-1,2))+9*mi(1)+int(n[2])
    else:ans+=mi(0)*81*(combi(a-1,2))+combi(a-2,2)*81+9*(a-2)*mi(1)+int(n[2])+(a-3)*9

print(ans)

N=int(input())
K=int(input())
import math
ans=0
n=str(N)
a=len(n)
def combi(p,q):
    if p<q : return 0
    else: return math.factorial(p)//(math.factorial(q)*math.factorial(p-q))
def mi(i):
    if i==0:
        return 0
    else:
        return i-1
def zero(i):
    if int(n[i])==0:
        return 0
    else:
        return 1
if a<K:
    ans=0
else:
    if a>K:
        ans+=combi(a-1,K)*(9**K)
    if K==1:ans+=int(n[0])
    elif K==2:
        x=0
        i=1
        b=0
        bs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            if (x==1) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*(a-1)*9+mi(bs)*9+b
    elif a==3 : ans+=mi(int(n[0]))*81*(combi(a-1,2))+9*mi(int(n[1]))+int(n[2])
    else:
        x=0
        i=1
        b=0
        bs=0
        c=0
        cs=0
        while True:
            if (int(n[i])!=0) and (x==0):
                b=int(n[i])
                bs=a-i
                x+=1
            elif (int(n[i])!=0) and (x==1):
                c=int(n[i])
                cs=a-i
                x+=1
            if (x==2) or (i==len(n)-1):
                break
            i+=1
        ans+=mi(int(n[0]))*81*(combi(a-1,2))+combi(bs-1,2)*81+9*(a-2)*mi(b)+c+mi(cs)*9

print(ans)


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):
from math import factorial

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

n=int(input())
k=int(input())
ans=0
nstr=str(n)
nl=len(nstr)
for i in range(k,nl):
    ans+=combinations_count(i-1,k-1)
ans*=9**k
zerocnt=0
for i in range(nl):
    if zerocnt<=nl-k:
        if i==0:
            ans+=(int(nstr[0])-1)*combinations_count(nl-1,k-1)*(9**(k-1))
        else:
            if nstr[i]=='0':
                zerocnt+=1
            else:
                ans+=(int(nstr[i])-1)*combinations_count(nl-i-1,k-i+zerocnt-1)*9**(k-i+zerocnt-1)
    else:
        break
print(ans)

s=input()
K=int(input())
n=len(s)
dp=[[[0]*2 for _ in range(K+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(n):
    for j in range(K+1):
        for k in range(2):
            nd=int(s[i])
            for d in range(10):
                ni,nj,nk=i+1,j,k
                if d!=0:
                    nj+=1
                if nj>K:
                    continue
                if nk==0:
                    if nd<d:
                        continue
                    if nd>d:
                        nk=1
                dp[ni][nj][nk]+=dp[i][j][k]
print(dp[n][K][0]+dp[n][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):
n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  
print(cnt)

n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))]




dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 
        dp[i][0][1] = dp[i-1][0][0] 
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] 
        dp[i][1][1] = dp[i-1][0][0]*(int(n[i])-1)+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(int(n[i])-1)+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(int(n[i])-1)+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] 
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-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 n == 0:
    return 0
  if n == k:
    return 1
  
  num = 1
  for i in range(n-k+1,n+1):
    num *= i
    
  for i in range(2,k+1):
    num //= i
    

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  print('tmp:', n,k,ans)
  return ans


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

print(syou(n, k))

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

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  if n[0] == '0':
    return syou(n[1:l], k-1)
  
  l = len(n)
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  print('tmp:', n,k,ans)
  return ans


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

print(syou(n, k))

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

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  return ans


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

print(syou(n, 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):
def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + mondai(d, 1)
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = mondai(n, k)

def mondai(n, k):

    keta = 0
    a = n
    b = []
    ans = 0
    d = 0

    while a >= 10:
        c = a % 10
        b.append(c)
        a = a // 10
        keta = keta + 1
    
    for i in range(len(b)):
        d = d + b[i] * (10 ** i)

    if k == 1:
        ans = keta * 9 + a

    elif k == 2:
        if keta == 0:
            ans = 0
        elif keta == 1:
            ans = keta * 9 * (a - 1) + mondai(d, 1)
        else:
            for i in range(1, keta):
                ans = ans + i * 81
            ans = ans + keta * 9 * (a - 1) + mondai(d, 1)
        
    else:
        if keta == 0 or keta == 1:
            ans = 0
        elif keta == 2:
            ans = keta * 81 * (a - 1) + mondai(d, 2)
        
        else:
            for i in range(2, keta):
                ans = ans + i * (i - 1) / 2 * 9 * 9 * 9
            ans = ans + keta * (keta - 1) / 2 * 81 * (a - 1) + mondai(d, 2) 
            
                
    return ans

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

ans = int(mondai(n, 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):
N=input()
k=int(input())
ln=len(N)
DP=[[[0]*2 for _ in range(k+1)] for _ in range(len(N)+1)]
DP[0][0][0]=1
for i in range(1,len(N)+1):
  DP[i][0][1]=1
for i in range(len(N)):
  ni=int(N[i])
  for j in range(1,k+1):
    DP[i+1][j][1]=DP[i][j][1]+max(0,ni-1)*DP[i][j-1][0]+9*DP[i][j-1][1]+DP[i][j][0]
    if ni==0:
      DP[i+1][j][0]=DP[i][j][0]
    else:
      DP[i+1][j][0]=DP[i][j-1][0]
print(DP[ln][k][0]+DP[ln][k][1])



N=input()
k=int(input())
ln=len(N)
DP=[[[0]*2 for _ in range(k+1)] for _ in range(len(N)+1)]
DP[0][0][0]=1
for i in range(1,len(N)+1):
  DP[i][0][1]=1
for i in range(len(N)):
  ni=int(N[i])
  for j in range(1,k+1):
    DP[i+1][j][1]=DP[i][j][1]+max(0,ni-1)*DP[i][j-1][0]+9*DP[i][j-1][1]
    if ni==0:
      DP[i+1][j][0]=DP[i][j][0]
    else:
      DP[i+1][j][0]=DP[i][j-1][0]
      DP[i+1][j][1]+=DP[i][j][0]
print(DP[ln][k][0]+DP[ln][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):
n = input()
k = input()
nl = len(n)

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

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

for i in range(nl):
  for j in range(2):
    for l in range(k+1):
      c = int(n[i])
      if j == 1:
        dp[i+1][j][l] += dp[i][j][l]
        if l < k:
          dp[i+1][j][l+1] += dp[i][j][l]*9
      else:
        if c == 0:
          dp[i+1][0][l] += dp[i][j][l]
        else:
          dp[i+1][1][l] += dp[i][j][l]
          if l < k:
            dp[i+1][1][l+1] += dp[i][j][l]*(c-1) 
            dp[i+1][0][l+1] += dp[i][j][l] 
            
print(dp[nl][0][k]+dp[nl][1][k])
          



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

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

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

for i in range(nl):
  for j in range(2):
    for l in range(k+1):
      c = int(n[i])
      if j == 1:
        dp[i+1][j][l] += dp[i][j][l]
        if l < k:
          dp[i+1][j][l+1] += dp[i][j][l]*9
      else:
        if c == 0:
          dp[i+1][0][l] += dp[i][j][l]
        else:
          dp[i+1][1][l] += dp[i][j][l]
          if l < k:
            dp[i+1][1][l+1] += dp[i][j][l]*(c-1) 
            dp[i+1][0][l+1] += dp[i][j][l] 
            
print(dp[nl][0][k]+dp[nl][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 modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)

r1,c1,r2,c2=map(int,input().split())
n1=r2+c2+2
n2=r2+c1+1
n3=r1+c2+1
n4=r1+c1
l=[r2+1,r2+1,r1,r1]
p=10**9+7
buf=1
cnt=0
l=[0]*(10**6+10)
l2=[0]*20
inv=[0]*(10**6+10)
for i in range(2,n1+3,1):#n1+1
    l[i]=(l[i-1]*i)%p
print((((l[n1]*modinv(l[r2+1],p)*modinv(l[n1-r2-1],p))%p)-(l[n2]*modinv(l[r2+1],p)*modinv(l[n2-r2-1],p))-(l[n3]*modinv(l[r1],p)*modinv(l[n3-r1],p))+(l[n4]*modinv(l[r1],p)*modinv(l[n4-r1],p)))%p)


import numpy as np

N=input()
K=input()
dp=np.zeros((len(str(N))+10,len(str(N))+10,2))
dp=dp.tolist()


x0=int(N[0])
dp[0][0][0]=1


for i in range(0,len(N),1):
    for j in range(0,4,1):
        for k in range(0,2,1):
            nd=int(N[i])
            for d in range(0,10,1):
                ni=i+1
                nj=j
                nk=k
                if not(d==0):
                    nj=nj+1
                if ((k==0)and(d<nd)):
                    nk=1
                if (not(nj>int(K)))and(not((k==0)and(d>nd))):
                    dp[ni][nj][nk]=dp[ni][nj][nk]+dp[i][j][k]


print(int(dp[len(N)][int(K)][0]+dp[len(N)][int(K)][1]))


Verdicts: Runtime Error

Accepted
Problem: Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.  Let us define a function f(r, c) as follows:    * f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)  Given are integers r_1, r_2, c_1, and c_2. Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

Submission attempts (in order):
mod = 10 ** 9 + 7
N = 2 * 10 ** 6

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


r1, c1, r2, c2 = map(int, input().split())
answer = 0

for r in range(r1, r2 + 1):
    for c in range(c1, c2 + 1):
        answer += com(r + c, c)
        answer %= mod
print(answer)


mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10

fac = [0] * N
finv = [0] * N
inv = [0] * N

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, N):
    fac[i] = fac[i - 1] * i % mod
    
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    global fac, finv, mod
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod

def g(r, c):
    return (com(r + c + 2, r + 1) - 1) % mod

r1, c1, r2, c2 = map(int, input().split())

answer = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
answer %= mod
print(answer)


def main():
    mod = 10 ** 9 + 7
    N = 2 * 10 ** 6 + 3

    fac = [0] * N
    finv = [0] * N
    inv = [0] * N

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, N):
        fac[i] = fac[i - 1] * i % mod
        
        # inv[i] = mod - inv[mod % i] * (mod // i) % mod
        # finv[i] = finv[i - 1] * inv[i] % mod
    
    finv[N // 2] = pow(fac[N // 2], mod - 2, mod)
    for i in reversed(range(N // 2)):
        finv[i] = (finv[i + 1] * (i + 1)) % mod

    def com(r, c):
        ans = fac[r + c] * finv[r] * finv[c]
        return ans % mod

    def g(r, c):
        return (com(r + 1, c + 1) - 1) % mod

    r1, c1, r2, c2 = map(int, input().split())

    answer = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
    answer %= mod
    print(answer)

if __name__ == "__main__":
    main()


Verdicts: Time Limit Exceeded

Time Limit Exceeded

Accepted
Problem: Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.  Let us define a function f(r, c) as follows:    * f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)  Given are integers r_1, r_2, c_1, and c_2. Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

Submission attempts (in order):
import sys
input = sys.stdin.buffer.readline
 
def main():
    t,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,t)+comb(t,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

import sys
import math
import numpy
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
       
    def comb(x,y):
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
   
if __name__ == "__main__":
    main()

Verdicts: Runtime Error

Accepted
Problem: Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.  Let us define a function f(r, c) as follows:    * f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)  Given are integers r_1, r_2, c_1, and c_2. Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

Submission attempts (in order):
# F - Many Many Paths
def get_factorials(lim: int, MOD: int) -> list:
    """Compute a table of factorials (1-indexed)."""
    factorials = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x *= i % MOD
        factorials[i] = x
    return factorials


def mod_comb_with_pow(n: int, k: int, MOD: int) -> int:
    """Compute nCr % MOD using pow(), not an inverse factorial table."""
    return fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD) % MOD


def main():
    global fact
    MOD = 10 ** 9 + 7
    R1, C1, R2, C2 = map(int, input().split())
    fact = get_factorials(2 * 10 ** 6 + 10, MOD)
    f = lambda x, y: mod_comb_with_pow(x, y, MOD)
    ans = (f(C1 + R1, R1) - f(C1 + R2 + 1, R2 + 1) - f(C2 + R1 + 1, R1) + f(C2 + R2 + 2, R2 + 1)) % MOD
    print(ans)


if __name__ == "__main__":
    main()


# F - Many Many Paths
def get_factorials(lim: int, MOD: int) -> list:
    """Compute a table of factorials (1-indexed)."""
    factorials = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        factorials[i] = x
    return factorials


def mod_comb_with_pow(n: int, k: int, MOD: int) -> int:
    """Compute nCr % MOD using pow(), not an inverse factorial table."""
    return fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD) % MOD


def main():
    global fact
    MOD = 10 ** 9 + 7
    R1, C1, R2, C2 = map(int, input().split())
    fact = get_factorials(2 * 10 ** 6 + 10, MOD)
    f = lambda x, y: mod_comb_with_pow(x, y, MOD)
    ans = (f(C1 + R1, R1) - f(C1 + R2 + 1, R2 + 1) - f(C2 + R1 + 1, R1) + f(C2 + R2 + 2, R2 + 1)) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Verdicts: Time Limit Exceeded

Accepted