ZOJ Problem Set - 2929
In 2028 year, China Football Team advanced into the final of the World Cup. What an exciting news! But the Manager of China is ZhuGuanghu's grandson, being conservative is their only style. As almost excepted, the final is boring, they don't even score one goal in 120 minutes! Now the match comes into penalty kick off. Here comes the official law of the penalty kick off:
1. The referee chooses the goal at which the kicks will be taken
2. The referee tosses a coin and the team whose captain wins the toss decides whether to take the first or the second kick
3. The referee keeps a record of the kicks being taken
4. Subject to the conditions explained below, both teams take five kicks
5. The kicks are taken alternately by the teams
6. If, before both teams have taken five kicks, one has scored more goals than the other could score, even if it were to complete its five kicks, no more kicks are taken
7. If, after both teams have taken five kicks, both have scored the same number of goals, or have not scored any goals, kicks continue to be taken until one team has scored a goal more than the other from the same number of kicks
8. No player is allowed to take a second kick until all other players in his team have taken a kick
You, assistant coach of China, have been working on the math particularly on probability for many years. You know everyone's success rate when taking a penalty in your team, and you also know the opponent's success rate (assume they have the same success rate). Now you will determine the order of taking the penalty to maximize the probability to win the World Cup.
There are several test cases in the input. Each case contains 12 integers, from 0 to 100. The first 11 integers is the success rate of your teammates. The last integer is the success rate of the opponent.
For each case, compute as accurately as possible the max possibility of your team to win the final, then output a single line containing percentage round to 0.0001
10 10 10 10 10 10 10 10 10 10 10 10
Author: YANG, Kete
Source: ZOJ Monthly, February 2008