33368번 - "Memo" Game With a Hint 다국어투 스텝

문제

"Memo", or "Memory", is a game with cards. In this problem, the game uses 25 pictures, and each picture is printed on exactly two rectangular cards: so, there are 50 cards in total. Initially, all cards are randomly shuffled and dealt face down, so that the pictures are not visible. The cards occupy positions which are numbered by integers from 1ドル$ to 50ドル$.

Vasilisa trains her memory by playing "Memo". She makes moves in the game. Each move consists of two actions. For the first action, Vasilisa picks a position with a card face down and turns it face up. For the second action, she picks another such position and also turns the card face up. If the two pictures on these cards are the same, they remain face up. Otherwise, they are both turned face down again, and Vasilisa gets a miss.

Vasilisa wins when all cards are face up. Her task is to win and get as little misses as possible.

Vasilisa has trained her memory well and devised a good strategy, and now, in each game, she makes approximately 14.83 misses on average. To make things more interesting, she called her sister Sasha to play together.

The backs of the cards are all the same, but they look differently when the card is rotated 180 degrees without turning it face up. Now Sasha and Vasilisa play as follows. Firstly, Sasha shuffles the cards and deals them face up. Then she turns them face down, but for each card, she can either rotate it 180 degrees, or not rotate. Finally, Vasilisa initially sees not only 50 cards with the same backs, but for each card, she sees whether it is rotated 180 degrees.

Devise a way for Sasha and Vasilisa to agree how the cards are rotated, so that Vasilisa can win with no more than 13.5 misses on average.

인터랙션 프로토콜

This is an interactive problem. Additionally, in this problem, your solution will be run twice on each test. Each line of input is terminated by an end-of-line character.

첫 번째 실행

During the first run, the solution acts for Sasha. The first line contains the word "prepare". The second line contains an integer $t,ドル the number of test cases (1ドル \le t \le 100$). Each of the next $t$ lines describes the initial positions of the cards: 50ドル$ uppercase English letters "A"--"Y" without spaces. Equal pictures correspond to equal letters. Each letter occurs in the string exactly twice. It is guaranteed that, except the examples, all strings in each test are picked in advance, randomly and uniformly.

For each test case, print a line with 50ドル$ binary digits: each position should contain a one if the card is rotated 180 degrees, and a zero otherwise.

Technically, this run is interactive, but all the input is given at once.

두 번째 실행

During the second run, the solution acts for Vasilisa. The first line contains the word "play". The second line contains an integer $t,ドル the number of test cases which is the same as during the first run.

The jury program counts the total number of misses for all test cases. This number has to be at most 1350ドル$: for example, if there are exactly 100ドル$ test cases (and not less), it means that one test case can have at most 13ドル.5$ misses on average.

Each test case starts by a line containing 50ドル$ binary digits, which is the line that the solution printed during the first run. After that, the solution has to interactively print actions until all cards are face up. To turn the card at position $p$ (an integer from 1ドル$ to 50ドル$), print a line containing the number $p$. In response, the solution gets a line with two characters. This line is "##" (two hashes) if the move is invalid: for example, the position $p$ is invalid, or the card at that position is already face up, or this move exceeds the maximum possible number of misses. In this case, solution has to terminate. Otherwise, the first character is an uppercase English letter "A"--"Y" at position $p$ corresponding to the picture. The second character can be one of the following:

• "." (dot) if it is the first action of a move;
• "-" (minus) if it is the second action of a move, and the pictures are different;
• "+" (plus) if it is the second action of a move, the pictures are the same, but Vasilisa did not yet win;
• "!" (exclamation mark) if it is the second action of a move, the pictures are the same, and this is the winning action.

After a response with an exclamation mark, the next line of input belongs to the next test case, or the interaction is terminated if there are no more test cases.

Do not forget to end the line and flush the output buffer immediately after printing each action: otherwise you will likely get the "Idleness Limit Exceeded" outcome.

When the solution gets the line "##", it can terminate immediately, in order to get the "Wrong Answer" outcome and not any other.

예제

For each test, the input during the second run depends on the solution's output during the first run.

Below we show two runs of a certain solution on the first test. Empty lines are added only for readers' convenience: there will be no empty lines during a real run. To conserve space, almost all moves are replaced with "(...)".

입력

출력

제한

힌트