H - Huge Kingdom: Atcoder 解説 /

実行時間制限: 4 sec / メモリ制限: 256 MB

Max Score: $1500$ Points

Problem Statement

Huge kingdom: $Atcoder$ contains $N$ towns and $N-1$ roads. This kingdom is connected.

You have to detect the kingdom's road.
In order to detect, You can ask this form of questions.
  • You can output a string $S$. Length of $S$ must be $N$ and The character of string $S$ must be represented by '$0$' or '$1$'.
  • Computer paint the towns with white or black according to the character string you output.
  • If $i$-th character of $S$ is '0', computer paint town $i$ white.
  • If $i$-th character of $S$ is '1', computer paint town $i$ black.
  • Please consider an undirected graph $G$.
  • For each edge, computer do the following processing: If both ends painted black, computer adds this edge to $G$.
  • Computer returns value $x$: sum of "diameter of tree"$^2$ about each connected components.
For example, when $S$="11001111" and the kingdom's structure is this, computer returns 10.
Please detect the structure of $Atcoder$ as few questions as possible.

Input, Output

This is a reactive problem.
The first input is as follows:

$N$
  • $N$ is number of towns in $Atcoder$.

Next, you can ask questions.
The question must be in the form as follows:
? $S$
$S$ is a string. The mean of $S$ written in the problem statement. Length of $S$ must be $N$.

The answer of question is as follows:
$x$
The mean of $x$ written in the problem statement.

Finally, your program must output as follows:
! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$
This output means your program detects all roads of $Atcoder$.
$(a_i,b_i)$ means there is a road between $a_i$ and $b_i$.

You can output roads any order, but you must output the answer on a single line.

Constraints

  • $N$=200
  • $Atcoder$ contains $N-1$ roads and this kingdom is connected.
  • All cases were made randomly.

Scoring

Let the number of questions be $L$.

  • If $L > 20000$, $score$ = $0$ points
  • If $18000 < L ≦ 20000$, $score$ = $200$ points
  • If $5000 < L ≦ 18000$, $score$ = $650-L/40$ points
  • If $4000 < L ≦ 5000$, $score$ = $800-L/20$ points
  • If $2000 < L ≦ 4000$, $score$ = $1400-L/5$ points
  • If $1200 < L ≦ 2000$, $score$ = $1500-L/4$ points
  • If $700 < L ≦ 1200$, $score$ = $1850-L/2$ points
  • If $L ≦ 700$, $score$ = $1500$ points

There is $5$ cases, so points of each case is $score/5$.

Sample Input

This case is $N=4$. This case is not include because this is not $N=200$.
N=4
0 1
1 2
1 3

Sample Output

Sample interaction is as follows:
Input from computer Output
4
? 1111
4
? 1101
4
? 1001
0
? 1100
1
? 1011
0
! (0,1) (1,2) (1,3)

In this sample, structure of $Atcoder$ is as follows:

This question is not always meaningful.
この問題はマラソン問題です。 writer解が必ずしも満点であるとは限りません。できるだけ良い点数を取りましょう。
配点： $1500$ 点

問題文

Atcoder王国は、$N$個の街と$N-1$個の道から成り立っています。
また、その王国は連結であります。つまり「木」です。

あなたは、その王国の構造を当てなければなりません。
ここでいう構造というのは、それぞれの道がどの番号の街とどの番号の街をつないでいるのか、という事です。

さて、あなたは構造を当てるにおいて、以下のような質問ができます。
  • 文字列$S$($N$文字)を出力する。その時、$S_i$=1の時、$i$番目の街を黒く塗り、$S_i$=0の時、$i$番目の街を白く塗ることを意味する。
  • $N$頂点のグラフ$G$を考える。
  • 王国の道の両端の街が、両方とも黒く塗られている場合、グラフ$G$にその辺を追加する。
  • グラフ$G$の各連結成分についての、「木の直径」を2乗した値の総和が返される。
例えば、以下のような構造で、S="11001111"の場合、以下のような値が返ってくる。
その時、できるだけ少ない質問回数で王国の構造を当てなさい。

入出力

これはリアクティブ問題である。
最初、以下のように入力される。

$N$
  • 1行に、Atcoder王国の街の個数$N$が与えられる。

次に、あなたは以下の様な質問をすることができる。
質問は、以下のような形式ですることができる。
? $S$
$S$は、質問する文字列（＝街の塗り方）である。$S$は$N$文字でなければならない。

また、質問は、以下のように返される。
$d$
質問で出力された文字列$S$について、問題文で与えられた作り方でグラフ$G$を作る。
グラフ$G$の各連結成分についての、「木の直径」を2乗した値の総和が返される。

最後に、あなたは以下のような出力をしなければならない。
! $(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$を直接つなぐ道があることを示す。

ただし、出力する道の順番はどのようなものでも良い。また、それぞれの道を出力する方法は2通りあるが、【(1,2),(2,1)など】その出力の順番もどれでもよい。

制約

  • $N$ = $200$
  • Atcoder王国には$N-1$本の道があり、連結である
  • Atcoder王国の街の番号は$0$以上$N-1$以下である。(0-based)
  • ケースはランダムに作られた。

テストケースの生成方法

以下の操作を、街が全て連結（連結成分が１つ）になるまで繰り返す。
  • ランダムな街の番号$u$, $v$を選ぶ。
  • もし、今の状態で街$u$から街$v$まで、いくつかの道路を使ってたどり着けない場合、街$u$と$v$の間に道路を結ぶ。
  • そうでない場合、何もしない。最初の操作に戻る。

得点

あなたが質問した回数を$L$とする。その時得点の理論値は以下のようになる。

  • $L > 20000$の時、$0$点
  • $18000 < L ≦ 20000$の時、$200$点
  • $5000 < L ≦ 18000$の時、$650-L/40$点
  • $4000 < L ≦ 5000$の時、$800-L/20$点
  • $2000 < L ≦ 4000$の時、$1400-L/5$点
  • $1200 < L ≦ 2000$の時、$1500-L/4$点
  • $700 < L ≦ 1200$の時、$1850-L/2$点
  • $L ≦ 700$の時、$1500$点

ケースは5個あるので、得点は理論値を$5$で割った値になる。

入力例

このケースは、$N=4$である。実際のケースではそのようなものは存在しない。（制約を満たしていないため）
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)

その王国は、以下の図のような構造をしています。

ただし, 必ずしも意味のある質問をしているとは限らない。
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されます。