P10746 [SEERC 2020] Codenames

There are $q$ $5 \times 5$ boards. For each cell, its color is given (only `r`, `b`, `n`, `x` are possible). The color distribution is: $9$ `r`, $8$ `b`, $5$ `n`, and $1$ `x`. The character corresponding to each cell on the board is fixed as follows: ``` abcde fghij klmno pqrst uvwxy ``` On the board, some colors have already been revealed (a revealed cell is shown using the uppercase letter of its color). Then you need to choose a string $w$ from a list of $n$ strings and a number $g$, and perform the following operation $g$ times. - If the cell corresponding to the current character $w_i$ has already been revealed, do nothing and set $i \gets i + 1$. - Otherwise, reveal the cell corresponding to $w_i$. If the color of $w_i$ is `n`, `b`, or `x`, you lose. Then set $i \gets i + 1$. - Stop when $g$ operations are completed or when all `r` cells have been revealed. You want to reveal all `r` cells. Find a pair $(w, g)$ that satisfies this requirement.

The first line contains an integer $n\ (1 \leq n \leq 10^5)$. Then follow $n$ lines, each containing a string, describing the whole list of strings. Line $n + 2$ contains an integer $q\ (1 \leq q \leq 10^5)$, the number of boards. Then follow $q$ boards, each of size $5 \times 5$, describing the colors of the $i$-th board.

For each board, if there is a solution, output one valid $w$ and $g\ (1 \leq g \leq 9)$. If there is no solution, output `IMPOSSIBLE`.

The answer could also be `actor 4`, `zeta 2`, etc. Translated by ChatGPT 5