loj#P2766. 「ROI 2017 Day 1」四轴飞行器编程

「ROI 2017 Day 1」四轴飞行器编程

题目描述

译自 ROI 2017 Day1 T1. Программирование квадрокоптеров

本题的数据是 HeRaNO 配的,有锅请找他

控制四轴飞行器的程序是一个长度为 nn 的字符串,仅由 () 组成,( 表示爬升 11 米,) 表示下降 11 米。这 nn 条指令依次编号为 1n1\ldots n
如果飞行器开始时在地上,完整执行了一遍程序后,飞行器刚好回到地面,并且在整个过程中,程序没有让它往地底下钻(换句话说,当飞行器在地面上时,仍然接到了 ) 指令),这个程序就是正确的。例如,()(())((())) 是正确的程序。((( 是不正确的,因为程序结束后飞行器位于地面上方 33 米处,())( 也是不正确的,因为第三条指令要求飞行器往地底下钻。
现在飞行器里有一个正确的程序。你想知道这个程序,但这个程序没法导出。还好,飞行器支持一种特殊调试模式。在此模式下,装有程序的四轴飞行器可以回答请求。每个请求包含两个整数 l,r(1lrn)l, r(1\le l\le r\le n)。对于每个请求,它会回答 Yes\texttt{Yes}No\texttt{No},表示:如果将原程序只留下指令 ll 到指令 rr,程序还是否正确。你希望使用调试模式来得到完整程序。

请编写一个程序,与模拟调试模式的交互器进行交互,并最终输出完整程序。

交互过程

你可以编写一个函数 getProgram() 并在程序开始包含 grader.h 来完成交互过程。该函数无返回值,也没有参数。或者直接编写一个完整程序来完成交互。

你需要先从标准输出流中获得一个整数 nn,表示四轴飞行器程序中的命令条数。

你可以向标准输出中输出询问和回答,形式如下:

  • 对于询问一段程序是否合法,你需要先输出一个字符 ?,后跟两个整数 l,rl,r,表示如果只留下指令 ll 到指令 rr 的程序,字符,整数之间用一个空格隔开。如果只留下指令 ll 到指令 rr 程序仍然正确,交互器会向标准输出中输出 Yes\texttt{Yes},否则会输出 No\texttt{No}
  • 对于回答整个程序,你需要先输出一个字符 !,后跟一个序列 c1c2cnc_1c_2\ldots c_n,表示这个程序。! 与序列之间用一个空格隔开。其中 cic_i 只能是 ()

在回答之后,你应该结束程序。保证四轴飞行器程序在交互过程中不会改变。

交互过程中,你的询问数不能超过一个值 kk

数据范围与提示

子任务编号 分值 nn kk
11 2121 2n162\le n\le 16 k=150k=150
22 2828 2n1002\le n\le 100 k=104k=10^4
33 2626 2n10002\le n\le 1000
44 2525 2n5×1042\le n\le 5\times 10^4 k=105k=10^5