QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100 互動

#4728. 隐藏序列

统计

这是一个通信(交互)题!

你成功到达了藏宝图上的 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 函数)。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.