PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: nskybytskyi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Alice has A slices of cake, Bob has B.
While they have different slice counts, Charlie will eat half the slices of whoever has more, rounded up.
Find the number of slices Charlie will eat.
EXPLANATION:
The constraints are small enough (A, B \leq 100) that direct simulation will be fast enough.
That is, while A \neq B, take whichever of them is larger and subtract half of it rounded up from it; then add this value to the answer.
To perform the rounding correctly, you can either use functions such as ceil (though make sure you don’t accidentally cast to integer before taking ceil), or do some simple casework depending on whether the value you’re dividing by 2 is even or odd.
TIME COMPLEXITY:
\mathcal{O}(\log\max(A, B)) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
a, b = map(int, input().split())
ans = 0
while a != b:
if a > b: a, b = b, a
# now b is larger
if b%2 == 0:
ans += b//2
b -= b//2
else:
ans += (b+1)//2
b -= (b+1)//2
print(ans)