# 7 This is a C++ question:

DartThrow

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

Method signature:

double bestScore(int payout[], int size, int prob);

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

0)

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

1)

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

2)

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

3)

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

4)

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

66

Returns: 84.61

Pseudo-code

The pseudo code for function :

double bestScore(int payout[], int size, int prob);

is shown below.

set max to 0

set prob1 to prob/100

set prob2 to (1-prob1)/2.0 //probability hitting neighboring targets

for i = 0 to size 1

set pay1 to payout at i^th target times prob1

set pay2 to payout on the left of the i^th target times prob2

set pay3 to payout on the right of the i^th target times prob2

if the sum of pay1, pay2 and pay3 is greater than max

set max to (pay1 + pay2 + pay3)

end for

return max

Sample Output

The driver (main( ) function) and testing function (verifyResult(double, double)) are given as an attachment to this assignment. In addition to implement the bestScore() function, you also need to complete testing code for test cases 4 and 5 in the main() function.