一群小孩在草坪上玩游戏,十分开心,一个喜欢猎奇的过路人走过来问他们:
“孩子们,你们在玩什么游戏呢?”
“我们中有一个人当裁判,剩下的人分成两队:星星队有 $n$ 个人,月亮队有 $m$ 个人。如果你猜对了谁是裁判,我就告诉你玩的是什么游戏。”
“好啊。不过,总得给我点提示吧?”
“那当然。你可以问我们某人是不是属于某队,而不能问某人是不是裁判。被问到的星星队的队员总是告诉你正确的答案;月亮队的队员总是告诉你错误的答案;而裁判,在你向他问奇数次的时候他会告诉你正确的答案,偶数次的时候会告诉你错误的答案。”
“哦,明白了。可以随便提问题吗?”
“你不许问任何人关于他自己的问题。例如,你不许问我:‘你是不是星星队的?’你也不能向任何一个人询问两次关于同一个人的问题。例如,你曾问过我丁丁是不是星星队的,你就不能再问我丁丁是不是月亮队的。最后,请你尽量不要问同一个人太多的问题,因为他还要接着玩呢,没时间老回答你的问题。”
过路人很聪明,不仅猜出了谁是裁判,还说出了剩下的每个人是哪个队的。你也来试试吧!
交互格式
本题是一道交互式试题,你的程序需要和交互程序通过标准输入输出进行交互。每次向标准输出打印了一行后,请立即刷新缓冲区。
对于每个测试点,交互库首先会输出一个整数 $T$ 表示测试数据组数。
对于每组测试数据:
交互库首先输出两个正整数 $n,m$ 表示两只队伍的人数,所有人用 $1,2,\cdots,n+m+1$ 编号。
接下来你可以输出若干行指令和交互库交互:
Ask C1 C2 T
表示向 $C1$ 询问 $C2$ 是否属于队伍 $T$,$T=0$ 表示星星队,$T=1$ 表示月亮队。- 如果小孩回答“是”,交互库返回 $1$,否则返回 $0$。
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