Huge Kingdom: Atcoder

AtCoder

IDs8pc_4_h

Time4000ms

Memory256MB

Difficulty—

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. ![image](https://atcoder.jp/img/s8pc-4/18f55c17e4feefd6794b69a1b91d5e6f.png) Please detect the structure of $Atcoder$ as few questions as possible. ## Constraints * $N$=200 * $Atcoder$ contains $N-1$ roads and this kingdom is connected. * All cases were made randomly. ## 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. ## 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$. [samples]

Samples

Input #1

This case is $N=4$. This case is not include because this is not $N=200$.  

N=4
0 1
1 2
1 3

Output #1

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:  

![image](https://atcoder.jp/img/s8pc-4/8d26e2d0a3fd5e4cc24efe8d21296341.png)

  
This question is not always meaningful.

API Response (JSON)

{
  "problem": {
    "name": "Huge Kingdom: Atcoder",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "s8pc_4_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Huge kingdom: $Atcoder$ contains $N$ towns and $N-1$ roads. This kingdom is connected.  \n  \nYou have to detect the kingdom's road.  \nIn order to detect, You can ask this form of questions.  \n\n*   You ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments