TheFrog | Topcoder Archive

Problem Statement

Frog Jim is fond of jumping. Moreover, all his jumps have the same length X. Currently, he is standing at the point 0 on the real axis. He needs to jump along the axis until he gets to point D or beyond it.

There are several pits between points 0 and D. For each valid i, there is a pit strictly between L[i] and R[i]. This means that Jim cannot step onto any point that is strictly between points L[i] and R[i]. (He is allowed to step onto the points L[i] and R[i]: as all pits are disjoint, the endpoints of each pit are always safe.)

Find the minimum length of jump X such that if Jim performs only jumps of length X, he can avoid every pit and get to point D or any point beyond it. Note that this length can be non-integer.

Definition

Class:: TheFrog
Method:: getMinimum
Parameters:: int, int[], int[]
Returns:: double
Method signature:: double getMinimum(int D, int[] L, int[] R)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

D will be between 1 and 30,000, inclusive.
L will contain between 1 and 50 elements, inclusive.
Each element of L will be between 0 and D-1, inclusive.
R will contain the same number of elements as L.
The i-th element of R will be between L[i]+1 and D, inclusive.
The intervals given by (L[i], R[i]) will not intersect.

Examples

```
16
```
```
{2}
```
```
{7}
```
```
Returns: 7.0
```
Moving by jumps of length 7, Jim goes from point 0 to point 7, then to point 14 and then to point 21, which is beyond 16. If Jim chose a shorter jump, he would end up in the pit.
```
25
```
```
{11, 3}
```
```
{21, 7}
```
```
Returns: 10.5
```
There are two pits. One of them is between points 11 and 21 and the other between points 3 and 7. By fixing jump length at 10.5, Jim successfully avoids them.
```
100
```
```
{0}
```
```
{100}
```
```
Returns: 100.0
```
Jim has no other choice but to jump right to point 100.
```
100
```
```
{0, 50}
```
```
{50, 100}
```
```
Returns: 50.0
```
In this case, point 50 is a suitable place to land, so Jim can choose X = 50.

{17, 25281, 5775, 2825, 14040}

{55, 26000, 5791, 3150, 14092}

Returns: 787.8787878787879

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.