Conquest

Problem Statement

You are playing a board game and have almost won. You have one large group of armies in one territory poised to eliminate your opponent, whose armies are scattered across three territories. To eliminate your opponent, you must reduce the number of armies your opponent controls to zero through a series of attacks. During an attack, your remaining armies attack one of your opponent's three territories from your starting territory. You may continue to make attacks as long as you have more than 1 army in your starting territory. During each attack, you may lose some armies, and your opponent may also lose some armies. If, through a series of attacks, you are able to cause your opponent to lose all of his armies in one of his territories, you must move exactly one army into that territory from your starting territory. You may then continue to attack your opponent's other territories from your starting territory. The goal, of course, is to defeat all the armies in all three of your opponent's territories, and move a single army into each of them, while leaving at least one behind in your starting territory. For example, let's say that you had 10 armies and attacked a territory with only 3 armies. As you will see below, one possible outcome for this attack is that both you and your opponent lose a single army. Then, you have 9 armies left, and your opponent has 2 armies left in that territory. You may then attack him again, and a possible outcome is that your opponent loses both of his remaining armies. In this case, you must move one of your 9 armies into that territory, leaving you with 8. You may then move on to attacking your opponent's other territories. The outcomes of the attacks are somewhat random, and there are different probabilities depending on the number of armies in your starting territory, and in the opponent's territory being attacked. The following table shows the probabilities of each of the potential outcomes. The outcome column contains two numbers. The first is the number of armies that you lose during the attack, and the second is the number of armies that your opponent loses during the attack. The probability column shows the probability of the given outcome for the specified numbers of armies in the two territories. For example, if you had more than 3 armies on your starting territory and attacked a territory that had only 1 army, you would have a 855 / 1296 probability of defeating that 1 army, and a 441 / 1296 probability of losing 1 of your armies. Any outcomes not listed have a probability of 0.

 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

0)


4
{1, 1, 1}
Returns: 0.15907653892318244

1)


10
{2, 2, 10}
Returns: 0.13552235780217273

2)


30
{5, 5, 5}
Returns: 0.9857787020110442