最高分数:$1500$ 积分
你必须探测王国的道路。
为了检测,您可以提出这种形式的问题。
请尽可能少地检测$Atcoder$的结构。
问题陈述
巨大的王国:$Atcoder$ 包含 $N$ 城镇和 $N-1$ 道路。这个王国是相连的。你必须探测王国的道路。
为了检测,您可以提出这种形式的问题。
- 您可以输出字符串$S$。 $S$ 的长度必须为$N$ 并且字符串$S$ 的字符必须由'$0$' 或'$1$' 表示。
- 计算机根据您输出的字符串将城镇涂成白色或黑色。
- 如果$S$ 的第$i$ 个字符是“0”,则计算机将$i$ 城镇绘制为白色。
- 如果$S$ 的第$i$ 个字符是“1”,则计算机将$i$ 城镇绘制为黑色。
- 请考虑一个无向图 $G$。
- 对于每条边,计算机进行以下处理:如果两端都涂成黑色,则计算机将这条边添加到$G$中。
- 计算机返回值$x$:每个连通分量的“树直径”$^2$之和。
输入、输出
这是一个反应性问题。第一个输入如下:
$N$
- $N$ 是 $Atcoder$ 中的城镇数量。
接下来,你可以提问。
问题必须采用以下形式:
? $S$$S$ 是一个字符串。问题陈述中所写的 $S$ 的平均值。 $S$ 的长度必须为$N$。
问题答案如下:
$x$问题陈述中写入的 $x$ 的平均值。
最后,您的程序必须输出如下:
! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$此输出意味着您的程序检测到 $Atcoder$ 的所有道路。
$(a_i,b_i)$ 表示 $a_i$ 和 $b_i$ 之间有一条路。
您可以按任意顺序输出道路,但必须在单行上输出答案。
约束
- $N$=200
- $Atcoder$ 包含 $N-1$ 条道路,并且这个王国是相连的。
- 所有病例都是随机制作的。
评分
设问题数为 $L$。- 如果 $L > 20000$,$score$ = $0$ 分
- 如果 $18000 < L ≦ 20000$,则 $score$ = $200$ 分
- 如果 $5000 < L ≦ 18000$,$score$ = $650-L/40$ 点
- 如果 $4000 < L ≤ 5000$,$score$ = $800-L/20$ 点
- 如果 $2000 < L ≦ 4000$,$score$ = $1400-L/5$ 分
- 如果 $1200 < L ≦ 2000$,则 $score$ = $1500-L/4$ 分
- 如果 $700 < L ≤ 1200$,则 $score$ = $1850-L/2$ 分
- 如果 $L ≤ 700$,则 $score$ = $1500$ 分
有 $5$ 个案例,因此每个案例的分数为 $score/5$。
示例输入
这种情况是$N=4$。不包括这种情况,因为这不是 $N=200$。N=4 0 1 1 2 1 3
示例输出
交互示例如下:| 从计算机输入 | 输出 |
|---|---|
| 4 | |
| ? 1111 | |
| 4 | |
| ? 1101 | |
| 4 | |
| ? 1001 | |
| 0 | |
| ? 1100 | |
| 1 | |
| ? 1011 | |
| 0 | |
| ! (0,1) (1,2) (1,3) |
在此示例中,$Atcoder$ 的结构如下:
这个问题并不总是有意义的。