← 返回题目列表

Codeforces · 2037/E

E. Kachina 最喜欢的二进制字符串

中文机器翻译题面 查看原题

这是一个交互问题。

Kachina 挑战你猜出她最喜欢的二进制字符串$$$^{\text{*}}$$$ $$$s$$$,长度为$$$n$$$。她将 $$$f(l, r)$$$ 定义为 $$$s_l s_{l+1} \ldots s_r$$$ 中 $$$\texttt{01}$$$ 的子序列 $$$^{\text{†}}$$$ 的数量。如果两个子序列是通过删除原始字符串中不同位置的字符而形成的,则认为它们是不同的,即使所得子序列由相同的字符组成。

要确定$$$s$$$,你可以问她一些问题。在每个问题中,您可以选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l < r \leq n$$$) 并向她询问 $$$f(l, r)$$$ 的值。

在询问 Kachina 不超过 $$$n$$$ 问题后确定并输出 $$$s$$$。然而,也有可能无法确定$$$s$$$。在这种情况下,您需要改为报告 $$$\texttt{IMPOSSIBLE}$$$。

从形式上来说,如果在询问了 $$$n$$$ 问题后,$$$s$$$ 总是有多个可能的字符串,那么无论提出什么问题,$$$s$$$ 都是不可能确定的。请注意,如果在存在最多 $$$n$$$ 查询序列将唯一确定二进制字符串时报告 $$$\texttt{IMPOSSIBLE}$$$,您将得到错误答案判决。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^4$$$) — $$$s$$$ 的长度。

保证所有测试用例的$$$n$$$总和不超过$$$10^4$$$。

互动

要提出问题,请按以下格式输出一行(不包含引号)

- "$$$\texttt{? l r}$$$" ($$$1 \leq l < r \leq n$$$)

当您准备好打印答案时,按以下格式输出一行

- 如果无法确定$$$s$$$,则输出“$$$\texttt{!IMPOSSIBLE}$$$”
- 否则,输出 "$$$\texttt{!s}$$$"

之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。打印答案不算作查询。

交互器不具有自适应性,这意味着答案在参与者提出问题之前就已知,并且不依赖于参与者提出的问题。

如果您的程序对一个测试用例进行超过 $$$n$$$ 查询,您的程序应立即终止以接收“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则,您可能会得到超出空闲限制的判决。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要进行破解,请使用以下格式。

第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) – 测试用例的数量。

每个测试用例的第一行应包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^4$$$) — $$$s$$$ 的长度。

以下行应包含 $$$s$$$,长度为 $$$n$$$ 的二进制字符串。

所有测试用例的 $$$n$$$ 总和不应超过 $$$10^4$$$。

示例

输入 #1

2
5

4

0

1

2

2

0

输出 #1

? 1 5

? 2 4

? 4 5

? 3 5

! 01001

? 1 2

! IMPOSSIBLE

注意

在第一个测试用例中:

在第一个查询中,您向 Kachina 询问 $$$f(1, 5)$$$ 的值,她在输入流中以 $$$4$$$ 进行响应。

在第二个查询中,您向 Kachina 询问 $$$f(2, 4)$$$ 的值。由于字符串 $$$\texttt{100}$$$ 中没有 $$$\texttt{01}$$$ 的子序列,因此她在输入流中以 $$$0$$$ 进行响应。

在提出了 $$$4$$$ 问题后,您将 $$$\texttt{01001}$$$ 报告为 $$$s$$$,并且它是正确的。

在第二个测试用例中:

在第一个查询中,您向 Kachina 询问 $$$f(1, 2)$$$ 的值,她在输入流中以 $$$0$$$ 进行响应。请注意,这是您可以提出的唯一明确的问题。

但是,请注意字符串 $$$00$$$ 和 $$$11$$$ 的答案都是 $$$0$$$,并且无法区分两者。因此,我们报告不可能。

请注意,此示例仅用于演示交互格式。不保证所提供的查询是最佳的或唯一确定答案。但是,可以证明存在最多 $$$5$$$ 查询的序列,该序列唯一确定样本测试用例 $$$1$$$。