#WC2022C. 猜词

猜词

题目描述

在本题中,你需要和交互库玩一款经典的游戏。在每局游戏中,交互库会从词库中生成一个 55 个字母的单词,并告诉你它的首字母,你需要在 55 次机会内猜中它。

每次猜测都需要猜一个词库中存在的单词。如果猜对了,游戏结束;在每次猜错后,交互库会返回哪些字母的位置是正确的(以金色表示),以及哪些字母在待猜单词中出现了但位置是错误的(以银色表示)。

具体来说,交互库会返回两个布尔类型的数组 gold\texttt{gold}silver\texttt{silver}gold[i]0 \leq i < 5,下同)表示第 ii 个字母是否猜对了(位置和内容均正确);silver[i] 表示如果第 ii 个字母没猜对(即不为金色),这个字母是否在本次猜测非金色字母的部分出现过。

例如,待猜单词为 panic\texttt{panic},猜测 paper\texttt{paper} 后交互库会返回 gold[0] = truep\texttt{p} 正确),gold[1] = truea\texttt{a} 正确),其余均为 false(注意 paper\texttt{paper} 中的第二个 p\texttt{p} 虽然在 panic\texttt{panic} 中出现过,但出现位置为本次猜测中的金色字母部分,因此 silver[2] = false)。

又如,待猜单词为 apple\texttt{apple},猜测 paper\texttt{paper} 后交互库会返回 gold[2] = truep\texttt{p} 正确),silver[0] = truep\texttt{p} 在本次猜测非金色字母的部分出现过),silver[1] = truea\texttt{a} 出现过),silver[3] = truee\texttt{e} 出现过),其余均为 false

【评分方式】

由于每局游戏具有较高的随机性,在本题中,你需要连续玩 T=1000T = 1000 局游戏。每局游戏的评分标准如下:

  • 如果任意一次猜测单词的长度不等于 55,或者猜测的单词不在词库中,得 00 分;
  • 如果第 11 次猜测猜对,得 150150 分;
  • 如果第 22 次猜测猜对,得 120120 分;
  • 如果第 33 次猜测猜对,得 100100 分;
  • 如果第 44 次猜测猜对,得 9090 分;
  • 如果第 55 次猜测猜对,得 8585 分;
  • 如果 55 次猜测均错,得 00 分。你在本题中的得分为【10001000 局游戏的平均分】和 100100 分的较小值。

【如何使用交互库】

本题只支持 C++。

你只能提交一个源文件 word.cpp 实现下列函数,并且遵循下面的命名和接口。

你需要包含头文件 word.h

你不需要,也不应该实现主函数。

你需要实现的函数有:

const char *guess(int num_testcase, int remaining_guesses, char initial_letter, bool *gold, bool *silver);
void init(int num_scramble, const char *scramble);

其中,第 ii 局游戏的 num_testcase 参数为 ii1iT1 \leq i \leq T),每局游戏会调用 151 \sim 5guess 函数,第 jj 次调用的 remaining_guesses 参数为 6j6-j1j51 \leq j \leq 5)。initial_letter 参数为当前局游戏待猜单词的首字母(保证为小写字母)。保证每次调用 guess 函数的 num_testcase 单调不降;保证 num_testcase 相同时 initial_letter 不变且 remaining_guesses 单调递降。如果某次猜测猜对或非法,则该局游戏结束,下次调用 guess 函数为下一局游戏。

goldsilver 为如上所述的两个布尔数组。当 remaining_guesses 参数为 55 时,goldsilver 数组不可用(即,可能为空指针),请避免使用它们;当 remaining_guesses 参数小于 55 时,goldsilver 为两个大小为 55 的布尔数组,存储着上一次猜测的结果。

guess 函数的返回值需要是一个长度为 55 的字符串,表示猜测的单词。该单词需要在词库中。

init 函数会在调用所有 guess 函数之前调用恰好一次。其中 num_scramble 参数是词库大小,scramble 是一个长度为 num_scramble×5\texttt{num\_scramble} \times 5 的字符串,存储着词库中的所有单词,每个单词长度为 55,中间没有任何分隔符。

【附加文件】

本题下发的文件有 word.h, word_sample.cpp, play.cpp, grader.cpp, scramble.txt, scramble.csv, scramble_pure.txt

word_sample.cpp 是你要实现的 word.cpp 的一个样例。

grader.cpp 为示例评测程序(编译命令:g++ ‐o grader grader.cpp word.cpp)。

scramble.txt, scramble.csv, scramble_pure.txt 均为本题所使用的词库文件,其中 scramble.txt 以换行符分隔单词,scramble.csv 以逗号分隔单词,scramble_pure.txt 不分隔单词(即,与 init 函数中的 scramble 参数内容相同)。

play.cpp 是一个可以让你和你的程序玩这个游戏的程序(编译命令:g++ ‐o play play.cpp word.cpp)。下面介绍 play.cpp 的输入与输出格式。

输入格式

输入第一行包含一个正整数 TT,表示游戏局数。

接下来 TT 局游戏,每局游戏第一行输入一个小写字母,表示待猜单词的首字母。

接下来 040 \sim 4 行,每行一个长度为 55 的由 g\texttt{g}s\texttt{s}-\texttt{-} 组成的字符串,其中第 ii 位(0 \leq i < 5,下同)是 g\texttt{g} 表示 gold[i] = true,第 ii 位是 s\texttt{s} 表示 silver[i] = true,第 ii 位是 -\texttt{-} 表示 gold[i] = silver[i] = false。如果猜对或猜测单词非法,则该局游戏结束,因此输入的行数是可变的。

输出格式

对于除了第一行游戏局数以外的每行输入,输出一个长度为 55 的字符串,表示猜测的单词。样例输出加入了额外的空行以便阅读。

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

样例解释

对于第 11 局游戏,待猜单词为 panic\texttt{panic},在第 44 次猜测猜对。

对于第 22 局游戏,待猜单词为 apple\texttt{apple},在第 33 次猜测猜对。

对于第 33 局游戏,待猜单词为 apple\texttt{apple},在第 33 次猜测猜对。注意即使每个位置都有至少一次猜测为金色,也需要额外一次猜测才算猜对。

对于第 44 局游戏,待猜单词为 above\texttt{above}55 次猜测均错。注意第 55 次猜测的结果并不需要输入,也不会传入 guess 函数。

对于第 55 局游戏,待猜单词为 apple\texttt{apple},第 11 次猜测非法(不在词库内),该局游戏直接结束。注意样例程序并不会自动识别这种情况。

对于第 66 局游戏,待猜单词为 apple\texttt{apple},在第 11 次猜测猜对。

对于第 77 局游戏,待猜单词为 cobra\texttt{cobra}。注意猜测 kraal\texttt{kraal} 时两个 a\texttt{a} 均为银色。注意由于样例程序并不知道待猜单词是什么,需要手动结束程序。

数据范围

对于 100%100\% 的数据,T=1000T = 1000num_scramble=8869\texttt{num\_scramble} = 8869。每次待猜的单词均在词库中所有单词这一范围内独立均匀随机生成,这些单词在调用 guess 函数之前已经完全确定,不会根据和你的程序的交互过程动态构造。交互库本身使用的时间不超过 11 秒,使用的内存不超过 16MB。

提示

请点击题目右侧“文件”选项下载本题的下发文件。

由于本题只有 11 组评测数据,运行错误、超时、内存超限等错误都会导致本题总分为 00 分。建议仔细检查避免此类错误。