P10873 [COTS 2022] Hats Šeširi

Translated from [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D1T3. $\texttt{3s,0.5G}$. I like Xiao Yuan!

$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.

One line with one integer $N$.

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].

#### 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 | Test point ID | $N=$ | Score | |:-----:|:------:|:-------:| | $1$ | $4$ | $7$ | | $2$ | $5$ | $7$ | | $3$ | $6$ | $7$ | | $4$ | $7$ | $7$ | | $5$ | $8$ | $7$ | | $6$ | $9$ | $7$ | | $7$ | $10$ | $7$ | | $8$ | $11$ | $7$ | | $9$ | $12$ | $7$ | | $10$ | $13$ | $7$ | | $11$ | $14$ | $6$ | | $12$ | $15$ | $6$ | | $13$ | $16$ | $6$ | | $14$ | $17$ | $6$ | | $15$ | $18$ | $6$ | Translated by ChatGPT 5