PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
924
PREREQUISITES:
None
PROBLEM:
A hare and a tortoise run a race that’s L meters long.
The tortoise moves at V_1 meters per second, the hare at V_2 meters per second.
The time calculated is the true time rounded up to the nearest integer.
Find the maximum amount of time that the hare can wait while still being able to beat the tortoise.
EXPLANATION:
The course is L meters long, and the tortoise moves at V_1 meters per second.
So, the tortoise will take \frac{L}{V_1} seconds to finish the race.
The reported time will thus be \left\lceil \frac{L}{V_1} \right\rceil, because we round upwards.
Here, \lceil \ \rceil denotes the ceiling function.
Similarly, the hare’s reported time will be \left\lceil \frac{L}{V_2} \right\rceil seconds.
If the hare waits for X seconds before starting, its overall reported time will be X+ \left\lceil \frac{L}{V_2} \right\rceil.
So, we want to find the largest X such that
It’s easy to see that this is exactly \left(\left\lceil \frac{L}{V_1} \right\rceil - \left\lceil \frac{L}{V_2} \right\rceil - 1\right), because everything is an integer.
Alternately, you can run a loop over X from 0 to 1000, each time checking whether the condition is satisfied - the constraints are small enough that this will run fast.
Note that when \left\lceil \frac{L}{V_2} \right\rceil = \left\lceil \frac{L}{V_1} \right\rceil, the hare can’t win; so the answer is -1.
However, the formula we obtained nicely takes care of this as well, so a special check isn’t necessary.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
l, v1, v2 = map(int, input().split())
tortoise, hare = (l + v1 - 1) // v1, (l + v2 - 1) // v2
print(tortoise - hare - 1)