Yet Another Contest 8 P4 - Fluke 2

View as PDF

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem types

Now that Nils has proven that his moments of strategic brilliance are not flukes, Josh has been challenged to do the same. To do so, they will play the following game.

The game will be played on an by grid of initially white cells. The rows are numbered from to , while the columns are numbered from to . Denote the cell in the -th row and the -th column as cell .

Nils and Josh will take alternating turns. In each turn, the player must select a cell, and then toggle its colour between black and white. Furthermore, this cell cannot be the same as the cell last chosen by the other player. The player who goes first will win if there are three consecutive black cells (adjacent cells in the same row or column; diagonals do not count) at any point during the first total turns (that is, each player has had turns each). Otherwise, the player who goes second will win.

In order to prove that his victories are a result of his strategic brilliance rather than just flukes, Josh must win consecutive games. To make things a little fairer, Josh will be allowed to decide which player takes the first turn. Can you help Josh win all games?

It can be proven that if it is possible for the first player to win within the first total turns, there is a strategy which allows them to win within the first total turns. Thus, if Josh chooses to go first, he must win within total turns for full points.

Scoring

Let be the number of turns in any particular game.

If you choose for Josh to go second, then you will receive of the points if Josh wins, and otherwise.

If you choose for Josh to go first, then you will receive of the points of the points if Josh wins, and otherwise, where is determined by the following table:

The score for a testcase is the minimum score amongst any of its games. The score for a subtask is the minimum score amongst any testcase in the subtask.

Interaction

This is an interactive problem, where the interactor will play the role of Nils. Since the moves that the interactor can make depends on your moves, the interactor will be adaptive.

At first, you should read in three space-separated integers on a single line, denoting the values of , and respectively. Note that the values of and are the same for all games.

Each of the following interactions represents a single game.

At the beginning of each game, on a single line, you should output either 1 or 2. Outputting 1 indicates that Josh will take the first turn, whilst outputting 2 indicates that Nils will take the first turn. If you do not do so, the interactor will output I on a single line, and you will be responsible for terminating your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict.

Then, the game will begin. When it is Josh's turn, on a single line, output your selected cell in the format r c, representing that Josh will toggle the cell . You should then read in a character on a new line, which will be one of W, L, C, or I. These denote that Josh has won, Josh has lost, the game should continue, or an invalid turn has occurred (such as an invalid output format or the same cell being toggled twice in a row) respectively. Upon reading L or I, you should terminate your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict. Upon reading W, if you have not yet played all games, then you should begin the next interaction for the following game. Upon reading C, you should continue the current game.

When it is Nils's turn, you should read in a line of input in the format r c, representing that Nils will toggle the cell . Then, you should read in a character on a new line, which will be one of W, L, or C. These have the same meaning as above, so you should terminate your program upon reading L, begin the next game upon reading W, and continue the current game upon reading C.

If you manage to win all games, then you will receive an Accepted verdict for that test case.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction 1

>>> denotes your output. Do not print this out.

1 4 1
>>> 1
>>> 1 1
C
1 4
C
>>> 1 2
C
1 1
C
>>> 1 3
W

Explanation for Sample Interaction 1

Here, the game is played on a by grid, and Josh only has to win a single game. Josh chooses to go first.

Josh begins by toggling the cell to black, and Nils follows by toggling the cell to black. Josh then toggles the cell to black, and Nils responds by toggling the cell back to white. Josh then wins by toggling the cell to black.

Sample Interaction 2

1 2 1
>>> 2
1 1
C
>>> 1 2
C
1 1
C
>>> 1 2
...
1 1
C
>>> 1 2
W

Explanation for Sample Interaction 2

Here, the game is played on a by grid, and Josh only has to win a single game. Josh chooses to go second.

Note that once Nils makes the first move of toggling the cell to black, Josh can only ever toggle the cell , and Nils can only ever toggle the cell . Note that ... does not actually appear in the output, and represents repeating turns that have been omitted for concision. Once both player have had turns each, total turns have elapsed, and Josh wins.