Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D1T3. $\texttt{3s,0.5G}$.

I like Xiao Yuan!

Problem Description

$N$ OIers are wearing either red or white hats. Each person can only see the colors of the other people's hats, and they will guess the color of their own hat based on what they see.

They want to design a set of guessing strategies that satisfies the following conditions:

• Suppose $b$ people wear white hats; then at least $\lfloor\frac{b}{2}\rfloor$ of them guess their own hat color correctly.
• Suppose $c$ people wear red hats; then at least $\lfloor\frac{c}{2}\rfloor$ of them guess their own hat color correctly.

Help them find a strategy such that the conditions are satisfied in all $2^N$ possible cases.

Input Format

One line with one integer $N$.

Output Format

Output $N$ lines. Each line is a string of length $2^{N-1}$ consisting of $\texttt{B},\texttt{C}$.

The string on line $i$ describes the strategy of the $i$-th OIer. Specifically:

• Define $f(S)$ as follows: sort all strings of length $(N-1)$ consisting of $\texttt{B},\texttt{C}$ in lexicographical order, then $f(S)$ is the rank of $S$.
• Let $x$ be the string output on line $i$, and let $s_i\in \{\texttt{B},\texttt{C}\}$ be the hat color worn by the $i$-th OIer. Here, $\texttt{B}$ means white (Croatian: “bijela”), and $\texttt{C}$ means red (Croatian: “crvena”).
• Let $y=\overline{s_1s_{2}\cdots s_{i-1}s_{i+1}\cdots s_n}$. Note that the left side is the most significant bit.
• The color guessed by the $i$-th OIer is $x_{f(y)}$.

See [Sample Explanation].

2

BC
CC

3

BBCC
BCBC
BBCC

Hint

Sample Explanation

Take sample $2$ as an example.

When $s=\texttt{CCC}$, for the $1$-st OIer, $x=\texttt{BBCC}$ and $y=\texttt{CC}$. Clearly $f(y)=4$, so he will guess $x_4=\texttt{C}$.

Scoring

Translated by ChatGPT 5