Background

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.

This is an interactive problem.

Problem Description

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:

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.

Input Format

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.

Output Format

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.

7
p
gg---
gg---
ggg--
a
g----
ssgs-
a
g---g
gggg-
a
g---g
g---g
g---g
g---g
a
a
c
-sss-

paper
paths
panda
panic

aargh
paper
apple

afore
apply
apple

apple
apple
apple
apple
apple

abcde

apple

kraal
cobra

Hint

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