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:
A party is contesting an election with N seats, and has won K of them.
How many more additional seats do they need in order to get a strict majority?
EXPLANATION:
Let R = \left\lfloor \frac{N}{2} \right\rfloor + 1 denote the number of seats required for a strict majority.
This is the smallest integer that’s larger than half of N.
If K \ge R, then the party already has enough seats, and doesn’t need any more.
The answer in this case is 0.
If K \lt R, then the party needs additional seats.
We’re looking to minimize the number of additional seats, so clearly it’s optimal to reach exactly R.
This requires (R - K) additional seats, which is the answer in this case.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
n, k = map(int, input().split())
req = n//2 + 1
if k >= req: print(0)
else: print(req - k)