#P11407. 游戏(通信题)

游戏(通信题)

3 游戏

这是一道通信题。

3.1 Problem Statement

小 D 和小 Y 正在和小 X 玩游戏。

他们之间的游戏共进行nn轮。每轮游戏中,以下事件会依次发生:

• 小 X 随机生成一个00 或 11 之间的整数,表示这一轮的答案。

• 小 D 猜测这一轮的答案是什么,小 D 知道且只知道之前所有的答案以及猜测。

• 小 Y 猜测这一轮的答案是什么,小 Y 知道且只知道之前所有的答案以及猜测。

• 若小 D 和小 Y 均猜测正确,则他们得到 11 分,否则不得分。

显然这个游戏非常地不公平——小 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() 来得到nn 的取值;

– 因为小 D 和小 Y 事先商定了策略,故小 Y 可以完全推算出小 D 的猜测;

– 函数应当返回一个长度为nn 的 0/1 字符串,表示小 Y 每一轮的猜测。

• void PlayFirst(int n):

– 其中 n 表示游戏进行的轮数;

– 该函数不应当返回任何值,而是通过调用下面的函数与交互库进行交互。

你可以通过调用如下函数来与交互库进行交互:

• std::string guess(char x):

– 其中 x 表示小 D 做出的一次猜测;

– 该函数会返回一个长度为 22 的 std::string,第一个字符表示小 Y 在这一轮做出的猜测,而第二个字符表示这一轮的答案。

6

3.3 Sample

对于一次答案为 0101 的可能的交互过程如下:

交互库调用函数 PlaySecond(0101),选手返回 1001。 交互库调用函数 PlayFirst(4),选手做出如下调用:

• 选手调用 guess(0),交互库返回 10,猜测错误不得分;

• 选手调用 guess(1),交互库返回 01,猜测错误不得分;

• 选手调用 guess(0),交互库返回 00,猜测正确得 11 分;

• 选手调用 guess(1),交互库返回 11,猜测正确得 11 分。

则小 D 和小 Y 的总得分为 22。

3.4 Sample Grader

在下发文件中,提供了样例交互库 game/grader.cpp,这个交互库可以帮助你在本机测试自己的代码。

你可以在命令行中,通过命令:g++ -o game game.cpp grader.cpp -std=c++11 -O2 -lm 得到可执行文件 game。

可执行文件将会按照以下格式从标准输入得到输入:

• 一行一个长度为nn的字符串SS表示每一轮的答案。

可执行文件将会按照以下格式输出到标准输出:

• 第一行一个长度为nn的字符串表示小 Y 每一轮的猜测。

• 第二行一个长度为nn 的字符串表示小 D 每一轮的猜测。

• 第三行一个整数表示小 D 和小 Y 的总得分。

在下发文件中,还提供了样例程序 game/game.cpp。它只用于熟悉交互方式,而并不能得到任何分数。我们建议选手在该样例程序的基础上修改得到自己的程序。 请注意最终测试时会将你的代码运行两次,任何全局变量都会被清空。因此在两次调用之间,选手无法保存任何信息,而只能通过与交互库交互获得信息。任何试图攻击交互库的行为都会导致选手在本题上得到 00 分。

3.5 Constraints

对于所有测试数据,n=106n=10^{6},保证数据使用 std::mt19937 生成。本题共 55 个测试点,你的得分为所有测试点的得分之和。对于一个测试点,设你的程序使小 D 和小 Y 得分为n⋅t%n·t\%,则你的得分如下(如果同时满足多个条件,则取得分最高者):

tt 至少为 单个测试点得分
49.9 2
62.4 6
66.6 9
68.9 11
70.4 13
71.9 15
73.4 18
74.7 20