UOJ Logo Universal Online Judge

UOJ

#251. 【Rujia Liu's Present 7】Guess the missing number

附件下载 统计

现在有一个 1n 的排列 a1,a2,,an,但是 an 被隐藏了。

你需要通过以下询问来确定 an 的值:

  • 询问:给出 i,j 满足 i[1,n),j[0,10],询问 ai 的二进制表示第 j 位。

定义一个数 x 二进制表示的第 0 位为最低位,第 1 位为次低位,以次类推。

交互格式

本题是一道交互式试题,你的程序需要和交互程序通过标准输入输出进行交互。每次向标准输出打印了一行后,请立即刷新缓冲区

对于每个测试点,首先,交互库将给出一个整数 T 表示测试数据组数。

对于每组测试数据:

交互库首先给出一个整数 n 表示排列长度。

接下来你可以输出若干行和交互库交互:

  1. 输出 Ask i j,满足 1i<n,0j10,表示询问 ai 的第 j 位。
    • 交互库会返回一个整数 01 表示这个二进制位。
  2. 输出 Answer x,表示你认为 an=x
    • 交互库不会返回信息,并开始下一组数据的交互或结束评测。

对于每组测试数据,你至多使用 Ask 操作 2222 次。

样例

交互库输出 选手程序输出
1  
4  
  Ask 1 0
0  
  Ask 1 1
1  
  Ask 2 2
1  
  Ask 3 0
1  
  Ask 3 1
0  
  Answer 3

explanation

对于这唯一一组数据,a1=2,a2=4,a3=1,a4=3

数据范围与提示

本题只有一个测试点,保证 1T25,2n1000

时间限制:2s

空间限制:512MB

来源

Uva Online Judge,经典问题,题目作者刘汝佳。

特别鸣谢:Md. Mahbubul Hasan