← 返回题目列表

Codeforces · 1081/F

F. 棘手的交互器

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

这是一个交互问题。

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$$$ 和您的查询将被散列并用作种子。因此,如果您对同一个秘密字符串给出相同的查询序列两次,您将得到相同的结果。除此之外,您可以考虑完全随机的选择,就像掷一枚均匀的硬币一样。您不需要(也不应该)利用确切的生成器来解决这个问题。