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.