这是一个交互问题。此问题不支持 hack。
狮身人面像的职责是守卫底比斯城,确保没有不值得的旅行者跨过城门。只有及时正确回答她的谜语(或者简称为acc)的人才能通过。至于那些失败的人,再也没有人听说过他们……
所以你别无选择,只能解决这个谜题。 Sphinx 有一个严格小于 $$$2^b$$$ 的非负整数数组 $$$a_1, a_2, \ldots, a_n$$$,并要求您找到其元素中的最大值。当然,她不会给你看数组,但她会给你$$$n$$$和$$$b$$$。由于不可能盲目地回答这个谜语,你可以问她一些问题。对于给定的 $$$i, y$$$,她会回答你 $$$a_i$$$ 是否大于 $$$y$$$。由于狮身人面像不太有耐心,你最多可以问 $$$3 \cdot (n + b) $$$ 这样的问题。
狮身人面像虽然狡猾,但很诚实。尽管数组可能会在查询之间发生变化,但之前提出的问题的答案仍然有效。
输入
第一行包含两个整数 $$$n$$$ 和 $$$b$$$ ($$$1 \leq n, b \leq 200$$$)。输入的其余部分将在整个交互过程中给出。
互动
在每一轮中,程序必须输出一行,其中包含整数 $$$i$$$ ($$$0 \leq i \leq n$$$) 和长度恰好为 $$$b$$$ 的二进制字符串,表示 $$$y$$$ 的二进制表示形式(最高有效位在前)。
如果 $$$i > 0$$$,则此行编码问题:$$$a_i$$$ 是否大于 $$$y$$$?。最多应该有 $$$3 \cdot (n+b)$$$ 这样的行;在每一个之后,交互器都会在一行中打印 yes 或 no。
如果$$$i = 0$$$,这是最后一轮交互,之后你的程序应该终止,并且$$$y$$$应该是Sphinx数组元素中的最大值。请注意,本轮不计入查询限制。
请注意,交互器是自适应的。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
如果您的解决方案未正确遵循上述交互指南,它可能会收到任意判决。否则,如果您的程序报告了错误的最大值,则会收到错误答案判断。
示例
输入 #1
5 3 yes no no no no yes
输出 #1
5 101 5 110 4 100 3 101 2 001 1 000 0 110
输入 #2
4 3 no no no no
输出 #2
1 000 2 000 3 000 4 000 0 000
输入 #3
1 1
输出 #3
0 0
注意
在所有示例中,顺序都是预先固定的。
在第一个示例中,序列为 $$$2, 1, 4, 0, 6$$$。
在第二个示例中,序列为 $$$0, 0, 0, 0$$$。
在第三个示例中,序列是 $$$0$$$。
请注意,如果交互器是自适应的,那么第一个和第三个示例中的交互将不足以返回正确的最大值。