CatAndRat
SRM 623 · 2013-12-22 · by standy
Problem Statement
At time 0, a rat enters the tube via the entrance. The rat can move inside the tube in both directions (clockwise and counterclockwise). The rat can change direction in an instant. Its maximum speed is Vrat.
At time T, the cat will enter the tube via the same entrance. The cat can also move in both directions and change its direction instantly. Its maximum speed is Vcat.
For the purpose of this problem, you should imagine the tube as a circle with radius R, and the rat and the cat as points on said circle.
The cat is trying to catch the rat as quickly as possible. The rat is trying not to be caught, and if that is impossible, to be caught as late as possible. At any time (starting at time 0) the cat and the rat know each other's position. Already at time 0 the rat knows the time T. Assume that both the cat and the rat behave optimally.
You are given the
Notes
- The cat and rat cannot leave the tube.
- Your return value must have a relative or absolute error less than 1e-9.
Constraints
- R, T, Vrat, and Vcat will each be between 1 and 1000, inclusive.
10 1 1 1 Returns: -1.0
The rat can survive. During the first unit of time it has to run away from the entrance. Then, once the cat enters the tube, the rat can always run in the same direction and with the same speed as the cat.
10 1 1 2 Returns: 1.0
The cat is now faster than the rat. The best strategy for the rat is to enter the tube and to start running in either direction at its maximum speed. The cat will then enter the tube, run in the same direction as the rat, and catch it in exactly 1 unit of time.
10 1 2 1 Returns: -1.0
The rat is now faster than the cat. It can survive, for example by using the strategy described in Example 0.
1000 1000 1 1000 Returns: 1.001001001001001
1 1000 1 2 Returns: 3.141592653589793
Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CatAndRat with a public method double getTime(int R, int T, int Vrat, int Vcat) · 45 test cases · 2 s / 256 MB per case