#1146. ddd和斑马

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: nocriz🦆

题目描述

注意:这是一道交互题! 如果你不知道你应该怎么做,不要恐慌,下面会解释。如果不懂也可以在群里问。

ddd在动物园,看到了一只斑马。斑马的条纹是一个长度为 1000 的 01 串。
你想要知道这个串,但ddd并不打算就这么简单地告诉你真相,他计划和你玩一个游戏。

输入格式

你的任务是实现一个函数:

std::string guess()

该函数应当返回ddd得到的 01 串。
你可以调用以下函数来向ddd询问该串的相关信息:

int query(int l, int r)

你必须保证 ,该函数有 的概率返回 中数字 的个数 ,另 的概率返 回 中的一个随机整数。请注意:对一组 你只能询问至多一次。 你可以参考样例交互库对上述描述进行理解。

输出格式

本题不需要你输出任何内容。你也不能进行输出,不然获得0分。

数据范围与提示

本题共包括 个测试点,我们会对你的函数进行不超过 次调用,我们允许你出现不超过 次答 案错误的情况,否则你将得到 分。否则,不妨设你最多一次调用了 query 函数,必须小于等于,不然你依然获得0分。

在下发文件中,我们提供了 guess.h, grader.cpp, guess.cpp 三个文件,你最终提交的代码应当包含在 guess.cpp 中,并包含头文件 guess.h
如果你想要命令行编译你的代码,应当执行:g++ guess.cpp grader.cpp -o guess -O2 -std=c++11

你可以使用下发的文件进行本机测试,获得自己程序的大概运行次数。