UOJ Logo Universal Online Judge

UOJ

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

附件下载 统计

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

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

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

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

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

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

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

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

交互格式

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

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

对于每组测试数据:

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

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

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

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

样例

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

数据范围与提示

本题只有一个测试点,满足 $1\leq T\leq 100, 2\leq n+m\leq 500$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

来源

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

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