#P12509. 【模板】通信题
【模板】通信题
题目背景
本题来源:http://8.136.99.126/p/P98,感谢 035966_L3 提供的题目。
以下排名不分先后。
- Update 2025/5/12 15:00:感谢 Moeebius 提供的 hack 代码,已更新交互库。
- Update 2025/5/12 21:18:感谢 SmokingTurtle 提供的 hack 思路,已更新交互库。
- Update 2025/5/13 14:40:感谢 破壁人五号 和 Argvchs 提供的 hack 代码,以及 Moeebius 提供的防范思路;已更新交互库。
- Update 2025/5/13 18:34:感谢 MrPython 提供的 hack 代码,已更新交互库。
- Update 2025/5/14 08:38:感谢 N_z_ 和 Exschawasion 提供的 hack 代码,已更新交互库。
题目描述
这是一道通信题,只支持 C++ 语言。请不要使用 C++14 (GCC 9) 提交。
给定两个长度相等(不超过 )且至多有一个位置的字符不同的 01 串 (下标从 开始)。Alice 只知道 ,Bob 只知道 。
Bob 想要确定 字符不同的那个位置。为了达成这一目的,Alice 决定偷偷帮助他。
具体来说,Alice 可以向 Bob 传递一个整数 ,满足 。
特别地,如果 ,Bob 应返回 0。
实现细节
你不需要,也不应该实现主函数。
你应该实现以下两个函数:
int Alice(std::string S);
- 在单组测试点中,该函数只会被调用一次。
- :长度不超过 的
std::string
数组,表示题目中的 。 - 该函数返回一个满足 的整数 ,表示 Alice 给 Bob 传递的数。
int Bob(std::string T, int X);
- 在单组测试点中,该函数只会被调用一次。
- :长度不超过 的
std::string
数组,表示题目中的 。 - :满足 的整数 ,表示 Alice 给 Bob 传递的数。
- 记 为 的长度,该函数返回一个满足 的整数 ,表示 字符不同的位置。如果 ,返回 0。
在最终评测时,对于单组测试点,上述两个函数会在不同的进程中运行。也就是说,你不能通过全局变量等方式试图在函数间传递信息。
评分方式
本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 0 分,运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 0 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据,及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。禁止通过操作标准输入输出等行为攻击交互库,一经发现,本题直接得 0 分。
如果 Alice 的返回值不是满足 的整数 、Bob 的返回值不是满足 的整数 、Bob 返回的 且满足 ,或者 Bob 返回 且 ,测试点得 0 分;否则得满分。
如果你的程序出现非预期行为(例如在函数里调用 exit
等),你可能会得到 Unknown Error。
样例交互库
下发文件有 grader.cpp
,你可以使用其辅助调试。为了兼容各操作系统,样例交互库不会将两个函数在不同进程中运行,而是在一个进程中依次调用两个函数,如果你使用了全局变量,请注意可能需要的清理工作。
编译
你可以将下发文件的 grader.cpp
复制到你编写的 communication.cpp
同一目录下,然后使用 g++ communication.cpp grader.cpp -std=c++14 -O2 -o grader
编译,该命令会在当前目录下生成可执行文件 grader(Linux / macOS)或 grader.exe(Windows)。
样例交互库输入格式
- 第一行一个字符串 。
- 第二行一个字符串 。
样例交互库输出格式
如果你的通信过程或返回值存在错误,交互库会输出 Wrong Answer
;否则输出 Accepted
。
0101011
0100011
4
提示
对于所有测试数据,记 为 的长度,保证 。
样例输出表示 Bob 函数的正确返回值。
测试点编号 | |
---|---|