409392: GYM103496 E Experiment - Pokémon Edition!

E. Experiment - Pokémon Edition!time limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

Alola! Alice landed an internship with the world-renowned Professor Kukui, the foremost expert on Pokémon moves. She just returned from an eight-week stay in Alola, and is excited to share her experience with you.

There are eighteen known Pokémon types, Normal, Fighting, Flying, Poison, Ground, Rock, Bug, Ghost, Steel, Fire, Water, Grass, Electric, Psychic, Ice, Dragon, Dark, Fairy. For an explanation of how type matchups work in Pokémon, read http://bit.ly/Abakoda2021TypeMatchups.

When we catch a Pokémon, we take it for granted that the Pokédex automatically tells us what type it is. But how did scientists first figure out that Raichu was an Electric type, whereas its Alolan regional variation is an Electric/Psychic type?

Professor Kukui assigned Alice the following problem. Alice is given a mystery Pokémon whose type is unknown. She can choose a type, and then attack the mystery Pokémon with a move of that type. After each attack, Professor Kukui's computer will tell her what that move's type effectiveness was against the mystery Pokémon ($$$4\times$$$, $$$2\times$$$, $$$1\times$$$, $$$0.5\times$$$, $$$0.25\times$$$, or $$$0\times$$$). You can assume that no other game mechanics are in play other than the type effectiveness system.

Since this method involves attacking and hurting the target Pokémon, Professor Kukui tasked Alice with developing a system that can figure out the mystery Pokémon's type in as few moves as possible. Alice is quite proud of her program, and she was able to prove that you should always be able to deduce the mystery type in five moves or less. Now, Alice is challenging you to do the same!

Interaction

The judge first outputs a single line containing a single integer $$$T$$$, the number of test cases.

At the beginning of each test case, the judge secretly generates one or two Pokémon types. If there are two types, they are guaranteed to be different (so no Fire/Fire-type Pokémon). We may give type combinations that are still unused in the actual Pokémon games (such as Ghost/Normal, as of the eighth generation).

You have two types of commands available to you.

If you wish to attack the mystery Pokémon, output a line containing ATTACK, a space, and then one of Normal, Fighting, Flying, Poison, Ground, Rock, Bug, Ghost, Steel, Fire, Water, Grass, Electric, Psychic, Ice, Dragon, Dark, Fairy. This is case-sensitive. The judge will then respond with a line containing the type effectiveness of a move of that type attacking the mystery Pokémon, which will be a line containing one of 4, 2, 1, 0.5, 0.25, or 0. If your query is invalid, the judge will respond with -1 and provide no further input; in this case, your program must exit immediately.

If you are ready to answer, output a line containing ANSWER, a space, and then the type(s) of the mystery Pokémon. If it has a single type, simply output that type (again, case-sensitive). If it has two types, output both of them in alphabetical order, separated by a forward slash /.

The judge will then respond with a single line containing NO if you were incorrect, or YES if you were correct. If your program receives a YES, then simply proceed with the next test case.

Technical Details

If you made an invalid command, said an invalid type, or received a NO, you will get $$$0$$$ points, and no further input (from the rest of the test cases) will be given from the judge. In such a case, your program should terminate immediately to prevent an Idleness Limit Exceeded verdict.

After printing a command or printing the answer, do not forget to flush the output. Otherwise, you will get an Idleness Limit Exceeded verdict. To manually flush the output, use:

• cout.flush() in C++
• sys.stdout.flush() in Python (don't forget to import sys)
• See the documentation for other languages.

Scoring

There will be at most $$$980$$$ test cases in a single interaction.

Let $$$Q$$$ be the maximum number of times you used the ATTACK command in any of the test cases. Then, if you answered all the test cases correctly, scoring is as follows. $$$$$$ \begin{align*} \begin{cases} 0, & 18 < Q \\ 48 + 4 \times (18 - Q), & 5 < Q \leq 18 \\ 100, & Q \leq 5. \end{cases} \end{align*} $$$$$$ In other words, you get a baseline of $$$48$$$ points for answering the question correctly in $$$18$$$ commands or less, then the closer you are to $$$Q=5$$$, the more points you get (in increments of $$$4$$$).

Note

Let's look at some sample interactions.

Contestant              Judge
                        3
ATTACK Dragon
                        2
ATTACK Electric
                        0
ANSWER Dragon/Ground
                        YES
ATTACK Ground
                        4
ATTACK Normal
                        0.25
ANSWER Rock/Steel
                        YES       
ATTACK Ice
                        0.5
ATTACK Steel
                        2
ATTACK Ghost
                        1
ATTACK Psychic
                        1
ATTACK Rock
                        2
ANSWER Ice
                        YES

First, the judge tells us that this interaction has three test cases.

In the first test case,

• Alice tries attacking with a Dragon-type move. It was super effective.
• Alice tries attacking with an Electric-type move. It was not effective.
• Alice realizes that Dragon is only super effective against Dragon, and that Electric is only not effective against Ground. She answers that the mystery Pokémon is Dragon/Ground, and the judge tells her she is correct.

In the second test case,

• Alice tries attacking with a Ground-type move. It dealt $$$4 \times$$$ damage, so Alice concludes that the mystery Pokémon has two types, both weak to Ground.
• Alice tries attacking with a Normal-type move. It dealt $$$0.25 \times$$$ damage, so Alice concludes that the mystery Pokémon has two types, both resisting Normal.
• Alice realizes that Normal is only not very effective against Rock and Steel, so she has enough information to conclude that the mystery Pokémon is Rock/Steel.

Note that the second command by itself provided enough information to deduce the mystery type, and that same conclusion could have been made without the first command. But Alice can only apply that reasoning in retrospect.

In the third test case, we can show that pure Ice is the only type consistent with the type effectiveness answers of Alice's five ATTACK commands.

For this interaction, Alice took $$$2$$$ attacks in the first test case, $$$2$$$ attacks in the second test case, and $$$5$$$ attacks in the third test case. So, $$$Q=5$$$, and she gets a full 100 points.

Contestant              Judge
                        1
ATTACK Normal
                        0.5
ATTACK Psychic
                        1
ANSWER Rock
                        NO

In this interaction (which only has $$$1$$$ test case),

• Normal-type attacks are not very effective.
• Psychic-type attacks deal regular damage.
• Alice (hastily) concludes that the mystery Pokémon is Rock-type, since that is consistent with the judge's responses. However, the judge tells her she is incorrect! The mystery Pokémon in this case was Fighting/Steel, and there are still many other type-combinations consistent with the answers of the judge.

Alice's answer was wrong, so she gets $$$0$$$ points.