P13116 [GCJ 2019 #2] Pottery Lottery

陶艺宫将举办一次抽奖活动，奖品是艺术家 Cody-Jamal 的一些珍贵花瓶。抽奖规则如下： - 有 100 人参与抽奖。每位玩家拥有一个唯一编号（1 到 100 之间），并获得一个带有该编号的代币。 - 桌上有 20 个空陶瓷花瓶，编号为 1 到 20。花瓶的开口足够大，可以放入代币，但开口很窄，玩家无法看到里面的内容。 - 在第 $i$ 天，编号为 $i$ 的玩家选择一个花瓶，并将自己的代币放入该花瓶。由于花瓶除了标签外完全相同，每位玩家都会独立且等概率地随机选择一个花瓶。 - 第 100 天，在编号为 100 的玩家放入代币后，组织者会摇晃花瓶，统计每个花瓶中的代币数量。如果恰好有一个花瓶中的代币数量比其他所有花瓶都少，那么这个花瓶就是“中奖花瓶”。组织者会倒出中奖花瓶中的所有代币，代币编号对应的玩家都将获得一个花瓶！如果有多个花瓶的代币数量同为最少，则无人获奖。 你被雇佣来测试抽奖的安全性，并将参与若干次试运行。公司总是会分配给你编号 100 —— 也就是说，你替代了编号为 100 的玩家。 你发现了一些夜间篡改抽奖的方法，但安保很严，你能做的有限！具体来说，在前 99 天的每一天结束后，你可以执行以下两种操作之一： - 伪造一个任意玩家编号（1 到 100 之间）的代币，并将其放入任意一个花瓶。你的伪造技术非常高超：如果某个花瓶成为中奖花瓶，中奖花瓶中的伪造代币也会使对应编号的玩家获奖（有一个例外，见下文）。 - 使用特殊相机查看某个花瓶内所有代币上的编号。 你可以在不同的夜晚选择不同的操作，并且可以动态决定：不需要提前规划所有操作。 第 100 天轮到你放入自己的代币，你可以选择任意一个花瓶（不需要随机选择）。当天你不能进行其他操作。 你知道，如果中奖花瓶中存在同一玩家编号的多个代币，作弊行为会被发现，无人获奖。但其他花瓶中是否有重复编号的代币无关紧要，因为组织者不会查看那些花瓶。 你的目标是在至少 90% 的测试用例中成为获奖者。 ### 交互协议 这是一个交互题。 最开始，你的程序应读取一行，包含一个整数 $\mathbf{T}$，表示测试用例数量。然后，你需要处理 $\mathbf{T}$ 个测试用例。 每个测试用例开始时，评测器会输出一行，包含一个整数：当前天数（评测器从第 1 天开始，在第 $i$ 天输出 $i$）。你的程序读取该整数后，应输出一行，包含两个整数 $\mathbf{V}$ 和 $\mathbf{P}$，其中 $1 \leq \mathbf{V} \leq 20$，$0 \leq \mathbf{P} \leq 100$。评测器的解释如下： - 如果 $1 \leq \mathbf{P} \leq 100$，你会将编号为 $\mathbf{P}$ 的代币放入编号为 $\mathbf{V}$ 的花瓶。评测器不会对此做出回应。 - 如果 $\mathbf{P} = 0$，你会查看编号为 $\mathbf{V}$ 的花瓶内的内容。评测器会输出一行整数。第一个整数是 $\mathbf{N}$，表示该花瓶内的代币数量，接下来有 $\mathbf{N}$ 个整数，按非递减顺序给出每个代币上的玩家编号。 注意，第 100 天你必须放入自己的代币，因此 $\mathbf{P}$ 必须为 100。 请记住，在第 $i$ 天（$1 \leq i \leq 99$），评测器会按照题目描述模拟第 $i$ 位玩家的操作，这发生在你当天的操作之前。 在你第 100 天提交操作后，如果这是最后一个测试用例，你的程序应终止；否则，继续读取下一个测试用例的数据。（注意，评测器不会告知你每个用例是否正确。只有在你完成所有 $\mathbf{T}$ 个测试用例后，评测器才会检查你是否答对足够多的用例，因此不要提前退出！例如，如果你答对了前 225 个用例中的 225 个然后退出，或者输出格式错误，你的解答将不被判为正确。） 如果你的程序输出了非法内容（如 $\mathbf{P}$ 或 $\mathbf{V}$ 不合法，或在第 100 天尝试查看花瓶），评测器会向你的输入流发送一行 -1，之后不会再有任何输出。如果你的程序在收到 -1 后仍继续等待评测器，则会超时，导致 Time Limit Exceeded 错误。请确保你的程序能及时退出，以获得 Wrong Answer 判罚，而不是 TLE。若总内存超限或程序运行时出错，也会得到相应的判罚。

参见交互协议。

参见交互协议。

**交互样例** ``` t = readline_int() // 读取 250 到 t curr_day = readline_int() // 读取 1（第 1 天） printline 8 100 to stdout // 将编号 100 的代币放入 8 号花瓶 flush stdout curr_day = readline_int() // 读取 2（第 2 天） printline 8 99 to stdout // 将编号 99 的代币放入 8 号花瓶 flush stdout curr_day = readline_int() // 读取 3（第 3 天） printline 8 100 to stdout // 将编号 100 的代币放入 8 号花瓶 flush stdout curr_day = readline_int() // 读取 4（第 4 天） printline 20 7 to stdout // 将编号 7 的代币放入 20 号花瓶 flush stdout curr_day = readline_int() // 读取 5（第 5 天） printline 8 0 to stdout // 查看 8 号花瓶 flush stdout tokens = readline_int_list() // 读取 5 2 5 99 100 100（玩家 2 和 5 // 恰好选择了 8 号花瓶） curr_day = readline_int() // 读取 6（第 6 天） printline 8 101 to stdout // 尝试放入非法编号的代币 flush stdout curr_day = readline_int() // 读取 -1（评测器判定解答错误） exit // 退出，避免 TLE 错误 ``` 你可以使用本地测试工具在本地或平台上测试。若要在本地测试，需要让测试工具与你的代码并行运行；你可以使用我们的 [interactive runner](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)。更多信息请阅读该文件中的注释。 测试工具的使用说明已包含在工具的注释中。我们鼓励你自行添加测试用例。请注意，虽然测试工具旨在模拟评测系统，但它**不是**真实的评测系统，行为可能有所不同。 **数据范围** **测试点 1（23 分，可见）** - $\mathbf{T} = 250$。 由 ChatGPT 4.1 翻译