PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N seats in a row. The i-th seat costs A_i.
Chef and Chefina want to buy two adjacent seats. What’s the minimum amount they need to pay?
EXPLANATION:
If Chef and Chefina purchase seats i and i+1, they must pay a total of (A_i + A_{i+1}).
The answer is thus just the minimum of (A_i + A_{i+1}) across all 1 \le i \lt N.
This can be computed in linear time by simply iterating through the array.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 500
for i in range(n-1):
ans = min(ans, a[i] + a[i+1])
print(ans)