Statistics

Problem Statement for "EllysThreeRivers"

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.

Definition

Class:
EllysThreeRivers
Method:
getMin
Parameters:
int, int, int[], int[]
Returns:
double
Method signature:
double getMin(int length, int walk, int[] width, int[] swim)
(be sure your method is public)

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

  1. 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

  2. 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.

  3. 666

    4

    {777, 888, 999}

    {11, 12, 13}

    Returns: 228.26633673141083

  4. 6

    100

    {2, 3, 4}

    {77, 88, 99}

    Returns: 0.12049782476139667

  5. 873

    54

    {444, 588, 263}

    {67, 97, 26}

    Returns: 26.365540023205206

    A large random example.

  6. 10

    3

    {5, 2, 3}

    {5, 2, 7}

    Returns: 3.206358804145409

  7. 42

    99

    {1, 1, 1}

    {1, 1, 1}

    Returns: 3.4240893747308077

  8. 1000

    100

    {1, 1, 1}

    {1, 1, 1}

    Returns: 12.999849996249809

  9. 1

    1

    {1, 1, 1}

    {100, 1, 1}

    Returns: 2.014092488547563

  10. 1000

    1

    {1000, 1000, 1000}

    {100, 1, 1}

    Returns: 2014.092488547563

  11. 1

    1

    {1, 1, 1}

    {1, 100, 1}

    Returns: 2.014092488547563

  12. 1000

    1

    {1000, 1000, 1000}

    {1, 100, 1}

    Returns: 2014.0924885475633

  13. 1

    1

    {1, 1, 1}

    {1, 1, 100}

    Returns: 2.014092488547563

  14. 1000

    1

    {1000, 1000, 1000}

    {1, 1, 100}

    Returns: 2014.0924885475633

  15. 1

    1

    {1, 1, 1}

    {100, 100, 1}

    Returns: 1.02235071540691

  16. 1000

    1

    {1000, 1000, 1000}

    {100, 100, 1}

    Returns: 1022.3507154069101

  17. 1

    1

    {1, 1, 1}

    {100, 1, 100}

    Returns: 1.02235071540691

  18. 1000

    1

    {1000, 1000, 1000}

    {100, 1, 100}

    Returns: 1022.3507154069101

  19. 1

    1

    {1, 1, 1}

    {1, 100, 100}

    Returns: 1.0223507154069102

  20. 1000

    1

    {1000, 1000, 1000}

    {1, 100, 100}

    Returns: 1022.3507154069101

  21. 1

    1

    {1, 1, 1}

    {100, 100, 100}

    Returns: 0.03162277660168379

  22. 1000

    1

    {1000, 1000, 1000}

    {100, 100, 100}

    Returns: 31.62277660168379

  23. 1000

    2

    {1, 1, 1}

    {1, 1, 1}

    Returns: 502.59807621135326

  24. 1

    100

    {1, 1, 1}

    {100, 100, 100}

    Returns: 0.03162277660168379

  25. 1000

    1

    {1000, 1000, 1000}

    {1, 1, 1}

    Returns: 3162.277660168379

  26. 989

    1

    {999, 2, 998}

    {24, 1, 98}

    Returns: 57.39415929575806

  27. 969

    1

    {713, 999, 68}

    {99, 97, 99}

    Returns: 20.7079155100707

  28. 997

    1

    {2, 1, 1000}

    {98, 1, 99}

    Returns: 15.278151634263711

  29. 709

    81

    {319, 795, 697}

    {95, 73, 44}

    Returns: 32.106959944330384

  30. 812

    55

    {477, 837, 590}

    {26, 93, 88}

    Returns: 36.24002021182467

  31. 692

    70

    {383, 153, 862}

    {12, 83, 75}

    Returns: 47.9315091426996

  32. 770

    71

    {57, 153, 325}

    {97, 68, 79}

    Returns: 12.015184548144735

  33. 424

    60

    {163, 275, 979}

    {31, 86, 4}

    Returns: 255.48147597689908

  34. 115

    2

    {787, 933, 48}

    {50, 46, 5}

    Returns: 45.70266338154858

  35. 655

    69

    {90, 240, 992}

    {1, 7, 44}

    Returns: 151.16660851530833

  36. 430

    83

    {992, 88, 120}

    {39, 47, 37}

    Returns: 32.44783787996134

  37. 2

    12

    {478, 728, 533}

    {23, 13, 85}

    Returns: 83.05322734314836

  38. 351

    8

    {812, 974, 778}

    {89, 40, 2}

    Returns: 423.0124734394166

  39. 283

    41

    {73, 994, 807}

    {50, 41, 32}

    Returns: 51.48946675617956

  40. 6

    92

    {677, 10, 503}

    {8, 29, 7}

    Returns: 156.82892122287066

  41. 982

    15

    {729, 128, 907}

    {48, 98, 80}

    Returns: 31.522247049508906

  42. 848

    55

    {215, 244, 956}

    {34, 27, 1}

    Returns: 984.1038328477277

  43. 29

    2

    {726, 104, 658}

    {11, 78, 85}

    Returns: 75.08034631941547

  44. 838

    95

    {466, 941, 356}

    {85, 39, 46}

    Returns: 40.84960192326622

  45. 174

    89

    {762, 702, 126}

    {2, 28, 41}

    Returns: 409.71354053673

  46. 644

    9

    {48, 560, 124}

    {51, 15, 6}

    Returns: 68.88188261221158

  47. 214

    41

    {961, 279, 306}

    {25, 15, 39}

    Returns: 65.45313672794364

  48. 211

    95

    {970, 10, 87}

    {52, 33, 55}

    Returns: 20.93552939515498

  49. 67

    38

    {899, 552, 559}

    {98, 87, 29}

    Returns: 34.808887106462585

  50. 330

    26

    {796, 972, 98}

    {37, 98, 53}

    Returns: 33.69514341197416

  51. 973

    1

    {855, 279, 205}

    {41, 74, 32}

    Returns: 37.517105353602425

  52. 593

    43

    {311, 735, 145}

    {94, 57, 24}

    Returns: 24.424179011925297

  53. 310

    31

    {113, 937, 888}

    {23, 2, 21}

    Returns: 517.7394187366211

  54. 87

    18

    {839, 328, 747}

    {64, 7, 14}

    Returns: 113.3805319183649

  55. 628

    73

    {46, 765, 389}

    {35, 25, 94}

    Returns: 38.99598774222261

  56. 407

    68

    {692, 662, 114}

    {29, 65, 32}

    Returns: 38.81645919705065

  57. 67

    48

    {781, 456, 187}

    {28, 69, 77}

    Returns: 36.96323250634985

  58. 989

    33

    {614, 233, 894}

    {1, 17, 43}

    Returns: 658.0423724301088

  59. 294

    4

    {602, 858, 310}

    {79, 25, 9}

    Returns: 76.97596638669066

  60. 557

    12

    {116, 836, 932}

    {59, 17, 22}

    Returns: 97.07663104364889

  61. 761

    39

    {327, 471, 664}

    {56, 52, 50}

    Returns: 31.75724168700356

  62. 999

    46

    {181, 517, 10}

    {67, 10, 42}

    Returns: 66.48183264749993

  63. 136

    75

    {754, 73, 59}

    {43, 16, 30}

    Returns: 24.323918002565193

  64. 45

    28

    {786, 523, 677}

    {29, 51, 82}

    Returns: 45.62409045159258

  65. 843

    20

    {510, 821, 324}

    {86, 38, 9}

    Returns: 67.55406014205694

  66. 854

    85

    {266, 872, 549}

    {14, 24, 61}

    Returns: 69.9108380055342

  67. 557

    87

    {780, 532, 345}

    {80, 48, 20}

    Returns: 39.654756741789996

  68. 447

    98

    {831, 776, 673}

    {81, 6, 40}

    Returns: 157.4034961575639

  69. 321

    44

    {849, 181, 829}

    {35, 47, 70}

    Returns: 40.48115784296614

  70. 319

    60

    {256, 570, 606}

    {60, 84, 40}

    Returns: 26.774690457728852

  71. 552

    81

    {949, 215, 233}

    {88, 46, 11}

    Returns: 38.14455919341227

  72. 947

    8

    {199, 838, 813}

    {96, 80, 87}

    Returns: 24.583049189630813

  73. 88

    19

    {761, 540, 47}

    {75, 22, 82}

    Returns: 35.318378376304636

  74. 114

    9

    {349, 94, 877}

    {43, 58, 50}

    Returns: 27.37782062653215

  75. 638

    99

    {122, 12, 619}

    {35, 8, 72}

    Returns: 17.11633956822566

  76. 491

    67

    {43, 665, 453}

    {29, 51, 43}

    Returns: 27.169025630459775

  77. 126

    53

    {685, 558, 34}

    {7, 56, 61}

    Returns: 108.58549824021065

  78. 53

    6

    {908, 460, 302}

    {96, 86, 68}

    Returns: 19.257881810598185

  79. 537

    74

    {250, 518, 310}

    {31, 43, 31}

    Returns: 33.53098194495919

  80. 102

    89

    {921, 907, 271}

    {28, 96, 20}

    Returns: 55.93469727895131

  81. 199

    96

    {805, 106, 577}

    {20, 59, 17}

    Returns: 76.59765877394904

  82. 167

    92

    {356, 304, 874}

    {9, 42, 36}

    Returns: 71.36418177355154

  83. 966

    99

    {809, 62, 553}

    {77, 26, 41}

    Returns: 31.128434370498113

  84. 303

    64

    {40, 346, 406}

    {27, 19, 21}

    Returns: 41.730025470435145

  85. 83

    60

    {527, 914, 581}

    {51, 60, 29}

    Returns: 45.63607787572167

  86. 734

    9

    {263, 697, 373}

    {37, 89, 31}

    Returns: 29.877137586542624

  87. 664

    92

    {711, 649, 758}

    {23, 93, 66}

    Returns: 51.0493659167597

  88. 251

    80

    {293, 416, 1000}

    {13, 8, 21}

    Returns: 123.26913569830492

  89. 494

    46

    {661, 308, 488}

    {7, 90, 18}

    Returns: 127.45692621793788

  90. 593

    51

    {716, 732, 169}

    {51, 38, 32}

    Returns: 41.018447555490496

  91. 995

    45

    {934, 711, 369}

    {21, 34, 4}

    Returns: 167.64403179133967

  92. 911

    85

    {256, 875, 457}

    {26, 66, 37}

    Returns: 40.08971926083948

  93. 702

    46

    {84, 60, 666}

    {63, 29, 5}

    Returns: 145.84958532668242

  94. 150

    66

    {125, 94, 866}

    {50, 71, 23}

    Returns: 41.81541544551314

  95. 161

    20

    {944, 85, 829}

    {83, 44, 13}

    Returns: 77.21348467778316

  96. 728

    35

    {335, 603, 829}

    {40, 62, 76}

    Returns: 31.235343404112808

  97. 632

    21

    {831, 943, 327}

    {4, 12, 59}

    Returns: 296.8753293921628

  98. 677

    5

    {793, 437, 511}

    {91, 14, 11}

    Returns: 88.84845402789122

  99. 425

    32

    {183, 541, 440}

    {66, 51, 42}

    Returns: 25.35718130871519

  100. 840

    36

    {474, 806, 762}

    {5, 36, 34}

    Returns: 145.40920036869377

  101. 6

    100

    {2, 3, 4 }

    {77, 88, 99 }

    Returns: 0.12049782476139667

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.
This problem was used for: