P13107 [GCJ 2019 #1A] Golf Gophers

去年，一群讨厌的地鼠在我们的果园里安了家。我们试图转行，开了一家迷你高尔夫球场，但看起来地鼠们又跟着我们来了！我们再次需要弄清楚有多少只地鼠，但我们无法直接观察它们，因为它们很隐秘且是夜行性动物，而我们喜欢晚上睡觉。我们只知道地鼠的数量在 $1$ 到 $M$ 之间（包含两端）。 我们的迷你高尔夫球场以每个球洞上都有一个小型电子风车而闻名，一共 18 个球洞。第 $i$ 个风车有 $2 \leqslant \mathbf{B}_{\mathrm{i}} \leqslant 18$ 片叶片，编号从 $0$ 到 $\mathbf{B}_{\mathrm{i}}-1$，顺时针排列。每天晚上，睡觉前我们会关闭所有风车，并将每个风车设置为 0 号叶片朝下，这样风车才能为第二天正常充电。然而，我们注意到，早上醒来时风车的位置已经被扰乱。由于我们的球场没有风，所以我们认为一定是这些调皮的地鼠搞的鬼！ 我们知道，每天晚上，所有地鼠都会依次出现；每只地鼠会独立且等概率地选择一个风车，并将其逆时针旋转一片叶片。例如，对于一个有 3 片叶片、0 号叶片朝下的风车，第一只地鼠会让 1 号叶片朝下，之后每有一只地鼠操作该风车，朝下的叶片编号依次变为 2、0、1，依此类推。 我们已经想好了一个计划。我们的风车设计允许我们轻松更改叶片数量（以调整球场难度），现在我们要利用这一点！每天晚上睡觉前，我们可以为每个风车选择叶片数量，范围在给定的限制内；我们不需要每晚为每个风车选择相同的叶片数，也不需要每晚都做相同的选择。第二天早上，我们会观察每个风车朝下的叶片编号。 我们有 $\mathbf{N}$ 个夜晚来推断出 $\mathbf{G}$，即地鼠的数量。你能帮我们吗？ ### 交互协议 这是一个交互题。 最开始，你的程序应读取一行，包含三个整数 $\mathbf{T}$、$\mathbf{N}$ 和 $\mathbf{M}$，分别表示测试用例数量、每个用例允许的夜晚数和地鼠数量的最大值。然后，你需要处理 $\mathbf{T}$ 个测试用例。 在每个测试用例中，你的程序最多与评测器进行 $\mathbf{N}+1$ 次交互。你可以进行最多 $\mathbf{N}$ 次如下形式的交互： - 你的程序输出一行 18 个整数，每个整数在 2 到 18 之间（包含），第 $i$ 个数表示你希望第 $i$ 个风车当晚拥有的叶片数。 - 评测器返回一行 18 个整数，第 $i$ 个数表示早上第 $i$ 个风车朝下的叶片编号（经过地鼠捣乱后）。如果你输出了非法数据（如超出范围的数字或格式错误），评测器会返回 -1。 每个夜晚，对于每只地鼠，选择哪个风车是独立且等概率的（伪）随机选择，与其他地鼠（包括自己）在任何夜晚的选择都无关。 在进行 0 到 $\mathbf{N}$ 次上述交互后，你必须再进行一次如下形式的交互： - 你的程序输出一个整数，表示你猜测的地鼠数量 $\mathbf{G}$。 - 评测器返回一行一个整数：如果你的答案正确则为 1，否则为 -1（或你输出了格式错误的行）。 当评测器向你的输入流发送 -1（因为数据非法或答案错误）后，不会再发送其他输出。如果你的程序在收到 -1 后仍然等待评测器输出，将会超时（TLE）。请注意，你有责任在收到 -1 后及时退出，以获得 Wrong Answer 判决而不是 Time Limit Exceeded。如果超出内存限制或发生运行时错误，将获得相应的判决。

见交互协议。

见交互协议。

**交互样例** 本交互对应于测试集 1。假设评测器实际设定的地鼠数量为 10。 ``` t, n, m = readline_int_list() // 读取 t=20, n=365, m=100。 // 第一天选择风车叶片数。 printline 2 2 2 2 18 3 3 3 3 3 3 4 4 4 4 5 2 2 到标准输出 flush stdout // 读取 0 0 0 0 0 0 1 2 1 0 1 2 0 0 0 0 1 0 到 res。 res = readline_int_list() // 第二天选择风车叶片数。 printline 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 到标准输出 flush stdout // 读取 0 1 1 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 到 res。 res = readline_int_list() printline 8 到标准输出 // 我们做了一个错误的猜测，尽管还可以调查 363 个夜晚。 flush stdout // 读取 -1 到 verdict（评测器判定我们的解答错误） exit // 退出以避免 TLE 错误 ``` 注意，即使猜测与已知信息一致，如果不是正确答案，依然会判错。 你可以使用本题的测试工具在本地或平台上测试。若要在本地测试，你需要让测试工具与代码并行运行；你可以使用我们的 [interactive runner](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)。更多信息请阅读该文件注释中的说明。 测试工具的使用说明已包含在工具注释中。我们鼓励你添加自己的测试用例。请注意，虽然测试工具旨在模拟评测系统，但它**不是**真实的评测系统，可能会有不同表现。 **数据范围** - $1 \leqslant \mathrm{T} \leqslant 20$。 **测试集 1（11 分，可见）** - $\mathrm{N}=365$。 - $\mathrm{M}=100$。 **测试集 2（21 分，隐藏）** - $\mathrm{N}=7$。 - $\mathrm{M}=10^{6}$。 由 ChatGPT 4.1 翻译