TopCoder Statistics - Problem Statement

Problem Statement

A man is moving on a raft near a village. The raft is travelling at a constant speed raftSpeed on a river that coincides with the X axis. The man can leave the raft, visit some sites in the village, and return back to the raft. The man leaves the raft as many times as he wants. During this entire time, the raft will continue to move at its original constant speed. The man can run with speed runSpeed, where runSpeed is greater than raftSpeed. He wants to visit at least K different sites. The raft starts infinitely to the left, passes the village, and moves infinitely to the right.

You will be given two int[]s x and y containing the coordinates of all the sites in the village. The i-th site is located at (x[i], y[i]). Return the minimal time the man must spend outside the raft to visit at least K different sites and return to the raft. You should neglect the sizes of the raft, the man, and the sites; assume they are all points.

Definition

Class:: Rafting
Method:: minRunningTime
Parameters:: int, int, int[], int[], int
Returns:: double
Method signature:: double minRunningTime(int raftSpeed, int runSpeed, int[] x, int[] y, int K)
(be sure your method is public)

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

raftSpeed will be between 1 and 50, inclusive.
runSpeed will be between raftSpeed+1 and 50, inclusive.
x will contain between 1 and 6 elements, inclusive.
y will contain exactly n elements, where n is the number of elements in x.
Each element of x will be between -50 and 50, inclusive.
Each element of y will be between 1 and 50, inclusive.
K will be between 1 and n, inclusive.

Examples

1

50

{0}

{1}

1

Returns: 0.04000800240080029

The man can run very fast, so he should leave the raft near point (0, 0) and return near this point too.
1

50

{0, 0}

{1, 1}

2

Returns: 0.04000800240080029

The sites can coincide.
1

2

{0}

{1}

1

Returns: 1.1547005383792515

The man should leave the raft near the point (-sqrt(3) / 3, 0) and come back near the point (+sqrt(3) / 3, 0).
1

50

{10, -10}

{1, 1}

2

Returns: 0.08001600480160058

The man should leave the raft twice to visit two sites separately.
4

21

{6, -1, 4, 6, 7, 1}

{1, 5, 3, 2, 5, 2}

6

Returns: 0.9517633779247896
1

5

{0,1}

{1,1}

2

Returns: 0.607625218510765
49

50

{-50,0,50}

{50,1,50}

3

Returns: 42.532716952546224
10

30

{0,50}

{50,50}

2

Returns: 5.0
16

22

{9,-3,13}

{6,1,3}

3

Returns: 0.9312790629079654
1

47

{34, -49}

{13, 1}

1

Returns: 0.04256282653793742
48

49

{28, 3, -38, -35, -1}

{3, 32, 33, 9, 11}

5

Returns: 52.17720575668599
48

49

{-10, -36, -24, -44, -19, -27}

{47, 48, 38, 27, 1, 43}

6

Returns: 77.22074467708595
49

50

{ -50, -50, -18, -18, 18, 18}

{ 1, 50, 1, 50, 1, 50}

6

Returns: 139.52379503279133
1

50

{ -50, 50 }

{ 1, 1 }

2

Returns: 0.08001600480160058
49

50

{ -33, -33 }

{ 1, 50 }

2

Returns: 49.53573221743627
1

50

{ -50, 50 }

{1, 1}

2

Returns: 0.08001600480160058
4

16

{12, -15, 5, 15, 0, 2}

{1, 13, 20, 9, 1, 14}

6

Returns: 4.492671784090256
5

26

{-10, 1, -6, -4, -10, -10}

{34, 45, 1, 27, 22, 1}

6

Returns: 3.945610015789649
16

49

{-2, -7, 0, 1, -4}

{37, 1, 38, 1, 4}

5

Returns: 1.8944444657238784
31

50

{13, 11, -5}

{1, 39, 2}

3

Returns: 2.6941908797571386
19

42

{-2, 5, 6}

{1, 25, 2}

3

Returns: 1.5538365034433705
9

31

{-9, -10, -9, -18, -13}

{35, 1, 22, 3, 39}

5

Returns: 3.030100548046264
10

24

{-5, 9, 8, -4, -8}

{1, 40, 2, 19, 29}

5

Returns: 4.871077163256746
12

38

{-4, 1, 6, -5, -4, -12}

{2, 1, 18, 9, 14, 19}

6

Returns: 1.7792046616099482
22

43

{13, -4, 11, 11, 3, -8}

{44, 2, 39, 2, 33, 44}

5

Returns: 2.9980665282724885
12

20

{-5, 8, 9, -3, 0}

{1, 21, 3, 23, 27}

3

Returns: 3.3416151511202323
19

46

{11, 9, -10, 7, 3, -3}

{14, 18, 19, 1, 10, 3}

6

Returns: 1.6533459577798966
13

22

{-2, -22, -1}

{33, 2, 3}

3

Returns: 4.776919105342279
13

38

{-19, -15, -22, 21, -8, 2}

{1, 11, 13, 20, 1, 17}

5

Returns: 1.7832611651271895
18

37

{3, -1, 11, -2}

{19, 26, 1, 4}

4

Returns: 1.9542933341230255
13

36

{2, -6, -9, -10}

{1, 4, 25, 3}

4

Returns: 1.7481652109585561
16

33

{1, 18, 17, 27, 35}

{1, 45, 34, 11, 33}

5

Returns: 3.8820542816473487
11

17

{26, 38, 38, -10, -27}

{1, 16, 2, 1, 19}

4

Returns: 3.389259305939259
10

49

{-8, 6, -1, -8, -3, -5}

{1, 16, 1, 34, 43, 40}

4

Returns: 1.5825875396184554
22

43

{7, -12, 23, -5, 14}

{24, 27, 27, 24, 25}

2

Returns: 1.4404672813472295
22

26

{3, 3, 1, 2, 0, -2}

{42, 41, 41, 41, 43, 41}

5

Returns: 6.213798042761099
26

41

{-5, 6, -10, 6}

{18, 7, 16, 14}

4

Returns: 1.2949527433040422
37

44

{0, -2, 27, -5, -25, -22}

{39, 40, 37, 38, 37, 38}

6

Returns: 3.8854642073974692
32

42

{-21, 23, 14}

{38, 37, 33}

1

Returns: 2.4262082529095657
5

21

{-5, -22}

{8, 7}

2

Returns: 1.4708710135363805
20

50

{28, -17, 33, -17}

{18, 21, 21, 17}

3

Returns: 1.6865705342396584
11

30

{-24, 19, 19, 33, 3}

{12, 19, 27, 16, 33}

4

Returns: 2.9220806700980306
18

47

{13, -10, -8}

{10, 16, 4}

2

Returns: 0.6449148155868302
5

21

{-30, -23, 35, -8}

{17, 11, 15, 12}

4

Returns: 4.071640249470194
9

48

{2, -11, 6, 10}

{2, 2, 3, 2}

4

Returns: 0.36939905771603426
4

43

{-24, 9, 30, 31}

{2, 1, 11, 28}

3

Returns: 0.6539985702138723
8

45

{-8, -8, -27, 21, -2, 11}

{34, 9, 6, 18, 4, 28}

4

Returns: 1.5507371859975476
3

7

{-12, 25, 11, 45, -16, -45}

{20, 21, 15, 8, 23, 6}

5

Returns: 13.936897044425463
3

46

{-16, 28, 33, 5, 34}

{18, 17, 23, 7, 22}

5

Returns: 2.1398912547304656
15

37

{20, 15, 21, -7, -21, 6}

{2, 1, 1, 2, 2, 2}

5

Returns: 0.4180476645675417
18

28

{-32, 29, -4, 14, 20}

{1, 2, 1, 3, 2}

5

Returns: 0.7740430825519949
1

39

{23, 1, -3, 8}

{4, 2, 3, 2}

4

Returns: 0.5642880936468349
6

38

{23, -34, -2, 32, -16, -33}

{2, 3, 5, 15, 12, 1}

5

Returns: 1.1768112301063507
12

44

{-8, 49, 14, -42, 47, 1}

{3, 8, 2, 4, 5, 4}

4

Returns: 0.6141922686399943
4

44

{9, 33, 8, 47, -6, -28}

{8, 9, 9, 8, 8, 8}

6

Returns: 1.9250465437295121
14

33

{-12, -26, -33, -21, -40, 0}

{3, 3, 3, 2, 2, 2}

6

Returns: 0.9767627694284606
5

50

{-32, 7, 12, -2, -33, -19}

{5, 8, 1, 1, 1, 9}

6

Returns: 0.9662911047441769
3

12

{-32, 13, -16, -1, -29, 5}

{1, 1, 1, 1, 1, 1}

6

Returns: 1.0327955589886444
14

30

{-4, 6, -12, 27, -44, -18}

{1, 1, 2, 2, 2, 1}

6

Returns: 0.6784005252999682
3

15

{-15, -21, -9, 3, -4, 21}

{2, 1, 2, 2, 1, 2}

6

Returns: 1.3608276348795434
5

25

{2, 42, -2, -8, -41, 13}

{2, 5, 1, 2, 5, 2}

6

Returns: 1.388044187577134
3

7

{-24, 13, 25, -5, 34, -31}

{3, 3, 2, 2, 1, 2}

6

Returns: 4.110960958218894
30

41

{-17, 16, -29, -12, -1, 27}

{1, 2, 3, 1, 3, 1}

6

Returns: 0.7872218936609648
12

27

{-9, -5, 11, -13, 7, -2}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.49613893835683387
19

35

{-27, -33, 5, 26, 42, -17}

{1, 2, 3, 2, 2, 1}

6

Returns: 0.748455199183749
7

37

{-47, -1, 42, 28, 44, -14}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.33028912953790823
7

37

{23, 33, -8, -17, -22, -34}

{4, 3, 1, 2, 2, 1}

6

Returns: 0.7156264473321345
10

44

{-32, 37, 7, -28, 22, -35}

{1, 6, 1, 1, 1, 1}

6

Returns: 0.5134360308102703
12

44

{-1, 16, 36, 23, 9, -22}

{2, 1, 1, 3, 2, 1}

6

Returns: 0.4724555912615341
5

34

{30, 23, 39, 28, -41, 14}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.35682062007003157
5

31

{1, 10, -25, -10, -17, 15}

{2, 1, 2, 1, 1, 1}

6

Returns: 0.5229763603684908
3

5

{-48, -28, 5, -44, 8, 39}

{1, 1, 1, 1, 1, 1}

6

Returns: 2.999999999999999
5

13

{-27, 8, 38, 29, -35, -2}

{1, 1, 1, 1, 1, 1}

6

Returns: 1.0
14

49

{-8, 25, -39, 19, 0, -28}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.255550625999976
2

39

{42, 22, -23, -47, -33, -39}

{1, 2, 3, 1, 3, 2}

6

Returns: 0.6161953991557163
6

30

{26, 18, 22, 13, -8, 7}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.408248290463863
9

33

{12, -5, -8, 7, -11, -24}

{1, 1, 1, 2, 2, 2}

6

Returns: 0.5669467095138409
21

46

{-32, -14, -24, -2, 12, -29}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.29320666645513255
2

27

{-12, 6, -6, 3, -3, 0}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.4456688116249245
26

40

{12, -5, 27, -17, 20, -1}

{1, 1, 1, 1, 1, 1}

6

Returns: 0.3947710169758613
10

46

{-25, -15, -5, -19, 25, -10}

{1, 2, 2, 2, 1, 2}

6

Returns: 0.44543540318737407
4

47

{36, 13, -10, -38, -24, 25}

{2, 1, 2, 1, 1, 2}

6

Returns: 0.38437327958308387
7

47

{-19, -34, 2, -6, 14, 31}

{3, 4, 4, 1, 1, 1}

6

Returns: 0.6024640760767095
1

50

{-50, -50, -50}

{1, 1, 1}

3

Returns: 0.04000800240080029
2

50

{50, -50}

{1, 50}

2

Returns: 2.0416339610148615
1

50

{-50, -50, -50}

{50, 50, 50}

3

Returns: 2.0004001200400143
1

50

{50, 50, 50, 50, -50}

{1, 1, 1, 1, 1}

1

Returns: 0.04000800240080029
2

49

{-50, -50}

{50, 1}

2

Returns: 2.044155165143059
1

49

{50, -50, -50}

{50, 50, 50}

2

Returns: 2.0412414523193156
1

49

{-50}

{1}

1

Returns: 0.04082482904638631
1

49

{50}

{1}

1

Returns: 0.040824829046386304
2

50

{-50, -50, -50, -50, -50}

{50, 1, 1, 1, 50}

2

Returns: 0.04003203845127179
1

50

{50, 50, -50, 50}

{1, 1, 1, 1}

4

Returns: 0.08001600480160058
1

49

{-50, -50, -50, -50, -50, -50}

{1, 1, 1, 50, 1, 50}

5

Returns: 2.0416499931971703
2

50

{50, 50, -50}

{1, 1, 50}

3

Returns: 2.0416339610148615
2

50

{-50, -50, -50, -50, -50}

{1, 1, 1, 1, 1}

1

Returns: 0.04003203845127179
2

49

{-50}

{50}

1

Returns: 2.0425184255141677
2

49

{-50}

{50}

1

Returns: 2.0425184255141677
2

49

{-50, -50, 50, 50, 50, 50}

{1, 1, 1, 1, 1, 1}

2

Returns: 0.04085036851028334
1

49

{-50, -50}

{50, 1}

2

Returns: 2.0416499931971703
1

50

{50, -50, -50, -50}

{1, 50, 50, 50}

1

Returns: 0.0400080024008003
1

50

{-50, -50}

{1, 1}

2

Returns: 0.04000800240080029
2

50

{50, 50}

{1, 1}

2

Returns: 0.04003203845127178

Statistics

Problem Statement for "Rafting"

Problem Statement

Definition

Notes

Constraints

Examples