← 返回题目列表

Codeforces · 2013/C

C. 密码破解

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

迪玛什得知曼苏尔向朋友写了一些关于他的非常不愉快的内容,因此他决定不惜一切代价找出他的密码,并查明他到底写了什么。

Mansur 相信他的密码的强度,他表示他的密码 — 是一个长度为 $$$n$$$ 的二进制字符串。他还准备回答迪玛希的以下类型的问题:

Dimash 说出一个二进制字符串 $$$t$$$,Mansur 回答 $$$t$$$ 是否是其密码的子字符串。

帮助迪玛希在不超过 $$$2n$$$ 操作中找到密码;否则曼苏尔就会明白其中的伎俩并停止与他交流。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

互动

在每个测试用例的开头,首先读取 $$$n$$$ ($$$1 \le n \le 100$$$) — 二进制字符串的大小。然后继续猜测。

要猜测每个字符串 $$$s$$$,您最多可以进行以下类型的 $$$2n$$$ 查询:

- “?t”,其中 $$$t$$$ 是一个二进制字符串,例如 ($$$1 \le |t| \le n$$$)。

响应此查询,如果 $$$t$$$ 是 $$$s$$$ 的子字符串,则您将收到 $$$1$$$,否则将收到 $$$0$$$。

收到答案后,按以下格式输出单个字符串:

- "!s",其中 $$$s$$$ 是大小为 $$$n$$$ 的二进制字符串。

之后,继续解决下一个测试用例。

如果您尝试错误或超过 $$$2n$$$ 尝试限制,您将收到 $$$-1$$$ 而不是答案,并得到错误答案的判决。在这种情况下,您的程序应立即终止以避免未定义的判决。

输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到解决方案“挂起”的判决。要刷新缓冲区,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客:

要使用 hack,请使用以下测试格式:

第一行应包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。

每个测试用例的第一行应包含一个数字 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串的长度。第二行应包含大小为 $$$n$$$ 的二进制字符串。

示例

输入 #1

4
3

0

0

1

4

4

2

输出 #1

? 00

? 000

? 010

! 010

! 1100

! 0110

! 10

注意

在第一个示例中,给出了字符串 $$$010$$$。因此,对质疑的答复如下:

"? 00" $$$00$$$ 不是 $$$010$$$ 的子串,所以答案是 $$$0$$$。

"? 000" $$$000$$$ 不是子字符串,所以答案是 $$$0$$$。

"? 010" $$$010$$$ 是一个子字符串,所以答案是 $$$1$$$。

在第二个示例中,字符串为 $$$1100$$$,在第三个示例中为 $$$0110$$$,在第四个示例中为 $$$10$$$。