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:
Chef has A milk chocolates and B dark chocolates.
He will repeat the following (A+B) times:
- Choose one chocolate that hasn’t been eaten yet, and eat it.
Chef’s satisfaction increases by 1 after each chocolate he eats, but only if the number of milk and dark chocolates eaten so far are not equal.
What’s his maximum possible satisfaction?
EXPLANATION:
Suppose A \gt B.
Then, Chef is able to obtain satisfaction from every chocolate he eats, because he can:
- First eat all A milk chocolates, one at a time.
This will increase his satisfaction by 1 each time, since the number of dark chocolates eaten so far will be 0 while the number of milk chocolates eaten is positive. - Then, eat all B dark chocolates, one at a time.
This will also increase his satisfaction by 1 each time, since the number of milk chocolates eaten so far will be A while the number of dark chocolates eaten is at most B (which is strictly less than A).
Thus, if A \gt B, the answer is just (A+B).
If A \lt B, the answer is similarly (A+B), since Chef can first eat all dark chocolates and then all milk chocolates.
When A = B however, observe that no matter what Chef does, the last chocolate he eats cannot give satisfaction; since the number of dark and milk chocolates will both equal A at that point.
However, he can get satisfaction from every other chocolate he eats, by first eating all milk chocolates and then all dark chocolates.
Thus, in this case, the answer is (A+B-1).
So, quite simply:
- If A = B, the answer is (A+B-1).
- Otherwise, the answer is (A+B).
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
a, b = map(int, input().split())
if a == b: print(a+b-1)
else: print(a+b)