406895: GYM102606 B Binary String

This is an interactive problem.

Cuber QQ, who was the master of subsequence, has recently come up with a new string game which immediately received much attention, well, at least your attention.

The rules of this game are straightforward. Cuber QQ will generate a binary string of length $$$n$$$, i.e., a string consisting of $$$n$$$ characters '0' and '1'. He will tell you the length of binary string he has generated. After that, he gives you some opportunities to ask him a binary string whose length is at most $$$\left \lfloor \frac{n}{2} \right \rfloor + 1$$$ , he will answer if your binary string is a subsequence (not necessarily continuous) of his binary string.

You can ask at most $$$1023$$$ questions if your binary string is a subsequence of Cuber QQ's binary string, and after that, you will get one and only one chance to make your guess of Cuber QQ's binary string. Unless you answer is correct, you will lose the game.

A non-empty sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly zero) elements.

In the first line, you are given one positive integer $$$n$$$ ($$$1\le n\le 1000$$$) — the length of the binary string generated by Cuber QQ.

To ask a question, print "? $$$s$$$" , $$$s$$$ ($$$1 \le |s| \le \left \lfloor \frac{n}{2} \right \rfloor + 1$$$) is a binary string that you are interested whether it is a subsequence of the binary string generated by Cuber QQ.

The interactor will respond with a single integer:

• 0 — the binary string you gave is not a subsequence of the binary string generated by Cuber QQ.
• 1 — the binary string you gave is a subsequence of the binary string generated by Cuber QQ.

When you are ready to answer, print "! $$$s$$$", $$$s$$$ is the binary string that you guess Cuber QQ generated. Note that the interactor doesn't print anything in response to you printed answer, so you have to terminate the program instantly.

You can ask at most $$$1024$$$ questions (including the last one) per test case.

After printing every query do not forget to put an end to 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 documentation for other languages.

If the interactor responds with "-1" instead of "0" or "'1", it means that you've made an invalid query. Exit immediately after receiving "-1" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution tries to read from a closed stream.

2

1

1

0

1

0

0

0

? 0

? 1

? 00

? 01

? 10

? 11

! 01