[ROI 2017] 四轴飞行器编程 (Day 1)

Luogu

IDLGP10649

Time1000ms

Memory512MB

DifficultyP4

2017交互题Special JudgeO2优化ROI（俄罗斯）

## Background ### 题面系统中隐藏了一个只含 `(` 和 `)` 的**合法括号字符串** $S$。你每次可以向系统询问一个 $S$ 的子区间 $S[l,r]$，系统会返回这个子区间是否是一个合法括号字符串。请编写一个程序，与系统进行交互，并最终输出 $S$ 的具体信息。关于合法括号字符串的定义： - 空串是合法括号字符串。 - 设 $\text{A}$ 是合法括号字符串，那么 $\text{(A)}$ 也是合法括号字符串。 - 设 $\text{A}$ 和 $\text{B}$ 是合法括号字符串，那么 $\text{AB}$ 也是合法括号字符串。 ### 交互过程 ~~你可以编写一个函数 `getProgram()` 并在程序开始包含 `grader.h` 来完成交互过程。该函数无返回值，也没有参数。~~ 请直接编写一个完整程序来完成交互。你需要先从标准输出流中获得一个整数 $n$，表示系统字符串的长度。你可以向标准输出中输出询问和回答，形式如下： - 对于询问一段子串是否合法，你需要先输出一个字符 `?`，后跟两个整数 $l,r$，表示选择 $S[l,r]$，字符，整数之间用一个空格隔开。如果 $S[l,r]$ 为合法括号字符串，交互库会向标准输出中输出 $\texttt{Yes}$，否则会输出 $\texttt{No}$； - 对于回答整个程序，你需要先输出一个字符 `!`，后跟一个长度为 $n$ 的合法括号字符串。`!` 与序列之间用一个空格隔开。在回答之后，你应该结束程序。保证四轴飞行器程序在交互过程中不会改变。交互过程中，你的询问数不能超过一个值 $k$。 [samples] ## Note #### 【数据范围】 | 子任务编号 | 分值 | $2 \le n \le $ | $k=$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $21$ | $16$ | $150$ | | $2$ | $28$ | $100$ | $10^4$ | | $3$ | $26$ | $10^3$ | $10^4$ | | $4$ | $25$ | $5 \times 10^4$ | $10^5$ |

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2017] 四轴飞行器编程 (Day 1)",
    "description": {
      "content": "",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10649"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "## Background\n\n### 题面\n\n系统中隐藏了一个只含 `(` 和 `)` 的**合法括号字符串** $S$。\n\n你每次可以向系统询问一个 $S$ 的子区间 $S[l,r]$，系统会返回这个子区间是否是一个合法括号字符串。\n\n请编写一个程序，与系统进行交互，并最终输出 $S$ 的具体信息。\n\n关于合法括号字符串的定义：\n\n- 空串是合法括号字符串。\n\n- 设 $\\text{A}$ 是合...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments