P14210 [ROI 2016 Day2] DNA 解码

**译自 [ROI 2016](http://neerc.ifmo.ru/school/archive/2015-2016.html) Day2 T2.** ***[Расшифровка ДНК](http://neerc.ifmo.ru/school/archive/2015-2016/ru-olymp-roi-2016-day2.pdf)***

**这是一个交互式题目。** 在鞑靼斯坦共和国境内进行考古发掘时，科学家们发现了一种未知古生物的遗骸，这种动物生活在数百万年前的喀山附近。与所有生物一样，这种生物的 DNA 分子由核苷酸序列组成，但其中不同种类核苷酸的数量可能与现代生物不同。 为了研究这一发现，科学家们制造了一种特殊的仪器，该仪器可以扫描 DNA 分子的核苷酸序列，并计算其中包含的不同种类核苷酸的数量。不幸的是，DNA 分子无法承受超过 $q$ 次扫描操作，之后就会被破坏。 研究人员希望借助该仪器来确定 DNA 中存在的不同核苷酸的数量 $k$，并找出 DNA 中哪些位置含有相同的核苷酸。科学家们想把核苷酸序列用正整数序列表示为 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le k$)，其中相同的数字表示相同的核苷酸，不同的数字表示不同的核苷酸。 你需要编写一个程序，与测试系统（评测程序）交互，以确定核苷酸的不同种类数量 $k$，以及表示 DNA 核苷酸序列的数列。 ### 交互格式 在程序开始时，系统会提供一个整数 $n$——DNA 分子的长度（$1 \le n \le 3000$）。对于每个测试，参数 $k$（不同核苷酸的数量，$1 < k \le n$）和 $q$（最大允许的查询次数）都是固定的。保证给定的 $q$ 足以解决问题。 这些参数不会直接告知你的程序；评测系统在生成数据时会确保 DNA 序列中存在 $k$ 种不同的核苷酸。 如果你的程序进行了超过 $q$ 次查询，则会立即收到测试结果“Wrong Answer”（答案错误）。 为了进行一次查询，你的程序应输出一行形如： > ? $i$ $j$ 其中 $i$ 与 $j$ 为两个正整数，表示要对 DNA 中第 $i$ 个到第 $j$ 个位置（包含两端）的片段进行扫描，系统将返回一个整数 $p$——该片段中不同核苷酸的种类数（$1 \le i < j \le n$）。 评测系统会在查询结果所在的一行中输出该整数 $p$ 作为响应。 当程序已经获得足够的信息来恢复整个 DNA 序列时，应输出三行内容： 第一行输出： > Ready! 第二行包含 $k$，第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le k$），表示推断出的核苷酸序列。相同的数字应代表相同的核苷酸，不同的数字代表不同的核苷酸。如果存在多个可能的正确序列，则可以输出任意一个。 之后程序必须正常结束。

无

无

### 样例解释 在第一个样例中，$n = 2$。只需一次查询就能判断第一个核苷酸和第二个核苷酸是否相同。 在第二个样例中，$n = 3$。第一次查询的结果表明前两个核苷酸相同；第二次查询的结果表明第三个核苷酸与前两个不同。因此有两种可能的正确答案：$1\ 1\ 2$ 或 $2\ 2\ 1$。 请严格遵守输出格式。每次输出后必须打印一个换行符，并刷新输出缓冲区。为此，在不同编程语言中应使用以下方法： - 在 Pascal 或 Delphi 中使用 `flush(output)`； - 在 C/C++ 中使用 `fflush(stdout)` 或 `cout.flush()`； - 在 Python 中使用 `sys.stdout.flush()`； - 在 Java 中使用 `System.out.flush()`。 ### 数据范围 | 子任务编号 | 分值 | 限制条件 | < | < |必须通过的子任务 | |:--:|:--:|:--:|:--:|:--:|:--:| | | | $n$ | $k$ | $q$ | | | 1 | 20 | $1 \le n \le 300$ | $1 \le k \le 2$ | $q = 72000$ | | | 2 | 25 | $1 \le n \le 300$ | $1 \le k \le n$ | $q = 72000$ | 1 | | 3 | 25 | $1 \le n \le 3000$ | $1 \le k \le n$ | $q = 72000$ | 1 | | 4 | 15 | $1 \le n \le 3000$ | $1 \le k \le n$ | $q = 72000$ | 1–3 | | 5 | 15 | $1 \le n \le 3000$ | $1 \le k \le n$ | $q = 36000$ | 1–4 | 翻译由 ChatGPT-5 完成