3065 「ROI 2016 Day2」DNA 解码

译自 ROI 2016 Day2 T2. Расшифровка ДНК

某古生物的 DNA 是一条包含 $n$ 个脱氧核苷酸的序列，但是该生物的 DNA 中核苷酸的种类可能与现代生物不同。

某种机器可以扫描 DNA 中连续的一段，并给出该段中包含多少种核苷酸。然而你只能使用这种机器至多 $q$ 次。

试求出该 DNA 中包含多少种核苷酸（假设包含 $k$ 种）。此外，你还需要给这 $k$ 种核苷酸编号（比如 GMP→1，AMP→2），然后给出用编号形式表示的完整 DNA 序列（比如 ATGC->2314）。请注意，你给出的 DNA 序列可以与标准答案中的不同，你只需保证：同种核苷酸使用编号相同，且不同种核苷酸编号不同。

交互方式

本题使用标准输入输出进行交互。

首先，你的程序可以从 stdin 读取一个整数 $n$。

你可以通过输出 "$\;!\texttt{?}\ i\ j\;!$" 来查询 DNA 的第 $i\sim j$ 个核苷酸中有多少种不同的核苷酸。交互器在接收到你的查询后，会在 stdin 中给出答复。

如果你得出了答案，请输出 Ready!，下一行输出 $k$，再下一行输出 $n$ 个整数，表示 DNA 序列。

你需要在输出你要执行的命令后刷新 stdout 的缓冲区来将命令发送到交互器。 - 如果你使用 C++ 且使用 iostream 系列，可以输出 std::flush 或 std::endl 来刷新缓冲区。 - 如果你使用 C/C++ 且使用 cstdio，那么请调用标准库函数 fflush(stdout) 来刷新。 - 如果你使用 Python，请使用 sys.stdout.flush()。 - 如果你使用 Java，请使用 System.out.flush()。

$$ \begin{array}{l|l} \hline \rm stdin &\rm stdout\ \hline \tt 2 & \ &\tt ?\ 1\ 2 \ \tt 2 & \ &\tt Ready!\ &\tt 2\ &\tt 1\ 2\ \hline \end{array}

$$

2
2

? 1 2
Ready!
2
1 2

$$ \begin{array}{l|l} \hline \rm stdin &\rm stdout\ \hline \tt 3 & \ &\tt ?\ 1\ 2 \ \tt 1 & \ &\tt ?\ 1\ 3 \ \tt 2 & \ &\tt Ready!\ &\tt 2\ &\tt 1\ 1\ 2\ \hline \end{array} $$

3
1
2

? 1 2
? 1 3
Ready!
2
1 1 2