PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
A footballer received R red cards and Y yellow cards.
Each red card received results in him being sent off.
Each two yellow cards received since the last send-off results in him being sent off.
Find the minimum number of send-offs possible.
EXPLANATION:
Each red card definitely results in the footballer being sent off.
Thus, at minimum, there are R send-offs.
We want to minimize the number of send-offs.
Observe that each send-off resulting from a red card can essentially free up one yellow card; since getting a yellow and then a red basically cancels out the yellow.
Thus, by getting cards in the order (yellow, red, yellow, red, yellow, red, …) we can cancel out upto R yellow cards.
There are now two possibilities:
- Y \le R
Here, we’re able to cancel out every yellow card.
So the minimum total number of send-offs will equal exactly R - one from each red card. - Y \gt R
Here, we’ll still have Y-R yellow cards remaining.
Each pair of them will now result in one send-off, so the total number of send-offs is half of Y-R (rounded down.)
So,
- If Y \le R the answer is R.
- If Y \gt R the answer is R + \text{floor}\left(\frac{Y-R}{2}\right).
It’s possible to combine both cases into the single expression
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
r, y = map(int, input().split())
print(r + (max(0, y-r))//2)