← 返回题目列表

Codeforces · 1687/B

B. 铁路系统

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

这是一个交互问题。

在加奈子和守矢神社的直接监督下,幻想乡的铁路系统终于完工了。 GSKR(幻想乡铁路)由 $$$n$$$ 个车站组成,并有 $$$m$$$ 双向轨道连接这些车站。第 $$$i$$$ 轨道的长度为 $$$l_i$$$ ($$$1\le l_i\le 10^6$$$)。由于预算限制,尽管两个车站之间可能有不止一条轨道,但铁路系统可能无法连接。

铁路系统的价值定义为其所有轨道的总长度。铁路系统的最大(或最小)容量定义为所有当前功能系统的全跨越森林中的最大(或最小)值。

简而言之,图的全生成林是与给定图具有相同连接性的生成林。

Kanako 的模拟器只能处理不超过 $$$2m$$$ 的查询。模拟器的输入是长度为 $$$m$$$ 的字符串 $$$s$$$,由字符 0 和/或 1 组成。如果 $$$s_i=$$$ 1,模拟器将假定第 $$$i$$$ 轨道功能正常。然后设备将告诉 Kanako 系统在模拟状态下的最大容量。

Kanako 想知道在模拟器的帮助下所有轨道都能正常运行的系统的最小容量。

铁路系统的结构是预先确定的。换句话说,交互器不具有适应性。

输入

输入的第一行也是唯一一行包含两个整数 $$$n,m$$$ ($$$2 \leq n \leq 200$$$, $$$1\le m \le 500$$$) — 车站和轨道的数量。

互动

通过读取 $$$n,m$$$ 开始交互。

要进行查询,请打印“? $$$s$$$”(不带引号,$$$s$$$ 是长度为 $$$m$$$ 的字符串,由字符 0 和/或 1 组成)。然后您应该从标准输入中读取我们的响应——模拟状态下系统的最大容量。

如果您的程序进行了无效查询或已用完尝试次数,则交互器将立即终止,并且您的程序将得到错误答案。

要给出最终答案,请打印“!$$$L$$$”(不带引号,$$$L$$$ 是所有轨道功能正常的系统的最小容量)。请注意,给出此答案不计入 $$$2m$$$ 查询的限制。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

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

黑客

输入的第一行必须包含两个整数 $$$n,m$$$ ($$$2 \leq n \leq 200$$$, $$$1\le m \le 500$$$) — 车站和轨道的数量。

接下来的 $$$m$$$ 输入行必须恰好包含 $$$3$$$ 以空格分隔的整数 $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i\ne v_i$$$, $$$1 \leq l_i \leq 10^6$$$) — 第 $$$i$$$ 个轨道的端点和长度。

示例

输入 #1

5 4

0

5

9

7

输出 #1

? 0000

? 1110

? 1111

? 1101

! 7

注意

这是示例的图表,满足 $$$l_i=i$$$。