Conquest

Problem Statement

``` attacking | defending |         |
armies    | armies    | outcome | probability
-----------+-----------+---------+------------
over 3    | over 1    | 2 - 0   | 2275 / 7776
over 3    | over 1    | 1 - 1   | 2611 / 7776
over 3    | over 1    | 0 - 2   | 2890 / 7776
over 3    | 1         | 1 - 0   | 441 / 1296
over 3    | 1         | 0 - 1   | 855 / 1296
3         | over 1    | 2 - 0   | 581 / 1296
3         | over 1    | 1 - 1   | 420 / 1296
3         | over 1    | 0 - 2   | 295 / 1296
3         | 1         | 1 - 0   | 91 / 216
3         | 1         | 0 - 1   | 125 / 216
2         | over 1    | 1 - 0   | 161 / 216
2         | over 1    | 0 - 1   | 55 / 216
2         | 1         | 1 - 0   | 21 / 36
2         | 1         | 0 - 1   | 15 / 36
```

You are given an int, armies, indicating the number of armies you have to start with. You are also given a vector , opponent, with exactly three elements, containing the number of armies in your opponent's territories.

You are to return a double indicating the probability that you successfully defeat all of your opponent's armies, assuming that you always make the best decision as to which territory to attack each time.

Definition

Class: Conquest
Method: bestChance
Parameters: int, vector
Returns: double
Method signature: double bestChance(int armies, vector opponent)
(be sure your method is public)

Notes

• You may attack any one of your opponents territories that has armies remaining on it. You do not need to continue to attack a territory until your opponent's armies on that territory are eliminited. You could for example, attack territory 0, then territory 1, and then go back to territory 0.
• Your solution have have an error of less than 1E-9.

Constraints

• armies will be between 4 and 50, inclusive.
• opponent will contain exactly 3 elements.
• Each element of opponent will be between 1 and 20, inclusive.

Examples

```0)

4
{1, 1, 1}
Returns: 0.15907653892318244
```

You have 4 armies to start with and your opponent has 1 army in each of his three territories. Since you must move an army into each territory after defeating your opponent, your only hope is to not lose a single army in any of your attacks. First, you attack territory 0, and defeat that army without losing any of your own with a probability of 855 / 1296. You must move 1 army into that territory, so you then only have 3 armies to attack territory 1. You conquer this territory without loss with a probability of 125 / 216. Finally, you have only two armies left to attack territory 2, and you win with a probability of 15 / 36. From this, we find that the overall probability of conquering all three territories is 1603125 / 10077696, which is about 0.159.

```1)

10
{2, 2, 10}
Returns: 0.13552235780217273

2)

30
{5, 5, 5}
Returns: 0.9857787020110442
```

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)2003, TopCoder, Inc. All rights reserved.