← 返回题目列表

AtCoder · s8pc_4_h

H. 巨大的王国:Atcoder

中文机器翻译题面 查看原题
最高分数:$1500$ 积分

问题陈述

巨大的王国:$Atcoder$ 包含 $N$ 城镇和 $N-1$ 道路。这个王国是相连的。

你必须探测王国的道路。
为了检测,您可以提出这种形式的问题。
  • 您可以输出字符串$S$。 $S$ 的长度必须为$N$ 并且字符串$S$ 的字符必须由'$0$' 或'$1$' 表示。
  • 计算机根据您输出的字符串将城镇涂成白色或黑色。
  • 如果$S$ 的第$i$ 个字符是“0”,则计算机将$i$ 城镇绘制为白色。
  • 如果$S$ 的第$i$ 个字符是“1”,则计算机将$i$ 城镇绘制为黑色。
  • 请考虑一个无向图 $G$。
  • 对于每条边,计算机进行以下处理:如果两端都涂成黑色,则计算机将这条边添加到$G$中。
  • 计算机返回值$x$:每个连通分量的“树直径”$^2$之和。
例如,当$S$="11001111"并且王国的结构是这样时,计算机返回10。
请尽可能少地检测$Atcoder$的结构。

输入、输出

这是一个反应性问题。
第一个输入如下:

$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$ 的结构如下:

这个问题并不总是有意义的。