Connection Status:
Competition Arena > EllysThreeRivers

EllysThreeRivers

SRM 543 · 2011-11-22 · by espr1t

SRM 543 · 2011-11-22 · by espr1t · Search
Class Name: EllysThreeRivers
Return Type: double
Method Name: getMin
Arg Types: (int, int, vector<int>, vector<int>)
Problem Statement

Problem Statement

Shopping is by no means an easy task. Yes, sure, if you want to buy shoes or some clothes that's no problem at all. But what happens if you would like an extremely rare poison, found only in the mists of Amazonia? Now you see, Elly's life is not as easy as you would think. She has almost reached her final destination, but unfortunately she can only walk and swim in the final part.

There are 4 really long, but narrow parallel islands, going from South to North, numbered from 0 to 3, inclusive. All islands have the same length length. There are also 3 rivers between the islands, numbered from 0 to 2, inclusive. Each river has certain width, given in width. River i flows between islands i and i+1.
For simplicity we can represent the islands as vertical line segments in the plane. The first island goes from point (0, 0) to (0, length), the second one from (width[0], 0) to (width[0], length), the third one from (width[0] + width[1], 0) to (width[0] + width[1], length), and so on, where width[i] is the width of the i-th river.

Elly can walk along any island with a constant speed walk. At any point on the current island, Elly may decide to swim to some point on the next island. (Both points may have non-integer coordinates.) The speed of the water in the rivers is negligible, so Elly's speed while swimming is the same in all directions. However, different rivers may contain different amounts of plants and animals that influence Elly's speed. More precisely, while swimming between islands i and i+1, Elly's speed is swim[i]. Elly is currently on the southmost point of island 0 and wants to reach the northmost point of island 3. She wonders what is the minimal time required to travel to her destination.

You are given the length of the islands (in kilometers) in the int length and Elly's walking speed (in kilometers per hour) in the int walk. You are also given the int[]s width and swim, that give the width (in kilometers) and Elly's swimming speed (in kilometers per hour) for each river, respectively. Return a double denoting the minimal required time (in hours) for Elly to reach her destination.

Notes

  • Your return value must have a relative or an absolute error of less than 1e-9.
  • During her trip, Elly must swim exactly three times.

Constraints

  • length will be between 1 and 1000, inclusive.
  • walk will be between 1 and 100, inclusive.
  • width will contain exactly 3 elements.
  • swim will contain exactly 3 elements.
  • Each element of width will be between 1 and 1000, inclusive.
  • Each element of swim will be between 1 and 100, inclusive.
Examples
0)
10
8
{5, 2, 3}
{5, 2, 7}
Returns: 3.2063518370413364

One optimal way to reach the end point is by swimming from (0, 0) to (5, 4.003203734135), then walking to (5, 4.050839751462) on island 1, then swimming to (7, 4.567237538143) on island 2, then swimming to (10, 9.989414218372) on island 2 and walking the rest to (10, 10) on island 3. The required times are as follows: (0, 0) -> (5, 4.003203734135) = 6.405126082833 / 5 = 1.281025216567 (5, 4.003203734135) -> (5, 4.050839751462) = 0.047636017327 / 8 = 0.005954502166 (5, 4.050839751462) -> (7, 4.567237538143) = 2.065591119774 / 2 = 1.032795559887 (7, 4.567237538143) -> (10, 9.989414218372) = 6.196773350028 / 7 = 0.885253335718 (10, 9.989414218372) -> (10, 10.000000000000) = 0.010585781628 / 8 = 0.001323222703

1)
1000
100
{91, 911, 85}
{28, 97, 19}
Returns: 21.549321613601297

Even though the walking speed is greater than the swimming speed in all rivers, there is a way to achieve the optimal answer without walking.

2)
666
4
{777, 888, 999}
{11, 12, 13}
Returns: 228.26633673141083
3)
6
100
{2, 3, 4}
{77, 88, 99}
Returns: 0.12049782476139667
4)
873
54
{444, 588, 263}
{67, 97, 26}
Returns: 26.365540023205206

A large random example.

Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysThreeRivers with a public method double getMin(int length, int walk, vector<int> width, vector<int> swim) · 101 test cases · 2 s / 256 MB per case

Submitting as anonymous