P8079 [WC2022] Word Guessing

**Abusing the judging system for this problem will result in an immediate account ban.** **Due to limitations of the judge environment, do not submit this problem using the C++14 (GCC 9) language, otherwise it may cause compilation errors.** The official testdata sent by the problem setter is used, but due to disputes, the “community testdata” name is temporarily kept. 60 s, 1 GiB, -O2, interactive. When submitting on Luogu, please note the following two points: - **Please remove the `word.h` header file from your code.** - **Do not use `rand()` for randomness.** Please replace it with `mt19937`. Be careful not to reuse a conflicting name, otherwise you will get CE. For details, see [here](https://www.luogu.com.cn/discuss/405355). **This is an interactive problem.**

In this problem, you need to play a classic game with the interactive library. In each game, the interactive library will generate a $5$-letter word from the dictionary and tell you its first letter. You need to guess it within $5$ attempts. Each guess must be a word that exists in the dictionary. If you guess correctly, the game ends. After each incorrect guess, the interactive library will return which letter positions are correct (shown as gold) and which letters appear in the target word but are in the wrong position (shown as silver). Specifically, the interactive library returns two boolean arrays $\texttt{gold}$ and $\texttt{silver}$. `gold[i]` ($0 \leq i < 5$, same below) indicates whether the $i$-th letter is guessed correctly (both position and character are correct). `silver[i]` indicates, if the $i$-th letter is not correct (i.e., not gold), whether this letter has appeared in the non-gold part of the target word. For example, if the target word is $\texttt{panic}$ and you guess $\texttt{paper}$, the interactive library returns `gold[0] = true` ( $\texttt{p}$ is correct), `gold[1] = true` ( $\texttt{a}$ is correct), and all others are `false` (note that although the second $\texttt{p}$ in $\texttt{paper}$ appears in $\texttt{panic}$, it appears in the gold part of this guess, so `silver[2] = false`). As another example, if the target word is $\texttt{apple}$ and you guess $\texttt{paper}$, the interactive library returns `gold[2] = true` ( $\texttt{p}$ is correct), `silver[0] = true` ( $\texttt{p}$ appears in the non-gold part of the target word), `silver[1] = true` ( $\texttt{a}$ appears), `silver[3] = true` ( $\texttt{e}$ appears), and all others are `false`. **Scoring** Because each game has a high degree of randomness, you need to play $T = 1000$ games in a row. The scoring for each game is as follows: - If any guessed word does not have length $5$, or **the guessed word is not in the dictionary**, you get $0$ points. - If you guess correctly on the $1$-st attempt, you get $150$ points. - If you guess correctly on the $2$-nd attempt, you get $120$ points. - If you guess correctly on the $3$-rd attempt, you get $100$ points. - If you guess correctly on the $4$-th attempt, you get $90$ points. - If you guess correctly on the $5$-th attempt, you get $85$ points. - If all $5$ attempts are wrong, you get $0$ points. Your score for this problem is the smaller one of the following two values: the average score over the $1000$ games, and $100$. **How to use the interactive library** This problem only supports C++. You may only submit one source file `word.cpp` to implement the following functions, and you must follow the naming and interfaces below. You need to include the header file `word.h`. You do not need to, and should not, implement `main`. The functions you need to implement are: ```cpp const char *guess(int num_testcase, int remaining_guesses, char initial_letter, bool *gold, bool *silver); void init(int num_scramble, const char *scramble); ``` For the $i$-th game, the parameter `num_testcase` is $i$ ($1 \leq i \leq T$). In each game, the `guess` function will be called $1 \sim 5$ times. For the $j$-th call, the parameter `remaining_guesses` is $6-j$ ($1 \leq j \leq 5$). The parameter `initial_letter` is the first letter of the target word in the current game (guaranteed to be a lowercase letter). It is guaranteed that across calls to `guess`, `num_testcase` is non-decreasing. It is guaranteed that when `num_testcase` is the same, `initial_letter` does not change and `remaining_guesses` is strictly decreasing. If a guess is correct or illegal, that game ends, and the next call to `guess` will be for the next game. The boolean arrays `gold` and `silver` are as described above. When `remaining_guesses` is $5$, the `gold` and `silver` arrays are not available (i.e., they may be null pointers), so please avoid using them. When `remaining_guesses` is less than $5$, `gold` and `silver` are two boolean arrays of size $5$, storing the result of the previous guess. The return value of `guess` must be a string of length $5$, representing your guessed word. This word must be in the dictionary. The `init` function will be called exactly once before all calls to `guess`. The parameter `num_scramble` is the dictionary size. `scramble` is a string of length $\texttt{num\_scramble} \times 5$, storing all words in the dictionary. Each word has length $5$, with no separators between words. **Additional files** The provided files are `word.h, word_sample.cpp, play.cpp, grader.cpp, scramble.txt, scramble.csv, scramble_pure.txt`. `word_sample.cpp` is a sample implementation of `word.cpp` that you need to write. `grader.cpp` is a sample judging program (compile command: `g++ ‐o grader grader.cpp word.cpp`). `scramble.txt, scramble.csv, scramble_pure.txt` are the dictionary files used in this problem. In `scramble.txt`, words are separated by newline characters. In `scramble.csv`, words are separated by commas. In `scramble_pure.txt`, words are not separated (that is, it is the same as the `scramble` parameter in `init`). `play.cpp` is a program that lets you play this game with your own program (compile command: `g++ ‐o play play.cpp word.cpp`). The input and output formats of `play.cpp` are described below.

**Sample Input Format** The first line contains a positive integer $T$, representing the number of games. For each of the next $T$ games, the first line contains a lowercase letter, representing the first letter of the target word. Then there are $0 \sim 4$ lines. Each line is a string of length $5$ consisting of $\texttt{g}$, $\texttt{s}$, and $\texttt{-}$. At position $i$ ($0 \leq i < 5$, same below), $\texttt{g}$ means `gold[i] = true`, $\texttt{s}$ means `silver[i] = true`, and $\texttt{-}$ means `gold[i] = silver[i] = false`. If you guess correctly or the guessed word is illegal, the game ends, so the number of input lines is variable.

**Sample Output Format** For every input line except the first line containing the number of games, output a string of length $5$, representing the guessed word. Extra blank lines are added in the sample output for readability.

**Sample Explanation** In game $1$, the target word is $\texttt{panic}$, and it is guessed correctly on the $4$-th attempt. In game $2$, the target word is $\texttt{apple}$, and it is guessed correctly on the $3$-rd attempt. In game $3$, the target word is $\texttt{apple}$, and it is guessed correctly on the $3$-rd attempt. Note that even if every position has been guessed as gold at least once, you still need an additional guess to count as guessing correctly. In game $4$, the target word is $\texttt{above}$, and all $5$ attempts are wrong. Note that the result of the $5$-th guess does not need to be input, and it will not be passed into the `guess` function. In game $5$, the target word is $\texttt{apple}$. The $1$-st guess is illegal (not in the dictionary), so the game ends immediately. Note that the sample program will not automatically detect this situation. In game $6$, the target word is $\texttt{apple}$, and it is guessed correctly on the $1$-st attempt. In game $7$, the target word is $\texttt{cobra}$. Note that when guessing $\texttt{kraal}$, both $\texttt{a}$ are silver. Also note that since the sample program does not know what the target word is, you need to terminate the program manually. **Constraints** For $100\%$ of the data, $T = 1000$, $\texttt{num\_scramble} = 8869$. Each target word is generated independently and uniformly at random from the set of all words in the dictionary. These words are fully determined before any calls to `guess`, and will not be constructed dynamically based on the interaction process with your program. The interactive library itself uses no more than $1$ second of time and no more than 16 MiB of memory. Since this problem has only $1$ set of testdata, runtime errors, time limit exceeded, memory limit exceeded, and similar errors will all cause the total score for this problem to be $0$. It is recommended to check carefully to avoid such errors. Translated by ChatGPT 5