PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: himanshu154
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
N people (including Om) stand for an election, which has M voters.
What’s the minimum number of votes Om needs to receive to ensure that he has always has strictly more votes than any other contestant?
EXPLANATION:
If Om receives x votes, clearly the worst case is when a single other candidate receives all of the remaining M-x votes.
So, for Om to have strictly more votes than any other contestant, x \gt M-x must hold.
This means 2x \gt M, i.e, x should be strictly more than half of M.
From here, it can be seen that:
- If M is even, the smallest valid x is \frac{M}{2} + 1.
- If M is odd, the smallest valid x is \frac{M+1}{2}.
Both cases can be put together into the simple formula
where \left \lfloor \ \cdot \ \right\rfloor denotes the floor function.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
print(m//2 + 1)