P6183 [USACO10MAR] The Rock Game S

Before the cows go home to rest and have fun, Farmer John wants them to get some mental exercise by playing a game. The game board consists of $n$ identical holes, and all holes are initially **empty**. A cow may either cover an empty hole with a rock, or uncover a hole that was previously covered. A **game state** is defined by which holes are covered by rocks. The goal of the game is for the cow to reach **every possible game state** exactly once, and finally return to the initial state. Here is an example from one of their games (empty holes are shown as `O`, and holes covered by rocks are shown as `X`): | Time | Hole 1 | Hole 2 | Hole 3 | Description | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | O | O | O | At the beginning, all holes are empty | | $1$ | O | O | X | Cover hole 3 | | $2$ | X | O | X | Cover hole 1 | | $3$ | X | O | O | Uncover hole 3 | | $4$ | X | X | O | Cover hole 2 | | $5$ | O | X | O | Uncover hole 1 | | $6$ | O | X | X | Cover hole 3 | | $7$ | X | X | X | Cover hole 1 | Now the cows are stuck and cannot continue. They must uncover a hole, but no matter which hole they uncover, they will reach a state they have already visited. For example, if they remove the rock from the second hole, they will reach the state they already visited at time $2$ (`X O X`). Below is a valid solution for 3 holes: | Time | Hole 1 | Hole 2 | Hole 3 | Description | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | O | O | O | At the beginning, all holes are empty | | $1$ | O | X | O | Cover hole 2 | | $2$ | O | X | X | Cover hole 3 | | $3$ | O | O | X | Uncover hole 2 | | $4$ | X | O | X | Cover hole 1 | | $5$ | X | X | X | Cover hole 2 | | $6$ | X | X | O | Uncover hole 3 | | $7$ | X | O | O | Uncover hole 2 | | $8$ | O | O | O | Uncover hole 1 and return to the original state | Now the cows are tired of this game, and they want you to help. Given $n$, find a valid sequence of states for the game. If there are multiple solutions, output **any one** of them.

Only one line with an integer $n$.

Print a total of $2^n+1$ lines. Each line contains a string of length $n$ consisting only of characters `O` and `X`. The $i$-th character of the string indicates whether hole $i$ is covered or not in that state. The first and last lines must both be all `O`.

#### Explanation for Sample 1 See the problem description. #### Constraints For $100\%$ of the testdata, $1\le n\le15$. Translated by ChatGPT 5