UOJ Logo Universal Online Judge

UOJ

#253. 【Rujia Liu's Present 7】Team star, Team moon

附件下载 统计

一群小孩在草坪上玩游戏,十分开心,一个喜欢猎奇的过路人走过来问他们:

“孩子们,你们在玩什么游戏呢?”

“我们中有一个人当裁判,剩下的人分成两队:星星队有 n 个人,月亮队有 m 个人。如果你猜对了谁是裁判,我就告诉你玩的是什么游戏。”

“好啊。不过,总得给我点提示吧?”

“那当然。你可以问我们某人是不是属于某队,而不能问某人是不是裁判。被问到的星星队的队员总是告诉你正确的答案;月亮队的队员总是告诉你错误的答案;而裁判,在你向他问奇数次的时候他会告诉你正确的答案,偶数次的时候会告诉你错误的答案。”

“哦,明白了。可以随便提问题吗?”

“你不许问任何人关于他自己的问题。例如,你不许问我:‘你是不是星星队的?’你也不能向任何一个人询问两次关于同一个人的问题。例如,你曾问过我丁丁是不是星星队的,你就不能再问我丁丁是不是月亮队的。最后,请你尽量不要问同一个人太多的问题,因为他还要接着玩呢,没时间老回答你的问题。”

过路人很聪明,不仅猜出了谁是裁判,还说出了剩下的每个人是哪个队的。你也来试试吧!

交互格式

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

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

对于每组测试数据:

交互库首先输出两个正整数 n,m 表示两只队伍的人数,所有人用 1,2,,n+m+1 编号。

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

  1. Ask C1 C2 T 表示向 C1 询问 C2 是否属于队伍 TT=0 表示星星队,T=1 表示月亮队。
    • 如果小孩回答“是”,交互库返回 1,否则返回 0
  2. Answer R1 R2 ... Rn+m+1 表示你认为的每个人的队伍,其中 Ri=0 表示第 i 个人属于星星队,Ri=1 表示第 i 个人属于月亮队,Ri=2 表示第 i 个人是裁判。
    • 交互库不会返回,并立刻结束这组数据的评测。

对于每组测试数据,你至多向每个人提两个问题,并且不能向一个人问两次关于同个人的问题,并且不能像某个人提关于他自己的问题。

样例

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

数据范围与提示

本题只有一个测试点,满足 1T100,2n+m500

时间限制:2s

空间限制:512MB

来源

Uva Online Judge,NOI2002,题目作者刘汝佳。

特别鸣谢:李益明,毛子青, Md. Mahbubul Hasan