PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given Chef’s scores in N assignments, each out of 100.
There is one assignment remaining.
What’s the minimum score Chef needs in the last assignment so that his overall score across all N+1 assignments is not less than 50\% of the total?
EXPLANATION:
There are N+1 assignments in total, each with a maximum score of 100 - meaning the total number of marks available is 100\cdot (N+1).
So, 50\% of the total score is exactly half of this, i.e, 50\cdot (N+1).
Chef’s current score is A_1 + A_2 + \ldots + A_N.
So, to reach 50\cdot (N+1), he needs a score of at least
on the final test.
Now,
- If this required score is \leq 0, it means Chef has already reached the threshold, so the answer is 0.
- If the required score is \gt 100, it’s not possible for Chef to achieve it in a single assignment since scores are out of 100. In this case, the answer is -1.
- If the required score is between 0 and 100, it’s achievable, and so it is the answer.
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()))
req = 50 * (n + 1)
cur = sum(a)
if cur + 100 < req: print(-1)
else: print(max(req - cur, 0))