Welcome to ZOJ
63 - ZOJ Monthly, February 2008 - 1006
Legendary Pokemon II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Pokemon is a very popular video game series, and has been merchandised into anime, comic, trading cards, toys, books, and other media.

Have you solved the problem Legendary Pokemon?
It's been a while, and your Pokemons grew stronger and stronger after that. One day another legendary Pokemon comes to you, although it cannot speak you immediately know what it wants in your mind (anyway, it is legendary). It has heard that you're a great Pokemon trainer and wants to test whether you have the ability to become its master. The test is very simple: just win it in the duel with one of your Pokemons. But it will leave once you lose. Of course you accept immediately, since you've heard that this legendary Pokemon is very powerful and cannot been captured in normal way.

The rules of the duel are different from normal Pokemon battles. Only normal attack moves are allowed, i.e. no status problem will be resulted, and you cannot use any items or change your Pokemon in the middle of the duel. And the legendary Pokemon has some kind of special power that makes no one can either dodge the opponent's attack or make critical hits, the ability of your Pokemon will be canceled, and the power points used will be recovered immediately (so a move can be used infinite times during the duel). So this is really a duel and you can win only if your Pokemon is stronger than it. Now with all statistics of your own Pokemons and the legendary Pokemon given, you would like to know which Pokemon you should use so that you are most likely to win. Assume the legendary Pokemon choose his move randomly in each turn.

Each Pokemon has a type or two and several stats: Level, HP (Hit Point), Attack, Defense, Special Attack, Special Defense and Speed. When a Pokemon's HP reaches zero it will faint (and lose the duel). Attack (Special Attack) determines the power of a Pokemon's physical (special) attacks. Defense (Special Defense) determines the Pokemon's defensive power against physical (special) attacks. The Pokemon with the larger Speed value will always move first in each turn. (And here when your Pokemon's speed equals to the legendary Pokemon's, the latter moves first)  A Pokemon can have at most four moves, but special moves such as those that will cause status problems or restore health are forbidden in this duel. And since the Power Point can be ignored here, each move can be described with its type and power alone. The damage of each move is calculated by this formula:

Damage = ((((2 * Level / 5 + 2) * AttackStat * AttackPower / DefenseStat) / 50) + 2) * STAB * Weakness/Resistance * RandomNumber / 100

Where Level is the attacker's current level, AttackStat is the attacker's Attack/Special Attack stat (according to the move type, discuss later), DefenseStat is the opponent's Defense/Special Defense, AttackPower is the power of the move, STAB is the same type attack bonus (1.5 if the move coordinates with the attacker's own type, 1.0 otherwise), Weakness/Resistance depends on if the move is super-effective or otherwise to the opponent (discuss later), and RandomNumber is simply a random number from 85 to 100, but will always be 100 in the duel due to the legendary Pokemon's special power, too. The final result of damage will be rounded down to an integer value.

There're 17 Pokemon types and 18 move types (the first 17 types are the same with Pokemon types, but neither your Pokemons nor the legendary Pokemon know moves with type "???"), in which Normal, Fighting, Poison, Ground, Flying, Bug, Rock, Ghost, Steel are physical attack types, while Fire, Water, Grass, Electric, Ice, Psychic, Dragon, Dark are special attack types. When using a move with physical attack types, the attacker's Attack stat and the opponent's Defense stat are used in the above damage calculation formula, and when using a move with special attack types the other two stats are used. (It is said that in the fourth generation Pokemon games each move is individually classified as Physical, Special, or Status, but I haven't played it yet. Could you lend me an NDS so that I can make a new problem after playing it?) Here's the table specifying the effectivenesses between move types and the opponent's own types:

  Normal Fire Water Grass Electric Ice Fighting Poison Ground Flying Psychic Bug Rock Ghost Dragon Dark Steel
Normal                         - X     -
Fire   - - O   O           O -   -   O
Water   O - -         O       O   -    
Grass   - O -       - O -   - O   -   -
Electric     O - -       X O         -    
Ice   - - O   -     O O         O   -
Fighting O         O   -   - - - O X   O O
Poison       O       - -       - -     X
Ground   O   - O     O   X   - O       O
Flying       O -   O         O -       -
Psychic             O O     -         X -
Bug   -   O     - -   - O     -   O -
Rock   O       O -   - O   O         -
Ghost X                   O     O   - -
Dragon                             O   -
Dark             -       O     O   - -
Steel   - -   - O             O       -

Where the types on the left are the types of the move, and those at the top are the types of the opponent. Blank means normal damage (Weakness/Resistance = 1.0 in the damage calculation formula), 'O' means super effective (Weakness/Resistance = 2.0), '-' means not very effective (Weakness/Resistance = 0.5), and 'X' means no effect at all (Weakness/Resistance = 0.0). Damage to Pokemon with two types is calculated by considering how each of its types reacts to the given attack and multiplying the results together.


Each test case begins with an integer N (1 <= N <= 6), the number of your Pokemons. Then following N descriptions of your Pokemons and another description of the legendary Pokemon. Each description of Pokemon starts with a line containing the name, type(s) and level of the Pokemon. The second line contains six integers specifying the Pokemon's six stats: HP, Attack, Defense, Special Attack, Special Defense, and Speed. Then a line with a single integer M (M <= 4), the number of the Pokemon's normal attack moves, then M lines each specifies a move with its type and power followed. The Pokemon name contains at most 10 letters. All types are in the above 17's and two types of a Pokemon are separated by '/'. Pokemon levels are between 1 and 100, inclusive. Pokemon's HP is at most 714 and other stats are at most 669 (What a fantastic Pokemon!). The power of a move can range from 10 to 250.

There's an empty line between every two cases, processing to the end of file.


For each test case, print the name of the Pokemon you should use in the duel in a single line. If two Pokemon are equally likely to win, print the first one appear in the input. If it is almost impossible for you to win the legendary Pokemon (when you can only win with a probability less than 0.1%), just print "Impossible".

Sample Input

Primeape Fighting 58
161 149 98 84 89 176
Fighting 75
Rock 75
Ground 100
Fighting 100
Charizard Fire/Flying 59
184 131 123 147 124 152
Normal 85
Flying 70
Fire 95
Fire 150
Alakazam Psychic 59
155 98 90 184 112 165
Psychic 65
Psychic 90
Articuno Ice/Flying 58
186 117 139 120 185 116
Flying 70
Ice 120
Ice 95
Fighting 20
Mewtwo Psychic 70
239 175 147 238 159 169
Normal 60
Psychic 90

Sample Output


Author: XIAO, Dong

Submit    Status