这是一个交互问题。
Anya 聚集了 $$$n$$$ 位国际象棋专家,编号从 $$$1$$$ 到 $$$n$$$,这些专家具有以下属性:
- 对于任何一对玩家,其中一个玩家在与另一个玩家的每场比赛中获胜(并且不会发生平局);
- 传递性不一定成立 - 可能会发生 $$$A$$$ 总是击败 $$$B$$$,$$$B$$$ 总是击败 $$$C$$$ 和 $$$C$$$ 总是击败 $$$A$$$。
为了组织锦标赛,Anya 举办了 $$$n-1$$$ 游戏。在每场比赛中,她都会选择两名球员。其中一名获胜并留下来,而另一名则被取消资格。所有比赛结束后,只剩下一名球员。如果玩家能够赢得锦标赛,则称其为候选大师(请注意,锦标赛的获胜者可能取决于 Anya 在 $$$n-1$$$ 游戏中选择的玩家)。
由于安雅是一个好奇的女孩,她对寻找候选大师很感兴趣。不幸的是,她的时间不多了。为了加快这一过程,她将组织最多$$$2n$$$ simuls(“同时表演”的缩写,其中一名玩家与多名玩家对战)。
在一场模拟中,Anya 恰好选择了一名玩家来与其他一些(至少一名)玩家对战。被选中的玩家赢得了他们在常规比赛中会赢得的所有比赛,同样的情况也适用于输球。同时完成后,安雅只会得知所选玩家获胜的总局数(而不是哪些局数)。在同时进行的比赛中,没有人被取消资格。
你能帮助安雅主持模拟赛并确定候选大师吗?
每对中的获胜玩家可以在模拟之间进行更改,但只能以保留所有先前模拟结果的方式进行更改。这些更改可能取决于您的查询。
互动
首先,陪审团发送一个整数 $$$n$$$ ($$$3 \leq n \leq 250$$$),该整数应该被读取——玩家数量。之后,您的程序可能会提出疑问或报告答案。
要提出查询,请打印“? $$$i \; s_1 s_2 \ldots s_n$$$”(不带引号),其中 $$$i$$$ 是将在模拟中与其他一些玩家对战的玩家的索引。 $$$s$$$ 是一个二进制字符串,表示他们对抗的玩家。 $$$i$$$ 与 $$$s_j = 1$$$ 成立的每个玩家 $$$j$$$ 进行比赛(并且 $$$s_j = 1$$$ 应至少成立一个 $$$1 \leq j \leq n$$$)。请注意,$$$s_i = 0$$$ 必须成立,因为玩家无法与自己对战,否则查询将被视为不正确。
此后,您应该读取一个整数 - 玩家 $$$i$$$ 获胜的人数。
确定答案后,必须打印“! $$$c_1 c_2 \ldots c_n$$$”(不带引号)并终止程序。 $$$c$$$ 是一个二进制字符串,表示候选大师。如果 $$$c_i=1$$$ 成立,则玩家 $$$i$$$ 是候选大师,否则不是。
如果您提出超过 $$$2n$$$ 查询,或者其中一个查询格式错误,则交互会立即终止,并且您的程序会收到错误答案的判决。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
在此问题中,黑客被禁用。
示例
输入 #1
3 1 1 1
输出 #1
? 1 010 ? 2 001 ? 3 100 ! 111
输入 #2
5 0 3 4
输出 #2
? 5 10110 ? 2 10111 ? 1 01111 ! 10000
注意
在第一个示例中,第一个查询描述了一个模拟,其中玩家 $$$1$$$ 与玩家 $$$2$$$(没有其他人)对战。查询的答案是 $$$1$$$,这意味着玩家 $$$1$$$ 赢得了他们玩的唯一一场游戏。我们可以得出结论,$$$1$$$ 击败 $$$2$$$。同样,第二个查询告诉我们 $$$2$$$ 击败 $$$3$$$,第三个查询告诉我们 $$$3$$$ 击败 $$$1$$$。在这种情况下,所有玩家都是候选大师
- 如果 $$$2$$$ 和 $$$3$$$ 先玩,玩家 $$$1$$$ 就可以赢得比赛。 $$$3$$$ 输了并离开,而 $$$2$$$ 留下来。 $$$1$$$ 然后与 $$$2$$$ 比赛并获胜;
- 其他玩家可以以同样的方式获胜。
在第二个示例中,第三个查询描述了玩家 $$$1$$$ 与其他所有玩家对战的模拟。查询的答案是 $$$4$$$,这意味着他们赢得了每场比赛。可以得出结论,玩家 $$$1$$$ 也击败了其他所有玩家。他们永远不会输,因此他们是唯一能够在所有可能的锦标赛结束时留下来的玩家,也是唯一可能的候选大师。