这是一个交互问题。
给你一个未知的二进制字符串$$$s$$$$$$^{\text{*}}$$$,长度为$$$n$$$。函数 $$$f(l, r)$$$ 定义为通过以下操作形成的数组 $$$a$$$ 中不同元素的数量:
- 设 $$$S$$$ 为子串 $$$s_l s_{l+1} \ldots s_r$$$。设 $$$m$$$ 为子字符串的长度。
- 我们从一个空数组 $$$a$$$ 开始。
- 对于$$$S$$$的第$$$i$$$第$$$(0 \le i \lt m)$$$左循环旋转$$$^{\text{†}}$$$,我们将反转次数$$$^{\text{‡}}$$$表示为$$$x_{i}$$$。
- 对于每个$$$i$$$,使得$$$0 \le i \lt m$$$,将$$$x_{i} \mbox{ mod } m$$$附加到数组$$$a$$$,其中$$$u \mbox{ mod } v$$$表示$$$u$$$除以$$$v$$$的余数。
要确定 $$$s$$$,您可以提出一些问题。在每个问题中,您可以选择 $$$2$$$ 整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 并获取 $$$f(l, r)$$$ 的值。每个查询都会产生 $$$\dfrac{n}{r-l+1}$$$ 的成本。请注意,成本不一定必须是整数。
您必须确定隐藏的二进制字符串,同时将查询的总成本保持在 $$$\mathbf{max(30,3\cdot n)}$$$ 以内。您最多可以进行 $$$\mathbf{2}$$$ 猜测。
$$$^{\text{*}}$$$二进制字符串仅包含字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$。
$$$^{\text{†}}$$$设一个二进制字符串$$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$。 $$$s$$$ 的第 $$$k$$$ 左循环定义为 $$$t_{k} \; = \; s_{k+1}s_{k+2}\cdots s_{n}s_{1}s_{2}\cdots s_{k}$$$。
$$$^{\text{‡}}$$$设字符串$$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$。 $$$s$$$ 的反转次数定义为索引对的数量 $$$i,j \; (1 \le i \lt j \le n)$$$,使得 $$$s_{i} \gt s_{j}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — 未知字符串 $$$s$$$ 的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
互动
要提出问题,请按以下格式输出一行(不带引号)
- "$$$\texttt{? l r}$$$" ($$$1 \leq l \leq r \leq n$$$)
猜测字符串$$$s$$$($$$s$$$的长度必须为$$$n$$$),按以下格式输出单行(不带引号)
- “$$$\texttt{!s}$$$”
猜测字符串不算作查询。
之后,如果您的字符串正确,则继续下一个测试用例,或者如果它是最后一个测试用例则终止程序。
交互器是 不 自适应,意味着答案在参与者提出问题之前就已知,并且不依赖于参与者提出的问题。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
要进行破解,请使用以下格式。
第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
每个测试用例的第一行应包含$$$n$$$ ($$$2 \le n \le 3000$$$),$$$s$$$ 的长度。
每个测试用例的第二行应包含 $$$s$$$,一个长度为 $$$n$$$ 的二进制字符串。
所有测试用例的 $$$n$$$ 总和不应超过 $$$3000$$$。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
3 5 1 1 1 1 3 3 0 1 8 0 1
输出复制
? 1 5 ? 2 5 ? 3 5 ! 00000 ? 1 3 ! 100 ! 001 ! 00000000 ! 10101010
注意
在示例交互中,输入和输出包含空行,以使交互者响应与查询保持一致。这些空行不会出现在实际的输入和输出中。
在第一个测试用例中,隐藏字符串是 $$$s =$$$ 00000。在这里,自从 0 无法创建任何反转,数组 $$$a$$$ 对于所有子字符串将始终为 $$$[0]$$$。因此,$$$f(l, r)$$$ 对于所有查询都会返回 $$$1$$$。
这里我们进行了 $$$3$$$ 查询。
第一个查询是 $$$f(1,5)$$$ 返回 1 — 此查询的成本为 $$$\dfrac{5}{5-1+1} = 1$$$。
第二个查询是 $$$f(2,5)$$$,它返回 1 — 此查询的成本为 $$$\dfrac{5}{5-2+1} = \dfrac{5}{4}$$$。
第三个查询是 $$$f(3,5)$$$,它返回 1 — 此查询的成本为 $$$\dfrac{5}{5-3+1} = \dfrac{5}{3}$$$。
所有这些查询后的总成本 $$$= 1 + \dfrac{5}{4} + \dfrac{5}{3} = \dfrac{47}{12}$$$ 小于 $$$\max(30, 3\cdot n) = 30$$$。
在此之后,我们猜测 $$$s =$$$ 00000,交互器返回 $$$1$$$,表明猜测正确。然后我们转向下一个测试用例。
在第二个测试用例中,隐藏字符串是 $$$s =$$$ 001.
我们进行查询 $$$f(1,3)$$$,它返回 3。此查询的成本为 $$$\dfrac{3}{3-1+1} = 1$$$。
查询的总成本为 $$$1$$$,小于 $$$\max(30, 3\cdot n) = 30$$$。
然后我们猜测 100,交互器返回 0,表明它不正确。
我们猜测 001,交互器返回 1,说明我们的猜测是正确的。然后我们转向下一个测试用例。
对于第三个测试用例,隐藏字符串是 $$$s =$$$ 10101010.