ZOJ Problem Set - 1230
Do you know Pokemon? It's a kind of very lovely cute sprite. In the world of pokemon, people live with their favorite pokemons and train them with love. One night, you saw a strange yet powerful pokemon in a narrow dark cave. 'It must be the legendary pokemon. If only I could catch him!' You thought. Setting our your best pokemon, you decided to catch it - the legendary pokemon.
As a skilled pokemon trainer, you know that all you have to do is to battle with it and throw a magic BALL to it during the battle. If you're lucky enough, the pokemon will be caught in the BALL, and become yours. It sounds easy, but the balls can not always catch pokemons, especially fierce ones, so you must be careful and follow a perfect strategy.
The battle is divided into rounds. In each round, your pokemon makes a move first, then does the wild pokemon (you can choose not to do anything). Each round, a pokemon makes a move or uses an item to attack its opponent or heal itself. You may also use a BALL to catch it in a round.
A move may be used as many times as you like, but can only be of the following three types:
1. Normal Attack
2. Status change
3. Poison attack
The damage that the opponent will take after being attacked by a Normal Attack or Poison attack is called damage value of the move; the probability that the move hits the target is called accuracy of that move. If a pokemon is confused by a move, the probability that it CHOOSE to attack itself is called confusion value of that move.
There is only one type of item available - Hyper Potion. It recovers a pokemon 200 HP.
A BALL could be of the following types:
1.Poke Ball - Used for catching pokemon. (BasicProbability=0.05)
The probability that a BALL can catch a pokemon is computed this way:
P = BasicProbability + CriticalLifeBonus + PoisonedBonus + StatusBonus
CriticalLifeBonus=0.05 if and only if 50 < the target's HP <=100.
All Bonus values are set to zero by default.
Initially, Both pockemons' HP are full(HP values can never be greater than their maximal values) and are in good health(not sleepy, confused or poisoned). Then, the battle starts. When one of the pokemons's HP is 0 or below 0, the battle ends immediately and the legendary pokemon goes away(you failed). When you catch it, the battle also ends(congratulations!)
Since the pokemon is wild, it has not been trained mentally. So it follows a very simple strategy during the battle:
1. In the ith round, he may decide to run away. The probability he makes this
decision is run[i]%; (he never fails to escape even if he's sleepy, confused
It is well known that the legendary pokemon is at level 50 and is male. His initial HP is always 999, but people don't know how many Hyper Potions he has. People never saw him battle for 6 or more rounds, so you may assume this is also true for your battle.
The input will contain no more than 20 test cases. Each test case begins with a line containing three integers l,g and HP describing your pokemon. l is your pokemon's level(1<=l<=100), g(0<=g<=1) is its gender. 0=male, 1=female. HP is your initial(and maximal) HP value(1<=HP<=999). The second line contains 5 integers. The ith integer is the value of run[i], (i.e.run[i]% is the probability that the wild pokemon flee in his ith move.) It is guaranteed that 0<=run[i]<=run[i+1] for all 1<=i<=4, and that run=100. The next line contains two integers p1, p2(0<=p1,p2<=10). p1 is the number of Hyper Potions that you have, p2 is that of the wild pokemon's. The next line contains 5 integers b1,b2,b3,b4,b5(0<=b1,b2,b3,b4,b5<=5), the number of corresponding balls you have(i.e b1 for Poke Ball...). The next line contains a single integer k(0<=k<=4), the number of moves your pokemon masters. In the following k lines, each line begins with an integer t(1<=t<=3), representing the type of the move. If t=1, there are two integers following in the same line: damage value and accuracy*100; if t=2, there are two integers following in the same line: confusion value*100 and accuracy*100. Note that the move makes the opponent sleepy if and only if confusion value=0. If t=3, there are three integers following in the same line: damage value, poison value and accuracy*100. All the values defined in the three types will be between 0 and 999 (inclusive) while 0<=accuracy, confusion<=100. The test case containing l=g=HP=0 will terminate the input and should not be regarded as a test case.
For each test case, output a single line containing the probability that you catch the pokemon if you follows a perfect strategy. Print your answer with four decimal places.
30 1 500
You should follow this strategy: use move 2(poison attack) in round 1, then throw his ball in round 2.
if the first move hits, the probability is (1-10%)*(0.2+0.1)=0.27, otherwise, the probability=(1-10%)*0.2=0.18, so the total probability=60% * 0.27 + 40% * 0.18 = 0.2340
(note that in some cases, the strategy is much more complex and may be dynamic
- you may do different things in different conditions)
Source: OIBH Online Programming Contest #1