The Riddle of the Sphinx

题意翻译

这是一道交互题，你需要猜测 $n$ 个数 $\{a_1,a_2...a_n\}$ 中的最大值。 保证 $a_i<2^b$ 你每次可以查询 $a_i > y$ 是否成立。 通过不超过 $3(n+b)$ 次操作确定最大值。 请注意，交互器是自适应的。 ---- **交互格式：** 对于查询： ```i y``` 表示询问 $a_i > y$ 是否成立，$y$ 应以 $2$ 进制输入。 对于回答 ```0 x``` 表示最大值为 $x$ ---- **数据范围** $n,b\le 200$

题目描述

What walks on four feet in the morning, two in the afternoon, and three at night? This is an interactive problem. This problem doesn't support hacks. Sphinx's duty is to guard the city of Thebes by making sure that no unworthy traveler crosses its gates. Only the ones who answer her riddle timely and correctly (or get an acc for short) are allowed to pass. As of those who fail, no one heard of them ever again... So you don't have a choice but to solve the riddle. Sphinx has an array $ a_1, a_2, \ldots, a_n $ of nonnegative integers strictly smaller than $ 2^b $ and asked you to find the maximum value among its elements. Of course, she will not show you the array, but she will give you $ n $ and $ b $ . As it is impossible to answer this riddle blindly, you can ask her some questions. For given $ i, y $ , she'll answer you whether $ a_i $ is bigger than $ y $ . As sphinxes are not very patient, you can ask at most $ 3 \cdot (n + b) $ such questions. Although cunning, sphinxes are honest. Even though the array can change between your queries, answers to the previously asked questions will remain valid.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ b $ ( $ 1 \leq n, b \leq 200 $ ). The remaining parts of the input will be given throughout the interaction process.

输出格式

In each round your program must output a single line with an integer $ i $ ( $ 0 \leq i \leq n $ ) and a binary string of length exactly $ b $ denoting the binary representation of $ y $ (most significant bit first). If $ i > 0 $ , this line encodes the question: Is $ a_i $ bigger than $ y $ ?. There should be at most $ 3 \cdot (n+b) $ such lines; after each of them, the interactor will print yes or no in a single line. If $ i = 0 $ , this is the last round of interaction, after which your program should terminate, and $ y $ should be the maximal value among the elements of Sphinx's array. Note that this round does not count to the query limit. Note that the interactor is adaptive. After printing a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see the documentation for other languages. If your solution does not correctly follow the interaction guideline above, it may receive an arbitrary verdict. Otherwise, your program will receive the Wrong Answer judgment if it reports the wrong maximum.

输入输出样例

输入样例 #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

说明

In all examples, the sequence is fixed beforehand. In the first example, the sequence is $ 2, 1, 4, 0, 6 $ . In the second example, the sequence is $ 0, 0, 0, 0 $ . In the third example, the sequence is $ 0 $ . Note that if the interactor was adaptive, then the interaction in the first and the third example would not be sufficient to return the correct value of maximum.

题意翻译

这是一道交互题，你需要猜测 $n$ 个数 $\{a_1,a_2...a_n\}$ 中的最大值。 保证 $a_i<2^b$ 你每次可以查询 $a_i > y$ 是否成立。 通过不超过 $3(n+b)$ 次操作确定最大值。 请注意，交互器是自适应的。 ---- **交互格式：** 对于查询： ```i y``` 表示询问 $a_i > y$ 是否成立，$y$ 应以 $2$ 进制输入。 对于回答 ```0 x``` 表示最大值为 $x$ ---- **数据范围** $n,b\le 200$