TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
def main():
    s = int(input())
    mod = 10**9+7
    dp = [0] * (s+1)
    dp[0] = 1
    for i in range(1, s+1):
        for j in range(1, (i-3)+1):
            dp[i] += dp[j]
            dp[i] %= mod
    print(dp[s])

if __name__ == "__main__":
    main()


def main():
    s = int(input())
    mod = 10**9+7
    dp = [0] * (s+1)
    dp[0] = 1
    x = 0
    for i in range(1, s+1):
        if i-3 >= 0:
            x += dp[i-3]
            x %= mod
        dp[i] = x
    print(dp[s])

if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
import scipy.special.comb
S = int(input)
ans = 0
for i in range(3, S+1, 3):
  ans += scipy.special.comb(S-2*(i//3)-1, i//3-1, exact=True)
print(ans)

from scipy.special import comb
S = int(input())
ans = 0
mod = 10**9+7
for i in range(3, S+1, 3):
  ans = (ans +comb(S-2*(i//3)-1, i//3-1, exact=True)) % mod 
print(ans)


Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())

dp = [0] * (S+1)

dp[0] = 1

for i in range(S+1):
  for j in range(0,(i-3)+1):
    dp[i] += dp[j]
    dp[i] %= 10**9+7

print(dp[-1] % 10**9+7)

mod = pow(10,9) + 7
S = int(input())

dp = [0] * (S+1)

dp[0] = 1

for i in range(S+1):
  for j in range(0,(i-3)+1):
    dp[i] += dp[j]
    dp[i] %= mod

print(dp[-1] % mod)

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s = int(input())
MOD = 1000000007
dp = [0] * (s+1)
dp[0] = 1
for i in range(1, s+1):
    for j in range(0, (i-3)+1):
        dp[i] += dp[j]
        dp[i] %= MOD

print(dp)

s = int(input())
MOD = 1000000007
dp = [0] * (s+1)
dp[0] = 1
for i in range(1, s+1):
    for j in range(0, (i-3)+1):
        dp[i] += dp[j]
        dp[i] %= MOD

print(dp[s])

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
from scipy.special import comb
import copy

MOD = 10**+7
s = int(input())
num = copy.copy(s)
cnt = 0
ans = 0

while num // 3 > 1:
    num //= 3
    cnt += 1
    ans += comb(s-3*cnt, cnt, exact=True, repetition=True)%MOD

print(ans)

from scipy.special import comb
import copy

MOD = 10**9+7
s = int(input())
cnt = 0
ans = 1

if s <= 2:
    print(0)
else :
    s = s-3
    while s >= 3:
        s -= 3
        cnt += 1
        if s > 0:
            ans += comb(s+cnt, cnt, exact=True)
            ans %= MOD
        else :
            ans += 1
    ans %= MOD
    print(ans)


Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s = int(input())
l = 10**9+7
list_1 = [0, 1, 1, 1]
list_2 = [0, 1, 2]
for i in range(3, s):
  list_2.append((list_2[i-1] + list_1[i])%l)
  list_1.append(list_2[i-2])
if s = 1 or s = 2:
  print(0)
else:
  print(list_1[s-1])


s = int(input())
l = 10**9+7
list_1 = [0, 1, 1, 1]
list_2 = [0, 1, 2]
for i in range(3, s):
  list_2.append((list_2[i-1] + list_1[i])%l)
  list_1.append(list_2[i-2])
if s == 1 or s == 2:
  print(0)
else:
  print(list_1[s-1])



Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())

L = S//3
mod = 10**9+7

res = 0
from scipy.special import comb

for l in range(1,L+1):
    s = S - l*3
    a = comb(s+l-1, l-1)
    res += a

print(res%mod)

S = int(input())

L = S//3
mod = 10**9+7

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

res = 0

for l in range(1,L+1):
    s = S - l*3
    a = cmb(s+l-1, l-1)
    res += a

print(int(res%mod))

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
def dp(i):
    if i == 1 or i == 2:
        return 0
    elif i == 3 or i == 4:
        return 1
    else:
        return dp[i - 3] + dp[i - 1]


S = int(input())
print(dp(S))


S = int(input())
mod = 10 ** 9 + 7
dp = [0 for _ in range(S)]
dp[0] = dp[1] = 0
dp[2] = dp[3] = 0

for i in range(S - 3):
    dp[i + 3] = (dp[i] + dp[i + 2]) % mod
    
print(dp[-1])

import math

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

S = int(input())
ans = 0
mod = 10 ** 9 + 7
for i in range(1,S // 3 + 1):      
   
    x = S - 3 * i       
    
    ans += (combinations_count(x + i - 1, i - 1)) % mod　
    ans %= mod

print(ans)


S = int(input())
if S == 1 or S == 2:
    print(0)

elif S == 3:
    print(1)

else:
    mod = 10 ** 9 + 7
    dp = [0 for _ in range(S)]
    dp[0] = dp[1] = 0
    dp[2] = dp[3] = 1

    for i in range(3, S):
        dp[i] = (dp[i - 3] + dp[i - 1]) % mod

    print(dp[-1])

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
from math import comb
mod = 10**9 + 7
s = 1729
ans = 0
n = 1
while s - 2*n - 1 >= 0:
    ans += comb(s-2*n-1, n-1)
    ans %= mod
    n += 1
print(ans)

from math import comb
mod = 10**9 + 7
s = int(input())
ans = 0
n = 1
while s - 2*n - 1 >= 0:
    ans += comb(s-2*n-1, n-1)
    ans %= mod
    n += 1
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())
mod = 10**9+7
memo = [-1]*(S+1)
def redis(s):
  if memo[s] != -1:
    return memo[s]
  else:
    if s < 3:
      memo[s] = 0
      return 0
    elif s < 6:
      memo[s] = 1
      return 1
    else:
      tmp = 0
      for num in range(s):
        tmp += (redis(num)*redis(s-num))%mod
      memo[s] = tmp
      return tmp%mod
print(redis(S))
    



S = int(input())
mod = 10**9+7
memo = [-1]*(S+1)
def redis(s):
  if memo[s] != -1:
    return memo[s]
  else:
    if s < 3:
      memo[s] = 0
      return 0
    elif s < 6:
      memo[s] = 1
      return 1
    else:
      tmp = 0
      for num in range(s-2):
        tmp += redis(num)%mod
      memo[s] = tmp
      return tmp%mod
print(redis(S))
    



S = int(input())
memo = [-1]*(S+1)
redis(s):
  if memo[s] != -1:
    return memo[s]
  else:
    if s < 3:
      memo[s] = 0
      return 0
    elif s < 6:
      memo[s] = 1
      return 1
    else:
      tmp = 0
      for num in range(s):
        tmp += redis(num)*redis(s-num)
      memo[s] = tmp
      return tmp
print(redis(S))
    

S = int(input())
mod = 10**9+7
memo = [-1]*(S+1)
memo[0] = 1
def redis(s):
  if memo[s] != -1:
    return memo[s]
  else:
    if s < 3:
      memo[s] = 0
      return 0
    elif s < 6:
      memo[s] = 1
      return 1
    else:
      tmp = 0
      for num in range(s-2):
        tmp += redis(num)%mod
      memo[s] = tmp
      return tmp%mod
print(redis(S))
    




Verdicts: Runtime Error

Wrong Answer

Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
bun=[]
bun.append([0,0]+[1]*(s-2))
for j in range(1,s//3):
    bun.append([0]*(3*(j+1)-1)+[1])
    for i in range(3*(j+1),s):
        bun[j].append((bun[j][i-1]+bun[j-1][i-3])%(10**9+7))

ans=0
for i in range(s//3):
    ans = (ans+bun[i][s-1])%(10**9+7)

print(ans)

s=int(input())

bun=[]
bun.append([0,0]+[1]*(s-2))
for j in range(1,s//3):
    bun.append([0]*(3*(j+1)-1)+[1])
    for i in range(3*(j+1),s):
        bun[j].append((bun[j][i-1]+bun[j-1][i-3])%(10**9+7))

ans=0
for i in range(s//3):
    ans = (ans+bun[i][s-1])%(10**9+7)

print(ans)

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
from math import factorial
 
s = int(input())
 
ans = 0
for i in range(s // 3):
    box = i + 1  
    ball = s - 3 * box 
 
　　
    
    
    ans += factorial(ball + box - 1) // (factorial(ball) * factorial(box - 1)) % (10**9 + 7)
print(ans)

from math import factorial

s = int(input())
 
ans = 0
for i in range(s // 3):
    box = i + 1  
    ball = s - 3 * box 

　　
    
    
    ans += factorial(s_ + i) // (factorial(s_) * factorial(i)) % (10**9 + 7)

print(ans % (10 ** 9 + 7))

from math import factorial
 
s = int(input())
 
ans = 0
for i in range(s // 3):
    box = i + 1  
    ball = s - 3 * box 
 
　　
    
    
    ans += factorial(ball + box - 1) // (factorial(ball) * factorial(box - 1)) % (10**9 + 7)
 
print(ans % (10 ** 9 + 7))

from math import factorial
 
s = int(input())
 
ans = 0
for i in range(s // 3):
    box = i + 1  
    ball = s - 3 * box 
 
　　
    
    
    ans_ = factorial(ball + box - 1) // (factorial(ball) * factorial(box - 1)) % (10**9 + 7)
    ans += ans_
print(ans)

s = int(input())

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

ans = 0
for i in range(x):
    Box = i + 1
    Nokori = s - 3 * Box
    ans_ = cmb(Nokori + Box - 1, Box - 1) 
    ans += ans_
print(ans % (10 ** 9 + 7))

s = int(input())

from scipy.special import comb

ans = 0
for i in range(x):
    Box = i + 1
    Nokori = s - 3 * Box
    ans_ = comb(Nokori + Box - 1, Nokori, exact=True) % (10 ** 9 + 7)
    ans += ans_
    
print(ans % (10 ** 9 + 7))

from math import factorial
 
S = int(input())
 
ans = 0
for i in range(S // 3):
    box = i + 1  
    ball = S - 3 * box 
    ans_ = factorial(ball + box - 1) // (factorial(ball) * factorial(box - 1))
    ans += ans_
print(ans % (10 ** 9 + 7))

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
MOD = 10**9+7

s = int(input())
a = [0]*range(s+1)
a[0] = 1
for i in range(3, s+1):
    a[i] = sum(a[:i-2]) % MOD
print(a[s])


MOD = 10**9+7

s = int(input())
a = [0]*(s+1)
a[0] = 1
for i in range(3, s+1):
    a[i] = sum(a[:i-2]) % MOD
print(a[s])


Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s=int(input())
INF=10**9 + 7

dp=[0]*(s+1)
dp[0]=1

for i in range(1,s+1): 
	for j in range(0,(i-3)+1):
		dp[i]+=dp[j]
		dp[i]%=INF
	print(dp)

print(dp[-1])

s=int(input())
INF=10**9 + 7

dp=[0]*(s+1)
dp[0]=1

for i in range(1,s+1): 
	for j in range(0,(i-3)+1):
		dp[i]+=dp[j]
		dp[i]%=INF

print(dp[-1])

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())
mod = 10**9 + 7

dp = [0] * (S+1)
dp[0] = 1
for i in range(1, S+1):
    for j in range((i+3)+1):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[S])


S = int(input())
mod = 10**9 + 7

dp = [0] * (S+1)
dp[0] = 1
for i in range(1, s+1):
    for j in range((i+3)+1):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[S])


S = int(input())
mod = 10**9 + 7

dp = [0] * (S+1)
dp[0] = 1
for i in range(1, S+1):
    for j in range((i-3)+1):
        dp[i] += dp[j]
        dp[i] %= mod

print(dp[S])


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s = int(input())

fact = [1] * s
inv = [1] * s
invf = [1] * s
for i in range(2, s):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(p // i) * inv[p % i] % mod
  invf[i] = invf[i-1] * inv[i] % mod

count = 0
rest = s
for n in range(1, (s + 2) // 3):
  rest -= 3
  count = (count + inv[rest + n - 1] * invf[rest] * invf[n - 1]) % mod
print(count)

s = int(input())
mod = 10 ** 9 + 7

fact = [1] * s
inv = [1] * s
invf = [1] * s
for i in range(2, s):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(mod // i) * inv[mod % i] % mod
  invf[i] = invf[i-1] * inv[i] % mod

count = 0
rest = s
for n in range(1, s // 3 + 1):
  rest -= 3
  count = (count + fact[rest + n - 1] * invf[rest] * invf[n - 1]) % mod
print(count)

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
def f(n):
  if n <= 1:
    return 1
  return f(n-1)*n

def h(n,m):
  return f(n+m-1)/f(n)/f(m-1)

s=int(input())

res = 0

pair = s//3

for i in range(1,pair+1):
  res += h(s-3*i,i)
print(res)
  

def f(n):
  res = 1
  if n <= 1:
    return 1
  while n>1:
    res *= n
    n-=1
  return res
 
def h(n,m):
  return f(n+m-1)//f(n)//f(m-1)
 
s=int(input())
 
res = 0
 
pair = s//3
 
for i in range(1,pair+1):
  res += h(s-3*i,i)
print(res%(10**9+7))

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s = int(input())
a = [0]*2001
a[3] = 1
for i in range(4,n+1):
    a[i] = a[i-3] + a[i-1]
mod = 10**9+7
print(a[s]%mod)

s = int(input())
a = [0]*2001
a[3] = 1
for i in range(4,s+1):
    a[i] = a[i-3] + a[i-1]
mod = 10**9+7
print(a[s]%mod)

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
N = int(input())
a = [0,0,0,1,1,1,2,3,4,6,9]
s = 0
for nums in a:
  s += nums
if N <= 10:
  print(a[N])
else:
  while len(a)<=N:
    a.append(1+s-a[-1]-a[-2])
    s += a[-1]

p = 10**9+7
print(a[-1]%p)
    

N = int(input())
a = [0,0,0,1,1,1,2,3,4,6,9]
s = 0
for nums in a:
  s += nums
if N <= 10:
  print(a[N])
else:
  while len(a)<=N:
    a.append(1+s-a[-1]-a[-2])
    s += a[-1]
  p = 10**9+7
  print(a[-1]%p)
    

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

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


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


N = int(input())
ans = 0
amari = int(N % 3)
shou = int(N // 3)

for i in range(shou):

    ans = (ans + combinations_count((amari + shou - 1), amari)) % (10**9 + 7)
    amari += 3
    shou -= 1
    print(ans)
print(ans)


from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


N = int(input())
ans = 0
amari = int(N % 3)
shou = int(N // 3)

for i in range(shou):
    amari += 3
    shou -= 1
    ans = (ans + combinations_count((amari + shou - 1), amari)) % (10**9 + 7)
print(ans)


from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


N = int(input())
ans = 0
amari = int(N % 3)
shou = int(N // 3)

for i in range(shou):

    ans = (ans + combinations_count((amari + shou - 1), amari)) % (10**9 + 7)
    amari += 3
    shou -= 1
print(ans)


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
a,b,c=1,0,0
exec('a,b,c=b,c,a+c;'*int(input()))
print(a%(1e9+7))

a=1
b=c=0
exec('a,b,c=b,c,a+c;'*int(input()))
print(a%(10**9+7))

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())
mod = 10**9+7

dp = [1]+[0]*(S-1)

for i in range(0, S+1):
    for j in range(3, S-2):
        dp[i] += dp[j]

print(dp[S]%mod) 


S = int(input())
mod = 10**9+7

dp = [1]+[0]*S

for i in range(1, S+1):
    for j in range(0, i-2):
        dp[i] += dp[j]

print(dp[S]%mod)


Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline()[:-1]
mod = 10**9 + 7
def readInt():return int(input())
def readIntList():return list(map(int,input().split()))
def readStringList():return list(input())
def readStringListWithSpace():return list(input().split())
def readString():return input()

target = readInt()
nums = [i for i in range(3,target+1)]

dp = [0] * (1+target)
for num in nums:
    if num <= target:
        dp[num] = 1
for i in range(target+1):
    for num in nums:
        if i - num > 0:
            dp[i] += dp[i-num]
print(dp[-1]%mod

import sys
sys.setrecursionlimit(10**7)

def input(): return sys.stdin.readline()[:-1]
mod = 10**9 + 7
def readInt():return int(input())
def readIntList():return list(map(int,input().split()))
def readStringList():return list(input())
def readStringListWithSpace():return list(input().split())
def readString():return input()

target = readInt()
nums = [i for i in range(3,target+1)]

dp = [0] * (1+target)
for num in nums:
    if num <= target:
        dp[num] = 1
for i in range(target+1):
    for num in nums:
        if i - num > 0:
            dp[i] += dp[i-num]
print(dp[-1]%mod)

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())
from math import factorial
ans = 0


m = S // 3 

print(m)

for p in range(1,m+1):
    x = S - 3*(p) 
    a = factorial(x+p-1) 
    b = factorial(p-1) 
    c = factorial(x)
    ans += ( a / b / c )%(10**9+7)


print(int((ans)%(10**9+7)))




S = int(input())
from math import factorial
ans = 0


m = S // 3 

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



for p in range(1,m+1):
    x = S - 3*(p) 
    """
    a = factorial(x+p-1) 
    b = factorial(p-1) 
    c = factorial(x)
    ans += ( a / b / c )%(10**9+7)
    """
    ans += cmb(x+p-1,p-1)


print(int((ans)%(10**9+7)))




Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3 or s == 4:
  print(1)
else:
  array = np.zeros(s)
  array[2] = 1
  array[3] = 1
  for i in range(4, s):
    array[i] = (array[i-1] + array[i-3]) % mod
  print(array[s])


s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3 or s == 4:
  print(1)
else:
  array = np.zeros(s)
  array[2] = 1
  array[3] = 1
  for i in range(4, s):
    array[i] = (array[i-1] + array[i-3]) % mod
  print(array[s-1])

s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3 or s == 4:
  print(1)
else:
  array = np.zeros(s)
  array[2] = 1
  array[3] = 1
  for i in range(4, s):
    array[i] = (array[i-1] + array[i-3]) % mod
  print(array[s])

s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3:
  print(1)
else:
  array = np.zeros(s)
  array[2] = 1
  for i in range(3, s):
    array[i] = np.sum(array[:i-3]) % mod
  print(array[s-1])

s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3:
  print(1)
else:
  array = np.zeros(s+1)
  array[0] = 1
  for i in range(3, s+1):
    array[i] = np.sum(array[:i-2]) % mod
  print(array[s])


s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3:
  print(1)
else:
  array = np.zeros(s)
  array[0] = 1
  array[2] = 1
  for i in range(4, s):
    array[i] = (array[i-1] + array[i-3]) % mod
  print(array[s-1])

s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3 or s == 4:
  print(1)
else:
	array = np.zeros(s)
	array[2] = 1
	array[3] = 1
    for i in range(4, s):
      array[i] = (array[i-1] + array[i-3]) % mod
	print(array[s])

s = int(input())
mod = 10**9+7
import numpy as np

if s == 1 or s == 2:
  print(0)
elif s == 3:
  print(1)
else:
  array = np.zeros(s+1)
  array[0] = 1
  for i in range(3, s+1):
    array[i] = np.sum(array[:i-2]) % mod
  print(int(array[s]))


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


MOD = 10**9 + 7
N = 10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

ans = 0
for i in range(1, s // 3 + 1):
    rest = s - 3 * i
    ans += cmb(rest + i - 1, rest, MOD)

print(ans % MOD)

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


MOD = 10**9 + 7
N = 10**6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

s = int(input())

ans = 0
for i in range(1, s // 3 + 1):
    rest = s - 3 * i
    ans += cmb(rest + i - 1, rest, MOD)

print(ans % MOD)

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
n=int(input())
r=[list(map(int,input().split())) for _ in range(n)]
a,c,b,d=0,10**10,0,10**10
for i in range(n):
    x,y=r[i]
    a=max(a,x+y)
    c=min(c,x+y)
    b=max(b,x-y)
    d=min(d,x-y)
    d=max(0,d)
print(abs(max(a-c,b-d)))

n=int(input())
p=10**9+7
l=[1]*(2001)
l[1],l[2]=0,0
s=1
for i in range(6,2001):
    l[i]+=s
    l[i]%=p
    s+=l[i-2]
print(l[n])

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
import sys
readline=sys.stdin.readline

S = int(readline())




N = S // 3

DIV = 10 ** 9 + 7
n = (10 ** 6) * 2
g1 = [1] * 2 + [0] * (n - 2) 
g2 = [1] * 2 + [0] * (n - 2) 
inverse = [0, 1] + [0] * (n - 2) 計算用テーブル

for i in range(2, n):
  g1[i] = (g1[i - 1] * i) % DIV
  inverse[i] = (-inverse[DIV % i] * (DIV // i)) % DIV
  g2[i] = (g2[i - 1] * inverse[i]) % DIV

def nCr(n, r, DIV):
  if (r < 0 or r > n):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

ans = 0
for i in range(N, 0, -1):
  rest = S - 3 * i
  if rest <= 0:
    ans += 1
    continue
  
  
  ans += nCr(rest + i - 1, rest, DIV)
  ans %= DIV
  
print(ans)


import sys
readline=sys.stdin.readline

S = int(readline())




N = S // 3

DIV = 10 ** 9 + 7

from functools import reduce
def nCr(n,r,DIV):
  if r < n - r:
    r = n - r
  if r == 0:
    return 1
  f = lambda x,y:x*y%DIV
  X = reduce(f,range(n-r+1, n+1))
  Y = reduce(f,range(1, r+1))
  return X * pow(Y, DIV - 2, DIV) % DIV

ans = 0
for i in range(N, 0, -1):
  rest = S - 3 * i
  if rest <= 0:
    ans += 1
    continue
  
  
  ans += nCr(rest + i - 1, rest, DIV)
  ans %= DIV
  
print(ans)


Verdicts: Time Limit Exceeded

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
n=int(input())
mod = 10**9+7

dp = [0]*(s+1)
dp[0] = 1

print(dp[])

s=int(input())
mod = 10**9+7

dp = [0]*(s+1)
dp[0] = 1
x = 0

for i in range(1,s+1):
  if i-3>=0:
    x += dp[i-3]
    x %= mod
  dp[i]=x
print(dp[s])
    

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s=int(input())
if s==1:
    print(0)
exit()
mod=10**9+7
dp=[0]*(s+1)
dp[1]=0
dp[2]=0

for i in range(3,s+1):
    for j in range(3,i+1):
        dp[i]+=(dp[i-j])%mod
    dp[i]+=1

print(dp[s]%mod)

s=int(input())
if s==1:
    print(0)
　　exit()
mod=10**9+7
dp=[0]*(s+1)
dp[1]=0
dp[2]=0

for i in range(3,s+1):
    for j in range(3,i+1):
        dp[i]+=(dp[i-j])%mod
    dp[i]+=1

print(dp[s]%mod)

s=int(input())
if s==1:
    print(0)
    exit()
mod=10**9+7
dp=[0]*(s+1)
dp[1]=0
dp[2]=0

for i in range(3,s+1):
    for j in range(3,i+1):
        dp[i]+=(dp[i-j])%mod
    dp[i]+=1

print(dp[s]%mod)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
from scipy.special import comb


s = int(input())

if s < 3:
    print(0)
else:

    count = 0
    total = 0

    while True:
        s = s-3
        count += 1

        if s >= 0:
           total += comb(s+count-1, count-1)
        else:
            break

    print(total % (10**9+7))


from scipy.special import comb


s = int(input())

if s < 3:
    print(0)
else:

    count = 0
    total = 0

    while True:
        s = s-3
        count += 1

        if s >= 0:
           total += comb(s+count-1, count-1 ,exact=True)
           total = total% (10**9+7)
        else:
            break

    print(int(total ))


Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
S = int(input())
DP = [0]*(S+1)
DP[0] = 1
DP[1] = 0
DP[2] = 0
for TS in range(3,S+1):
    DP[TS] = (DP[TS-1]+DP[TS-3])%Mod
print(DP[S])

S = int(input())
DP = [0]*(S+1)
Mod = 10**9+7
if S>=3:
    DP[0] = 1
    DP[1] = 0
    DP[2] = 0
    for TS in range(3,S+1):
        DP[TS] = (DP[TS-1]+DP[TS-3])%Mod
    print(DP[S])
else:
    print(0)

Verdicts: Runtime Error

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
import numpy as np
 
n = int(input())
print(n)

import sys
import numpy as np

def dump(x):
    print(x, file=sys.stderr)


MOD = 10**9+7

N = int(input())
arr = np.zeros((N+1,N+1),dtype=int)
for i in range(3,N+1):
    arr[0,i] = 1

for i in range(1,N+1):
    sum_ = 0
    for j in range(3*i,N+1):
        sum_ += arr[i-1,j]
        sum_ %= MOD
        if j+3 >= N + 1:
            break
        arr[i,j+3] = sum_

dump(arr)

ans = 0
for i in range(N+1):
    ans += arr[i,N]
    ans %= MOD
print(ans)










Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
import scipy

mod = 10**9+7

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

s = int(input())
if s==1 or s==2:
    print(0)
    exit()

pk_num = s//3-1
ans = 1
for i in range(pk_num):
    pk = (i+2)*3
    g = s - pk
    b = i+2
    ans += cmb(g+b-1,b-1)
    ans %=  mod
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: Given is an integer S. Find how many sequences there are whose terms are all integers greater than or equal to 3, and whose sum is equal to S. The answer can be very large, so output it modulo 10^9 + 7.

Submission attempts (in order):
s=int(input())
mod=10**9+7
dp=[0]*s
dp[0]=1

for i in range(0,s+1):
	dp[i]=dp[i-1]+dp[i-3]
	dp[i]%=mod

print(dp[s])



s=int(input())
mod=10**9+7
dp=[0]*s


for i in range(4,s+1):
	for j in range(0,(i-3)+1):
		dp[i]+=dp[j]
		dp[i]%=mod
print(dp[s])



s=int(input())
mod=10**9+7
dp=[0]*(s+1)
dp[0]=1

for i in range(1,s+1):
	for j in range(0,(i-3)+1):
		dp[i]+=dp[j]
		dp[i]%=mod
print(dp[s])



Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
import sys

from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a = []
b = []
for i in range(n):
    x,y = rl()
    a.append(x+y)
    b.append(x-y)
a.sort()
b.sort()
print(max(a[-1]-a[0], b[-1]-[0]))

import sys

from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a = []
b = []
for i in range(n):
    x,y = rl()
    a.append(x+y)
    b.append(x-y)
a.sort()
b.sort()
print(max(a[-1]-a[0], b[-1]-b[0]))

Verdicts: Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:tuple(map(int,stdin.readline().split()))

n=int(input())

l=list(set(tuple([lnii() for i in range(n)])))
l.sort()
#rint(l)

if len(l)==1:
  print(0)
  exit()

max_v=0
min_v=10**10
for x,y in l:
  max_v=max(max_v,abs(x)+abs(y))
  min_x=max(max_v,abs(x)+abs(y))

print(max_v-min_v)

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:tuple(map(int,stdin.readline().split()))

n=int(input())

l=set(tuple([lnii() for i in range(n)]))

if len(l)==1:
  print(0)
  exit()

x_max=0
x_min=10**10
y_max=0
y_min=10**10
for x,y in l:
#  s=abs(x-y)
  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)

#  t=abs(x+y)
  t=x+y
  y_max=max(y_max,t)
  y_mim=min(y_min,t)


x_max=abs(x_max)
x_min=abs(x_min)
y_max=abs(y_max)
y_min=abs(y_min)
print(x_max,x_min,y_max,y_min)


print(max(x_max-x_min,x_max-y_min,y_max-y_min,y_max-x_min))

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:tuple(map(int,stdin.readline().split()))

n=int(input())

l=set(tuple([lnii() for i in range(n)]))

if len(l)==1:
  print(0)
  exit()

x_max=0
x_min=10**10
y_max=0
y_min=10**10

ans=0
for x,y in l:
#  s=abs(x-y)
  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)

#  t=abs(x+y)
  t=x+y
  y_max=max(y_max,t)
  y_mim=min(y_min,t)


  ans=max(s,y)
print(ans)

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

l=lnii()

if len(l)==1:
  print(0)
  exit()

x_max=0
x_min=10**10
y_max=0
y_min=10**10

for x,y in l:
  s=x-y
  x_max=max(x_max,s)
  x_min=min(x_min,s)

  t=x+y
  y_max=max(y_max,t)
  y_min=min(y_min,t)

x_ans=x_max-x_min
y_ans=y_max-y_min
print(max(x_ans,y_ans))

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())

z=[]
w=[]
for i in range(n):
  x,y=nii()
  z.append(x-y)
  w.append(x+y)

z_ans=max(z)-min(z)
w_ans=max(w)-min(w)
print(max(z_ans,w_ans))

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
def cost(x1,y1,x2,y2):
    return abs(x1-x2) + abs(y1-y2)


n = int(input())

x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
ans = - math.inf
for i in range(n):
    for j in range(i+1,n):
        ans = max(ans,cost(x[i],y[i],x[j],y[j]))
print(ans)

n = int(input())

x = []
y = []
for i in range(n):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
d1_max = x[0]+y[0]
d1_min = x[0]+y[0]
d2_max = x[0] - y[0]
d2_min = x[0]-y[0]
ans = -1
for i in range(1,n):
    d1_max = max(d1_max,x[i]+y[i])
    d1_min = min(d1_min,x[i]+y[i])
    d2_max = max(d2_max,x[i] - y[i])
    d2_min = min(d2_min,x[i]-y[i])
    ans = max((d1_max-d1_min),(d2_max-d2_min))
print(ans)

Verdicts: Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
p=sorted(l,key=lambda x: x[0]+x[1])
q=sorted(l,key=lambda x: x[0]-x[1])
print(max(p[-1]-p[0],q[-1]-q[0]))

n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
p=[a+b for a,b in l]
q=[a-b for a,b in l]
p.sort()
q.sort()
print(max(p[-1]-p[0],q[-1]-q[0]))


Verdicts: Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    x, y = MI()
    x1 = x
    x2 = x
    x3 = x
    x4 = x
    y1 = y
    y2 = y
    y3 = y
    y4 = y
    for _ in range(n-1):
        x, y = MI()
        if x+y > x1+y1:
            x1 = x
            y1 = y
        if -x+y > -x2+y2:
            x2 = x
            y2 = y
        if -x-y > -x3-y3:
            x3 = x
            y3 = y
        if x-y > x4-y4:
            x4 = x
            y4 = y
        temp = [abs(x1-x2)+abs(y1-y2), abs(x1-x3)+abs(y1-y3), abs(x1-x4)+abs(y1-y4), abs(x2-x3)+abs(y2-y3), abs(x2-x4)+abs(y2-y4), abs(x3-x4)+abs(y3-y4)]
        ans = max(temp)
        print(ans)

if __name__ == '__main__':
    main()

import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    x, y = MI()
    x1 = x
    x2 = x
    x3 = x
    x4 = x
    y1 = y
    y2 = y
    y3 = y
    y4 = y
    for _ in range(n-1):
        x, y = MI()
        if x+y > x1+y1:
            x1 = x
            y1 = y
        if -x+y > -x2+y2:
            x2 = x
            y2 = y
        if -x-y > -x3-y3:
            x3 = x
            y3 = y
        if x-y > x4-y4:
            x4 = x
            y4 = y
    temp = [abs(x1-x2)+abs(y1-y2), abs(x1-x3)+abs(y1-y3), abs(x1-x4)+abs(y1-y4), abs(x2-x3)+abs(y2-y3), abs(x2-x4)+abs(y2-y4), abs(x3-x4)+abs(y3-y4)]
    ans = max(temp)
    print(ans)

if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
n = int(input())
l = []
for i in range(n):
  l.append(list(map(int,input().split())))
m = []
for i in l:
  a,b = i
  k.append(a+b)
  m.append(a-b)
k.sort()
m.sort()
print(max([k[-1]-k[0],m[-1] -m[0]]))

n = int(input())
l = []
for i in range(n):
  l.append(list(map(int,input().split())))

k = []
m = []
for i in l:
  a,b = i
  k.append(a+b)
  m.append(a-b)
k.sort()
m.sort()
print(max([k[-1]-k[0],m[-1] -m[0]]))

Verdicts: Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
def main():
    N = int(input())
    pts = []
    m = 0
    a1 = 0
    a2 = 0
    b1 = 0
    b2 = 0
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()


def main():
    N = int(input())
    pts = []
    m = 0
    a1 = 0
    a2 = 0
    b1 = 0
    b2 = 0
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b1, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()


def main():
    N = int(input())
    pts = []
    m = 0
    a1 = 0
    a2 = 0
    b1 = 0
    b2 = 0
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(min(a1 - a2, b1 - b2))

main()


def main():
    N = int(input())
    x, y = map(int, input().split())
    a1 = x + y
    a2 = x + y
    b1 = y - x
    b2 = y - x
    N -= 1
    while N != 0:
        x, y = map(int, input().split())
        a1 = max(a1, x + y)
        a2 = min(a2, x + y)
        b1 = max(b1, y - x)
        b2 = min(b2, y - x)
        N = N - 1
    print(max(a1 - a2, b1 - b2))

main()


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

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

Xmax = -2*10**9
Ymax = -2*10**9
Xmin = 2*10**9
Ymin = 2*10**9


for i in range(N):
    x, y = map(int, input().split())
    if (x + y >= Xmax):
        Xmax = x + y
    if (x + y =< Xmin):
        Xmin = x + y
    if (x - y >= Ymax):
        Ymax = x - y
    if (x - y =< Ymin):
        Ymin = x - y

print(max(Xmax - Xmin, Ymax - Ymin))

N = int(input())

Xmax = -2*10**9
Ymax = -2*10**9
Xmin = 2*10**9
Ymin = 2*10**9


for i in range(N):
    x, y = map(int, input().split())
    if (x + y >= Xmax):
        Xmax = x + y
    if (x + y <= Xmin):
        Xmin = x + y
    if (x - y >= Ymax):
        Ymax = x - y
    if (x - y <= Ymin):
        Ymin = x - y

print(max(Xmax - Xmin, Ymax - Ymin))

Verdicts: Runtime Error

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
yx = [[y, x] for x, y in xy]
xy.sort()
yx.sort()
yx = [[x, y] for y, x in yx]

ans = 0
tmp = [xy[0], xy[-1], yx[0], yx[-1]]
print(yx)
for x, y in tmp:
    for x1, y1 in tmp:
        ans = max(ans, abs(x - x1) + abs(y - y1))
print(ans)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

f0 = [x - y for x, y in xy]
f1 = [x + y for x, y in xy]

f0.sort()
f1.sort()

ans = max((f0[-1] - f0[0]), (f1[-1] - f1[0]))
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=-10**9
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
for i in range(0,n):
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
for i in range(0,n):
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migsita=minlocal
for i in range(0,n):
    local=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
aa=migiue-hidarisita
bb=hidariue-migsita
print(max(aa,bb))

n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=0
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
for i in range(0,n):
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
for i in range(0,n):
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migsita=minlocal
for i in range(0,n):
    local=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
aa=migiue-hidarisita
bb=hidariue-migsita
print(max(aa,bb))

n = int(input())
hidarisita=2*10**9
migiue=0
migisita=2*10**9
hidariue=-10**9
x=[]
for i in range(0,n):
    x.append(list(map(int, input().split())))
    
for i in range(0,n):
    minlocal=x[i][0]+x[i][1]
    if minlocal<hidarisita:
        hidarisita=minlocal
    if minlocal==hidarisita:
        hidarisita2=minlocal
for i in range(0,n):
    maxlocal=x[i][0]+x[i][1]
    if maxlocal>migiue:
        migiue=maxlocal
    if maxlocal==migiue:
        migiue2=maxlocal
for i in range(0,n):
    minlocal=-x[i][0]+x[i][1]
    if minlocal<migisita:
        migisita=minlocal
    if minlocal==migisita:
        migisita2=minlocal
for i in range(0,n):
    maxlocal=-x[i][0]+x[i][1]
    if maxlocal>hidariue:
        hidariue=maxlocal
    if maxlocal==hidariue:
        hidariue2=maxlocal
aa=migiue-hidarisita
ab=migiue-hidarisita2
ba=migiue2-hidarisita
bb=migiue2-hidarisita2
cc=hidariue-migisita
cd=hidariue-migisita2
dc=hidariue2-migisita
dd=hidariue2-migisita2
print(max(aa,ab,ba,bb,cc,cd,dc,dd))

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There are N points on the 2D plane, i-th of which is located on (x_i, y_i). There can be multiple points that share the same coordinate. What is the maximum possible Manhattan distance between two distinct points?  Here, the _Manhattan distance_ between two points (x_i, y_i) and (x_j, y_j) is defined by |x_i-x_j| + |y_i-y_j|.

Submission attempts (in order):
def main():
  n = int(input())
  a_li , b_li = [] , []
  for _ in range(n):
    x , y = int(input())
    a_li.append(x + y)
    b_li.append(x - y)
    print(max(max(a_li) - min(a_li), max(b_li) - min(b_li)))

if __name__ == "__main__":
  main()

def main():
  n = int(input())
  a_li , b_li = [] , []
  for _ in range(n):
    x , y = map(int,input().split())
    a_li.append(x + y)
    b_li.append(x - y)
  print(max(max(a_li) - min(a_li), max(b_li) - min(b_li)))
 
if __name__ == "__main__":
  main()

Verdicts: Runtime Error

Accepted