Finally, you are face to face with the leader of the alien robots! You have managed to distract it with its favorite word game, while your fellow Resistance members try to shut down the robots’ power supply.
The game uses the robot language, which is made up of 105 words: the set of all five-letter strings made up of uppercase English letters between A and J, inclusive. For example, AAAAA, FGHIJ, and BEIGE are among the valid words.
You know that these words have a rank order, with no ties, such that a higher-ranked word beats any lower-ranked word, with the one exception that the lowest-ranked word beats the highest-ranked word. Unfortunately, you do not know the rank order of the words in the robot language!
The game has the following rules:
Turn 0: You start by naming a word W0.
Turn 1: The robot names a word W1. If W1 beats W0, the robot scores a point.
This continues; on turn i, the active player is you if i is even, or the robot if i is odd. The active player names a word Wi and scores a point if Wi beats Wi-1. (If the two words are the same, no point is scored.) The score is not announced — in particular, you will not know whether each of your words has scored a point!
This continues for a total of 201 turns.
Notice that you get the last turn (naming W200), and that at the end of that turn, each player’s score is between 0 and 100, inclusive.
Thanks to some great work by the Resistance’s spies, you know the strategy that the robot will use for every turn of the game. It only cares about scoring 100 points, so on every turn, it will choose a word uniformly at random from all possible words that will score a point on that turn, and independently of all of its previous word choices. The robot knows the rank order of the language, so it has no trouble choosing words!
If you do not score at least N points, the robot will become bored and stop playing with you, so your plan (and the universe) will be doomed!
1 ≤ T ≤ 50.
Time limit: 40 seconds per test set. (10 seconds per test run.)
Memory limit: 1GB.
Wi is five characters long and consists only of characters in the set of uppercase letters ABCDEFGHIJ, for all odd i. (The robot plays valid words.)
Test set 1 (Visible)
N = 25.
Test set 2 (Visible)
N = 50.
using namespace std;