TheFrog
TCO13 Round 1A · 2013-02-19 · by gojira_tc
Problem Statement
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.
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.
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.
30000
{17, 25281, 5775, 2825, 14040}
{55, 26000, 5791, 3150, 14092}
Returns: 787.8787878787879
Submissions are judged against all 219 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheFrog with a public method double getMinimum(int D, vector<int> L, vector<int> R) · 219 test cases · 2 s / 256 MB per case