#P11407. 游戏(通信题)
游戏(通信题)
3 游戏
这是一道通信题。
3.1 Problem Statement
小 D 和小 Y 正在和小 X 玩游戏。
他们之间的游戏共进行轮。每轮游戏中,以下事件会依次发生:
• 小 X 随机生成一个 或 之间的整数,表示这一轮的答案。
• 小 D 猜测这一轮的答案是什么,小 D 知道且只知道之前所有的答案以及猜测。
• 小 Y 猜测这一轮的答案是什么,小 Y 知道且只知道之前所有的答案以及猜测。
• 若小 D 和小 Y 均猜测正确,则他们得到 分,否则不得分。
显然这个游戏非常地不公平——小 D 和小 Y 只能够完全随机地做出猜测。
为了弥补这一点,小 X 会在小 D 和小 Y 商定完策略后,告诉小 Y 每一轮的答案,然后再进行这个游戏。
小 D 和小 Y 当然都想要最大化他们的总得分,但是他们并不会,请你帮帮他们。
3.2 Implementation Details
你的程序需要包含头文件 game.h,即 #include "game.h"。 你不需要,也不应该实现主函数。你只需要实现下列函数:
• std::string PlaySecond(std::string arr):
– 其中 arr 为一个 0/1 字符串,表示小 Y 得到的每一轮的答案;
– 你可以通过调用 arr.size() 来得到 的取值;
– 因为小 D 和小 Y 事先商定了策略,故小 Y 可以完全推算出小 D 的猜测;
– 函数应当返回一个长度为 的 0/1 字符串,表示小 Y 每一轮的猜测。
• void PlayFirst(int n):
– 其中 n 表示游戏进行的轮数;
– 该函数不应当返回任何值,而是通过调用下面的函数与交互库进行交互。
你可以通过调用如下函数来与交互库进行交互:
• std::string guess(char x):
– 其中 x 表示小 D 做出的一次猜测;
– 该函数会返回一个长度为 的 std::string,第一个字符表示小 Y 在这一轮做出的猜测,而第二个字符表示这一轮的答案。
6
3.3 Sample
对于一次答案为 0101 的可能的交互过程如下:
交互库调用函数 PlaySecond(0101),选手返回 1001。 交互库调用函数 PlayFirst(4),选手做出如下调用:
• 选手调用 guess(0),交互库返回 10,猜测错误不得分;
• 选手调用 guess(1),交互库返回 01,猜测错误不得分;
• 选手调用 guess(0),交互库返回 00,猜测正确得 分;
• 选手调用 guess(1),交互库返回 11,猜测正确得 分。
则小 D 和小 Y 的总得分为 。
3.4 Sample Grader
在下发文件中,提供了样例交互库 game/grader.cpp,这个交互库可以帮助你在本机测试自己的代码。
你可以在命令行中,通过命令:g++ -o game game.cpp grader.cpp -std=c++11 -O2 -lm 得到可执行文件 game。
可执行文件将会按照以下格式从标准输入得到输入:
• 一行一个长度为的字符串表示每一轮的答案。
可执行文件将会按照以下格式输出到标准输出:
• 第一行一个长度为的字符串表示小 Y 每一轮的猜测。
• 第二行一个长度为 的字符串表示小 D 每一轮的猜测。
• 第三行一个整数表示小 D 和小 Y 的总得分。
在下发文件中,还提供了样例程序 game/game.cpp。它只用于熟悉交互方式,而并不能得到任何分数。我们建议选手在该样例程序的基础上修改得到自己的程序。 请注意最终测试时会将你的代码运行两次,任何全局变量都会被清空。因此在两次调用之间,选手无法保存任何信息,而只能通过与交互库交互获得信息。任何试图攻击交互库的行为都会导致选手在本题上得到 分。
3.5 Constraints
对于所有测试数据,,保证数据使用 std::mt19937 生成。本题共 个测试点,你的得分为所有测试点的得分之和。对于一个测试点,设你的程序使小 D 和小 Y 得分为,则你的得分如下(如果同时满足多个条件,则取得分最高者):
| 至少为 | 单个测试点得分 |
|---|---|
| 49.9 | 2 |
| 62.4 | 6 |
| 66.6 | 9 |
| 68.9 | 11 |
| 70.4 | 13 |
| 71.9 | 15 |
| 73.4 | 18 |
| 74.7 | 20 |