这是一个交互问题。
Couti厌倦了学习,于是他打开电脑,开始玩益智游戏。
很久以前,男孩发现了一个长度为 $$$n$$$ 的序列 $$$s_1, s_2, \ldots, s_n$$$,由一个狡猾的交互者保存。它仅由 $$$0$$$ 和 $$$1$$$ 组成,$$$1$$$ 的数量为 $$$t$$$。除了 $$$n$$$ 和 $$$t$$$ 之外,男孩对这个序列一无所知,但他可以尝试通过交互器进行一些查询来找出它。
我们定义了一种称为翻转的操作。翻转 $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) 意味着对于 [l,r]$$$ 中的每个 $$$x \,将 $$$s_x$$$ 更改为 $$$1-s_x$$$。
在每个查询中,男孩可以给交互者两个整数 $$$l,r$$$ 满足 $$$1 \leq l \leq r \leq n$$$ 并且交互者将翻转 $$$[1,r]$$$ 或 $$$[l,n]$$$ (两个结果具有相同的概率,并且交互者做出的所有决策都是相互独立的,有关更多详细信息,请参阅注释部分)。每次操作后,交互器都会告诉当前 $$$1$$$ 的数量。请注意,每次操作后顺序不会恢复。
帮助男孩在不超过 $$$10000$$$ 的交互中找到原始序列。
“奇怪的传说,愚蠢的游戏。”他想。然而,经过多次尝试,他仍然坚持下去。你能帮助他打败这场比赛吗?
互动
交互从包含两个整数 $$$n$$$ 和 $$$t$$$ 的行开始($$$1 \leq n \leq 300$$$, $$$0 \leq t \leq n$$$)——序列的长度和其中 $$$1$$$ 的数量。
之后就可以进行查询了。
要进行查询,请打印一行“? l r” ($$$1 \leq l \leq r \leq n$$$),然后刷新输出。
每次查询后,读取单个整数 $$$t$$$ ($$$-1 \leq t \leq n$$$)。
- 如果$$$t=-1$$$,这意味着你没有查询,你应该立即终止你的程序,那么你会得到错误的答案,否则判断结果将是不确定的,因为你将与一个封闭的流交互。
- 如果 $$$t \geq 0$$$,则表示序列中 $$$1$$$ 的当前数量。
当你找到原始序列时,打印一行“!s”,刷新输出并终止。将 $$$s_1, s_2, \ldots, s_n$$$ 作为二进制字符串打印,并且不打印中间的空格。
如果您不打印任何内容或忘记刷新输出,您的解决方案将超出空闲限制。
要刷新,您需要在打印查询和行结束后立即执行以下操作:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
对于 hack,请使用以下格式:
在第一行也是唯一一行中,打印一个非空二进制字符串。它的长度将为$$$n$$$,并将被视为$$$s_1、s_2、\ldots、s_n$$$。
例如,示例对应的测试包含行“0011”。
示例
输入 #1
4 2 2 2 0
输出 #1
? 1 1 ? 1 1 ? 3 4 ! 0011
注意
对于第一个查询 $$$1,1$$$,交互器应该翻转 $$$[1,1]$$$ 或 $$$[1,4]$$$。它选择翻转$$$[1,4]$$$,因此序列变成了1100。
对于第二个查询 $$$1,1$$$,交互器应该翻转 $$$[1,1]$$$ 或 $$$[1,4]$$$。它再次选择翻转$$$[1,4]$$$,因此序列变成了0011。
对于第三个查询 $$$3,4$$$,交互器应该翻转 $$$[1,4]$$$ 或 $$$[3,4]$$$。它选择翻转$$$[3,4]$$$,因此序列变成了0000。
问:交互者如何在 $$$[1,r]$$$ 和 $$$[l,n]$$$ 之间进行选择?真的是随机的吗?
答:交互器将使用秘密伪随机数生成器。只有 $$$s$$$ 和您的查询将被散列并用作种子。因此,如果您对同一个秘密字符串给出相同的查询序列两次,您将得到相同的结果。除此之外,您可以考虑完全随机的选择,就像掷一枚均匀的硬币一样。您不需要(也不应该)利用确切的生成器来解决这个问题。