这是一个通信(交互)题!
你成功到达了藏宝图上的 X 点,但为了打开宝箱,你首先需要破解密码。宝箱上的标签写着游戏规则:密码是一个长度为 $N$ 的二进制序列,为了找到这个序列,你可以询问以下类型的问题:“$S$ 是隐藏序列的子序列吗?”
一个值为 $S_1, S_2, \dots, S_K$ 的二进制序列 $S$ 被认为是代码 $C$(值为 $C_1, C_2, \dots, C_N$)的子序列,当且仅当 $S$ 可以通过删除 $C$ 中的某些值得到。
形式化地,$S$ 是 $C$ 的子序列,当且仅当存在 $K$ 个下标 $1 \le i_1 < i_2 < \dots < i_K \le N$,使得对于任意 $1 \le j \le K$,都有 $C_{i_j} = S_j$。
如果你成功破解了密码,你将获得一部分宝藏。根据你所询问的最长查询长度,你将获得不等量的宝藏(在本题中,满分为 100 分)。
实现细节
你需要在源代码的开头包含头文件 “grader.h” 并实现以下过程:
vector < int > findSequence (int N);
- 该过程由评测程序恰好调用一次。
- $N$ 是隐藏序列的长度。
- 该函数应返回一个包含 0 和 1 的 STL
vector<int>,即隐藏序列。
你的代码可以包含任意数量的辅助过程,也可以声明全局变量。
你的程序可以多次调用以下函数,只要总过程符合时间限制:
bool isSubsequence (vector < int > S);
- $S$ 是你选择的仅由 0 和 1 组成的 STL
vector<int>。 - 如果 $S$ 是隐藏代码的子序列,该过程返回 1,否则返回 0。
子任务与评分
设 $L$ 为所询问查询中的最长长度。该问题共有 2 个子任务。对于每个子任务,你将获得该子任务中所有测试点得分的最小值:
| 子任务 | 数据范围 | $L$ 的条件 | 分数 |
|---|---|---|---|
| 1 | $7 \le N \le 10$ | $L \le \lfloor \frac{N}{2} \rfloor + 1$ | 20 |
| $L \le \lfloor \frac{3N}{4} \rfloor + 1$ | 15 | ||
| $L \le N$ | 10 | ||
| 2 | $100 \le N \le 200$ | $L \le \lfloor \frac{N}{2} \rfloor + 1$ | 80 |
| $L \le \lfloor \frac{N}{2} \rfloor + 3$ | 72 | ||
| $L \le \lfloor \frac{3N}{4} \rfloor + 1$ | 44 | ||
| $L \le N$ | 24 |
我们用 $\lfloor X \rfloor$ 表示 $X$ 的整数部分。如你所见,如果你询问的任何查询长度超过了 $N$,你将得到 0 分。
交互示例
评测程序调用函数 findSequence(3)。隐藏序列为 0 1 0。你的程序调用函数 isSubsequence([0, 1]) 和 isSubsequence([1, 0]),并对这两个查询都收到肯定回答。然后它调用 isSubsequence([1, 1]),返回否定回答 (0),最后你的程序利用已获得的信息返回序列 [0, 1, 0]。
样例评测程序
你获得了一个包含样例评测程序的压缩包,以帮助你在本地测试代码。它包含一个头文件、一个 grader.cpp 文件以及你需要实现的 sequence.cpp 文件。
评测程序从标准输入读取隐藏序列,然后调用你实现的函数来寻找序列。最后,它会检查返回的序列是否与隐藏序列匹配,如果匹配,它会将你询问过的查询的最大长度打印到标准输出。
评测程序读取的输入格式为: $N$ $C_1 \ C_2 \ C_3 \dots \ C_N$
样例评测程序并非用于正式评分,而是用于辅助你的本地测试。当然,你可以修改它,但你提交的源代码仍需符合格式要求(包含 “grader.h” 并实现 findSequence 函数)。