Legendary Pokemon

Time Limit: Java: 10000 ms / Others: 10000 ms

Memory Limit: Java: 32768 KB / Others: 32768 KB

Description

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
The move attacks the opponent. As a result, the HP(life value) of the opponent will decrease.

2. Status change
The move itself does not cause any damage, but you can make your opponent sleepy or confused. if your opponent's sleepy, he cannot make any move, if your opponent is confused, he will attack himself sometimes. These will be effective within 3 rounds (that is, the victim will be in the wrong status 3 times, and during that time, any Status-change type moves will not take effect).

3. Poison attack
This move attacks the opponent and makes him poisoned. If a pokemon is poisoned, it will lose an additional poison value units of HP BEFORE he can make a move. The effect lasts for 3 rounds(that is, the victim will be hurt by poison 3 times, during that time, any poison-type attack will still do damage, but will take no OTHER effect)

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)
2.Great Ball - Catches pokemon more easily than a pokeball. (BasicProbability=0.1)
3.Ultra Ball - Capture pokemon more easily than with the great ball. (BasicProbability=0.15)
4.Level Ball - If your pokemon is higher levels than the target pokemon then BasicProbability=0.18, otherwise, it is the same as a Great Ball.
5.Love Ball - Captures pokemon of an opposite gender than yours easily (BasicProbability=0.20), otherwise, BasicProbability=0.0

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.
CriticalLifeBonus=0.1 if and only if 0 < the target's HP <=50.
PoisonedBonus=0.1 if and only if the target is poisoned.
StatusBonus=0.05 if and only if the target is in the wrong status(sleepy or confused).

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 or poisoned)
2. If he decided to continue the battle, he check if his HP. If it's not greater than 150, he uses a Hyper Potion(even if he's sleepy or confused) if he has any, otherwise, he uses his only normal attack move - Cross Chop. Its Accuracy is 30%, but the damage value is 300.

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.

Input

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[5]=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.

Output

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.

Sample Input

30 1 500
10 100 100 100 100
0 10
0 0 0 0 1
2
1 100 80
3 300 50 60
0 0 0

Sample Output

0.2340
Note
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)

None

Source

OIBH Online Programming Contest #1