TopCoder Statistics - Problem Statement

Problem Statement

Pistol Pete, the neighborhood game dealer, has offered to let you play his newest game. Pete's going to let you throw a dart at his wall containing several targets. Depending on what target you hit, you will win a fabulous prize!

You've been practicing a game like this lately, and you figure it's right up your alley. You will hit the target you aim at with prob percent probability. When you miss the target you aim at, you will hit either of the adjacent targets with equal probability. Since the targets are arranged in a circular fashion, if you miss target 0, then you will either hit target 1 or target n-1, where n is the total number of targets. See example 0 for clarification.

Pete has given you a int[] payout, in which the i-th element corresponds to the payout of hitting target i. You will also be given prob, the percent probability your dart will hit the target you aim for. The total number of targets is equal to the number of elements in payout. Given this information, return a double with the average payout that you will get from Pete if you play optimally.

Definition

Class:: DartThrow
Method:: bestScore
Parameters:: int[], int
Returns:: double
Method signature:: double bestScore(int[] payout, int prob)
(be sure your method is public)

Notes

A return value with either an absolute or relative error of less than 1.0e-9 is considered correct.

Constraints

payout will contain between 3 and 50 elements, inclusive.
Each element of payout will be between 0 and 100, inclusive.
prob will be between 0 and 100, inclusive.

Examples

{10,40,50}

80

Returns: 45.0

In this case, you have three options: Aim at 10: Score = 10(0.8) + 50(0.1) + 40(0.1) = 17.0 Aim at 40: Score = 40(0.8) + 10(0.1) + 50(0.1) = 38.0 Aim at 50: Score = 50(0.8) + 40(0.1) + 10(0.1) = 45.0 Of the three options, the best score is 45, and so we return it.
{10,40,50}

61

Returns: 40.25

This time, you don't throw as well. In this case, it is best to aim for the 50, scoring 50(0.61) + 40(0.195) + 10(0.195) = 40.25.
{20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5}

60

Returns: 13.4

A standard dartboard.
{20,1,18,4,13,6,10,15,2,17,3,19,7,16,8,11,14,9,12,5}

20

Returns: 15.4

Sometimes missing can be a good thing.
{1,13,42,44,72,83,46,52,46,22,41,95,41,6,70,41,74,89,13,100,29,93,9,55,57,63,15,86,82,22,23,13,84,5,79,28,38,97,28,94,38}

68

Returns: 77.72
{16,99,96,26,71,9,89,43,11,41,58,84,27,8,17,54,26,36,87}

66

Returns: 84.61
{86,78,88,81,75,75,23,52,22}

93

Returns: 87.405
{10,47,100,50,4,93,43,22,62,64,81,84,90,25,32,41,68,25,69,3,80,62,100,70,59}

51

Returns: 84.735
{91,37,39,48,41,58}

46

Returns: 67.51
{69,16,9,13,12,71,3,31,30,32,28,22,25,49,16,91,80,3,48,58,29,57,56,51,73}

59

Returns: 73.37
{60,85,45,44,52,70,95,83,79,64,51}

91

Returns: 93.33500000000001
{75,59,93,37,87,16,86,95,60,97,1,76,92,3,43,76,47,22,53,30}

82

Returns: 91.03999999999999
{31,4,60,0,15,66,82,70,43,25,33,98,28,36,28,45,31,10,60,86,97,81,96,93,11,54,97,38,57,49,2,60,62,39,8,33,15,27,56,22,51,70,34,79,11,17,52,13,56,98}

78

Returns: 94.03
{65,18,74,60,59,13,96,0,75,9}

74

Returns: 72.72999999999999
{98,58,77,95,52,16,0,80,22,89,19,63,72,15,86,12,82,42,68,96,62,28,93}

60

Returns: 89.0
{42,68,78,44,90,28,47,51,42,94,73,46,15,42,75,49,63,74,9,51,34,62,31,31,30,68,33,79,66,83,36,58,73,39,7,82,6,3,73,70,98,48,40,5,23,71,83,36,58}

84

Returns: 91.75999999999999
{74,13,21,6,23,92,49,49,100,32,47,5,78,5,84,49,3,22,88,31,79,52,78,7,93,39,25,75,44,19,52,9,100,21,3}

33

Returns: 69.755
{48,43,11,75,80,22,58,80,60,78,44,98,38,14,68,98,50,79}

9

Returns: 85.035
{13,2,17,52,96,2,30,37,38,87,67,69,1,27,93,1,91,5,29,35,17,61,14,42,41,22,18,93,47,84,18,48,73,37,88,25,46,32,79,64,26,60,6,39,70}

86

Returns: 86.34
{17,1,71,15,58,93,90,20,64,73,36,75,43,14,28,18,46,51,76,83,25,73,71,47,3,94,98,68,72,38,19,77,81,78,22,12,48,95,54,74}

0

Returns: 85.0
{98,92,30,47,5,54,12,58,92,73,90,61,68,25,18,30,39,99}

5

Returns: 95.625
{19,48,11,84,85,77,92,8,61,10,9,46}

6

Returns: 87.81
{64,58,89,15,4,55,79,15,54,95,33,24,92}

83

Returns: 86.24499999999999
{92,33,48,50,3,84,80,99,54,3,97,38,47,43,79,79,14,98,78,67}

53

Returns: 85.405
{3,76,41,28,12,67,38,71,80,23,98,11,41}

27

Returns: 71.18
{35,68,41,75,0,26,100,25,75,40,66,51,68,92,19,60,86,91}

47

Returns: 80.435
{62,57,42,38}

99

Returns: 61.855000000000004
{17,13,5,96,22,55,68,83,2,91}

69

Returns: 70.425
{22,79,41,80,3,26,88,13,74,6,23,5,92,94,37,61,40,37,51,99,63,8,85,80,1,22}

92

Returns: 95.64
{41,79,41}

83

Returns: 72.53999999999999
{97,90,32,53,89,24,81,57,2,37,32,25,38,34,7,85,99,87,46,82,29,89,26,74,47,24,71,67,66,32,89,26,31,73,88,3,92,4,80,49}

9

Returns: 87.17
{85,27,100,5,57}

50

Returns: 63.5
{9,34,98,4,30,44,55,3,48,43,76,35,90,96,38,90,7,6,53,88,70,71,60,99,84,75,79,19,49,87,12,70,52,72,29,100,93,49,50,16,9,78,15,60,47}

57

Returns: 87.39
{61,65,61,41,93,32,94,87,52,97,70,97,59,33,28,97,97,78}

24

Returns: 90.52
{49,17,91,81,9,19,84,31,100,34,47}

90

Returns: 93.25
{90,52,16,21,91,95,21,0,58,7,9,6,39,43,14,63,1,28,85,78,18,67,90,68,27,42,80,31,57,60,99,88}

82

Returns: 94.5
{99,49,29,82,11,74,49,36,30,39,7,13,98,9,61,2,1,71,8,53,93,31,15,59,0,62,63,9,21,67,45,39,59,40,78,97,99,65}

43

Returns: 92.155
{40,54,81}

73

Returns: 71.82
{98,89,65,35,69,18}

44

Returns: 84.80000000000001
{94,77,97,42,100,73,60,38,43,52,0,52,31,35,75,26,22,34,71,43,88,84,28,52,14,92,62,2,76,74,42,95,98,8,32,82,46,63,9,78,93,92,1,87,62,47}

99

Returns: 99.575
{42,27,69,14,98,18,67,5,28,75,39,63,82,93,70}

92

Returns: 91.64
{6,25,77,69,83,74,11,59,95,6,83,73,54,85,1,79,88,92,67,26,82,80,79,42,19,37,81,94,75,24,46,55,53,35,10,87,24,77,21,68,24,22,29,95,3,100,28,47,35}

83

Returns: 91.28
{93,16,79,80,74,1,86,97,21,95,67,95,73,29,60,7,16,53,62,15,22}

96

Returns: 95.25999999999999
{53,43,68,0,84,48,10,85,15,45,25,83,21,1,76,9,27,31,82,66,94,75,20,86,73,51,32}

94

Returns: 92.59
{23,75,93,37,10,20,80,75,16,2,95,79,76,64,0,62,46,45,19,76,39,38,66,29,23,79,40,82,0,14,97,38,9,5,69,45,62,93,77,13,12,37,25,63,81,33,33,10}

92

Returns: 91.32000000000001
{82,41,17,55,88,52,5,77,60,18,75,21,76}

51

Returns: 71.095
{39,25,82,6,89,80,85,20,65,58,80,1,94,14,62,64,30,32,74,98,5,3,99,87,25,99,8,44,34,84,19,65,22,64,35,70,55,58,67,19,26,43,81,66}

61

Returns: 82.72999999999999
{32,66,22,21,69,58,66}

3

Returns: 67.21499999999999
{16,69,21,32,24,91,6,88,57,35,68,15,10,81,24,95,97,57,2,73,62,37,97,10,84,92,82,73,92,69,55}

83

Returns: 93.42999999999999
{3,19,78,48,44,94,49,7,52,20,4}

72

Returns: 80.69999999999999
{100,84,50,57,14,0,23,54,82,5,68,95,89,41,39,19,89,3,57,33,99,62,91,61,59,26,32,14,89,8,17,90,69,19,16}

47

Returns: 86.255
{23,13,72,59,15,80,11,60,58,41,22,100,99,68,26,34,56}

47

Returns: 91.05
{34,65,24,25,97,15,9,24,34,10,10,100,24,36,56}

53

Returns: 60.99
{87,19,14,8,18,11,41,100,59,54,15,13,97,42}

88

Returns: 94.0
{97,15,52,80,69,59,99,78,39,29,38,71,33,33,30,77,9,51,53,80,70,40,24,68,58,82,40,39,91,87,20,31,58,48,15,16,64,89,18,29,62,81,19,93,62,88,92,93}

94

Returns: 97.16999999999999
{87,71,86,3,94,13,49,56,95,39,69,68,34,4,19,16,44,67,24,28,45,8,68,36}

98

Returns: 94.05
{69,35,45,19,12,74,70,21,67,7,13,40,33,46,47,54,47,46,85,34,68,67,98,94,98,50,47,73,53,8,88,3,93,50,81,89,69,13}

88

Returns: 95.89999999999999
{49,78,47,86,11,32,74,39}

36

Returns: 69.4
{13,97,80,54,20,41,70}

56

Returns: 78.02000000000001
{26,43,31,16,87,30,10,48,50,42,45,23,11,57,83,18,48,49,33,49,76,59,83,48,73,82,100,34,53,70,11,59,20,41,34,27,78,73}

24

Returns: 85.41999999999999
{29,31,9,80,24,36,7,6,49,71,32,77,0,77,14}

45

Returns: 55.1
{43,51,66,14,78,81,14,87,80,42,19,42,98}

2

Returns: 82.6
{6,66,99,56,72,59,83,64,71,51,10,2,80,50,18,63,95,98,90,9}

8

Returns: 92.94000000000001
{1,48,17,42,3,52,57,47,56,6,89,37,59,82,88,52,56,99,60,20,26,49,31,91,50,30,48,8,82,66,92,11,89,13,12,57,5,52,72}

59

Returns: 82.19
{26,94,12,32,85,74,53,62,78,39,34,8,44,5,8,55,19,28,46,57,44,86,85,83,63,62,14,100,97,3,15}

69

Returns: 86.205
{59,92,38,55,5,38,52,71,39,74,63,26,61,11}

65

Returns: 76.775
{5,26,57,17,86,30,74,36,47,92,35,84,86,94,21,23,40,48,79,50,53,26}

23

Returns: 88.31
{77,44,50,98,86,2,28,82,23,26,59,66,41,84,52,100,99,16,70,64,61,23,8,77,13,6,67,32,89,44,45,64}

54

Returns: 88.72999999999999
{68,11,9,40,26,30,90,98,8,37,43,53,10,7,25,18,25,5,57,46,97,83,62,47,22,73,23,61,19,73,72,64,95,42,61}

21

Returns: 80.235
{38,64,11,45,84,12,10,59,59,83,75,52,87,91,72,41,82,46,44,33,63,54,98,21,26}

27

Returns: 82.60499999999999
{91,72,52,55,82}

22

Returns: 80.08
{28,89,80,79,40,50,80,34,96,91,96,40,82,27,26,87,74,9,92,77,29,70,20,47,51,82,47,49,32,97,0,99,12,28,37,58}

96

Returns: 95.27999999999999
{83,60,80,51,25,91,5,70,41,28,4,45,79,70}

16

Returns: 79.24
{84,69,68,1,65,7,55,86,62,89,61,30,61,95,99,8,67,51,18,68,91,7,59,3,97,76,3,25,26,70,27,56,87,46,88,25,46,62,23,28,55}

56

Returns: 88.4
{15,91,44,9,24,16,85,59,36,58,26,68,62,46,55,5,47,28}

39

Returns: 59.915000000000006
{73,86,100,26,49,16,5,33,87,84,58,18,100,90,47,100,52,17,77,43,40,13,25,0,83,73}

56

Returns: 86.22
{2,17,39,28,66,23,81,77,7,9,60,20,0,12,29,27,64,73,43}

25

Returns: 60.875
{12,45,14,68,98,37,17,62,49,42,46,49,0,29,86,83,15,33,49,2}

26

Returns: 64.33
{31,95,30,8,28,28}

29

Returns: 52.655
{52,96,3,89,7,32,68,68,94,100,86,44,11,96,83,55,71,26,90,94,42,31,72,41,54,70,17,1,26,80,2,79,84}

35

Returns: 93.5
{97,16,28,81,31,42,96,26,97}

45

Returns: 77.475
{46,0,83,47,78,45}

62

Returns: 65.84
{19,87,28,57,22,44,12,13,87,47,26,34,17}

76

Returns: 73.32000000000001
{72,9,30,75,10,13,68,29,23,65,52,72,10,23,51,44,47,2,80}

92

Returns: 76.56
{23,80,99,63,53,9,90,11,16,85,11,64,51,63,100,6,47,34,45,43,37,21,56,73,100,92,1,2,53,63,36,29,28,60,13,42,81,54,73,100,45,14,79,38,98,0,76,5}

86

Returns: 97.55
{85,41,24,89,38,60,52,56,20,0,36,75,37,73,74,79,63,90,0,14,39,78}

22

Returns: 79.77
{84,14,2,38,20,18,29,92,23,32,39,95,60,45,28,6,95,68,53,27,22,0,55}

72

Returns: 82.25999999999999
{69,7,76,22,41,21,62,82,61,43,31,32,86,38,33,0,68,14,57,75,47,1,16,17,87,85,43,87,41,80,61,28,48,17,53,36,17,76,79}

79

Returns: 80.80000000000001
{91,0,19,22,85,55,75,82,81,0,88,13,48}

32

Returns: 79.28
{90,63,30,54,97,2,19}

75

Returns: 79.75
{98,16,67,77,18,84,70,31,94,97,89,86,58,18,95,16,43,14,32,11,0,78,15,65,40,39,100,12,73,98,27,57,22,62,21,51,68,85,10,27,96,68,85,97,90,4,66,22}

59

Returns: 94.745
{22,7,7,14,74,5,64,59,53,7}

60

Returns: 58.8
{99,90,90,88,93,14}

86

Returns: 92.42
{1,8,17,48,10,18}

10

Returns: 30.7
{31,61,5,9,86,29,30,5,19,15,15,81,29,20,76,94,0,16,2,87,69,61,49,14,95}

76

Returns: 80.56
{26,17,88,10,71,49,76,14,65,72,34,89,53}

66

Returns: 73.53
{13,21,21,89}

15

Returns: 49.9
{97,69,15,38,37,71,94,71,72,85,60,17,56,17,38,99}

99

Returns: 98.685
{21,42,72,82,62,90,21,56,0,10,80,10,63,78,80,46,63,63,49,10,25,34,90,99,19}

95

Returns: 96.775
{0, 100, 100, 100 }

50

Returns: 100.0
{10, 10, 10 }

50

Returns: 10.0
{14, 13, 14, 5 }

30

Returns: 13.7
{100, 100, 50, 0, 50, 50 }

0

Returns: 75.0
{4, 1, 3, 5 }

40

Returns: 4.1
{10, 40, 50 }

81

Returns: 45.25
{50, 40, 10, 40 }

80

Returns: 48.0
{16, 99, 96, 26, 71, 9, 89, 43, 11, 41, 58, 84, 27, 8, 17, 54, 26, 36, 87 }

66

Returns: 84.61
{12, 11, 5, 7, 9, 23, 11, 15 }

19

Returns: 17.48

Statistics

Problem Statement for "DartThrow"

Problem Statement

Definition

Notes

Constraints

Examples