CF1503B 3-Coloring

This is an interactive problem. Alice and Bob are playing a game. There is $ n\times n $ grid, initially empty. We refer to the cell in row $ i $ and column $ j $ by $ (i, j) $ for $ 1\le i, j\le n $ . There is an infinite supply of tokens that come in $ 3 $ colors labelled $ 1 $ , $ 2 $ , and $ 3 $ . The game proceeds with turns as follows. Each turn begins with Alice naming one of the three colors, let's call it $ a $ . Then, Bob chooses a color $ b\ne a $ , chooses an empty cell, and places a token of color $ b $ on that cell. We say that there is a conflict if there exist two adjacent cells containing tokens of the same color. Two cells are considered adjacent if they share a common edge. If at any moment there is a conflict, Alice wins. Otherwise, if $ n^2 $ turns are completed (so that the grid becomes full) without any conflicts, Bob wins. We have a proof that Bob has a winning strategy. Play the game as Bob and win. The interactor is adaptive. That is, Alice's color choices can depend on Bob's previous moves.

N/A

N/A

The final grid from the sample is pictured below. Bob wins because there are no two adjacent cells with tokens of the same color. $ $$$\begin{matrix}2&3\\3&1\end{matrix} $ $$$ The sample is only given to demonstrate the input and output format. It is not guaranteed to represent an optimal strategy for Bob or the real behavior of the interactor.