这是NOI的第一道交互式题，貌似很复杂，但实际上不难，只要仔细分析。
分析可以发现，对于两个人a,b，只要a,b均不是裁判，Ask(a,b,0)，如果回答Yes则a,b同属于一队，否则a,b不同属于一队，所以Ask(a,b,0)一定等于Ask(b,a,0)。因此我们可以以此判断出裁判，如果Ask(a,b,0)不等于Ask(b,a,0)，则a,b中有一个是裁判。于是我们可以分别正着和倒着问一圈，找出唯一的一组Ask(a,b,0)不等于Ask(b,a,0)，则a为裁判，而且可以判断出b所属队伍，进而判断出所有人所属队伍，这样每个人都只问了两遍。
晕，找不到C++版的交互库，害我还得写Pascal，真不舒服。
{
* Problem: NOI2002 child
* Author: Guo Jiabao
* Time: 2009.5.19 20:05
* State: Solved
* Memo: 交互式提问 逻辑判断
}
program child;
uses childlib;
const
MAX=1000;
var
N,M,T:integer;
belong,ansp,ansn:array [1..MAX] of integer;
procedure solve;
var
i,a,b,k:integer;
begin
GetNM(N,M);
T:=N+M+1;
for i:=1 to T do
begin
a:=i;b:=i+1;
if i=T then b:=1;
ansn[i]:=Ask(a,b,0);
end;
for i:=T downto 1 do
begin
a:=i;b:=i-1;
if i=1 then b:=T;
ansp[i]:=Ask(a,b,0);
end;
for i:=1 to T do
begin
a:=i;b:=i+1;
if i=T then b:=1;
if ansn[a]<>ansp[b] then
begin
belong[a]:=2;
if ansn[a]=1 then
belong[b]:=0
else
belong[b]:=1;
k:=b;b:=b+1;if b>T then b:=1;
while a<>b do
begin
if ansn[k]=1 then
belong[b]:=belong[k]
else
belong[b]:=1-belong[k];
k:=b;b:=b+1;if b>T then b:=1;
end;
break;
end;
end;
end;
procedure print;
var
i:integer;
begin
for i:=1 to T do
Answer(belong[i]);
end;
begin
solve;
print;
end.
<h2><span class="mw-headline">调皮的小孩 </span></h2>
【问题描述】
一群小孩在草坪上玩游戏，十分开心，一个喜欢猎奇的过路人走过来问他们：
“孩子们，你们在玩什么游戏呢？”
“我们中有一个人当裁判，剩下的人分成两队：星星队有N个人，月亮队有M个人。如果你猜对了谁是裁判，我就告诉你玩的是什么游戏。”
“好啊。不过，总得给我点提示吧？”
“那当然。你可以问我们某人是不是属于某队，而不能问某人是不是裁判。被问到的星星队的队员总是告诉你正确的答案；月亮队的队员总是告诉你错误的答案；而裁判，在你向他问奇数次的时候他会告诉你正确的答案，偶数次的时候会告诉你错误的答案。”
“哦，明白了。可以随便提问题吗？”
“你不许问任何人关于他自己的问题。例如，你不许问我：‘你是不是星星队的？’你也不能向任何一个人询问两次关于同一个人的问题。例如，你 曾问过我丁丁是不是星星队的，你就不能再问我丁丁是不是月亮队的。最后，请你尽量不要问同一个人太多的问题，因为他还要接着玩呢，没时间老回答你的问题。 ”
过路人很聪明，不仅猜出了谁是裁判，还说出了剩下的每个人是哪个队的。你也来试试吧！
【交互】
本题是一道交互式题目，你的程序应当和测试库进行交互，而不得访问任何文件。测试库提供三个函数：GetNM，Ask，Answer，它们的作用和用法如下：
-
GetNM(N,M)必须首先调用，用它来获得正整数N,M的值。(2<=N+M<=500)。
-
Ask(Child1,Child2,T)的作用是询问。其中1<=Child1,Child2<=N+M+1,且 Child1≠Child2。T非0即1，T为0表示星星队，为1表示月亮队。即询问小孩Child1“小孩Child2是不是属于T队”。若函数返回 1，表示Child1回答说“是”；若函数返回0，表示Child1回答“否”。
-
Answer(Ans)用来告诉测试库你猜的答案。参数Ans的值为0，1，2。为0表示星星队，为1表示月亮队，为2表示裁判。你应当连续调用 N+M+1次本过程，从1号开始到N+M+1号为止依次说明每个小孩的角色，注意仅有一个裁判。调用完N+M+1次本过程后，测试库会终止你的程序，切记 你的程序不得自行终止。
【一个成功交互的例子】
函数调用
返回值
说明
GetNM(N,M)
N=1, M=1
星星队和月亮队各有一名队员
Ask(1,2,0)
0
问小孩1：“小孩2是不是星星队的？”答：“否”
Ask(2,1,0)
1
问小孩2：“小孩1是不是星星队的？”答：“是”
Ask(3,1,1)
0
问小孩3：“小孩1是不是月亮队的？”答：“否”
Answer(2)
无
小孩1是裁判。
Answer(1)
无
小孩2是月亮队的。
Answer(0)
无
小孩3是星星队的。
【对Pascal程序员的提示】
你的程序应当使用下列语句引用测试库：
uses childlib;
测试库提供的函数/过程原型为：
procedure GetNM(var N,M:integer);
function Ask(Child1,Child2,T:integer):integer;
procedure Answer(Ans:integer); 【对C/C++程序员的提示】
你应当建立一个工程，把文件childlib.o包含进来，然后在程序头加上一行：
- include “childlib.h”
void GetNM(int *N, int *M);
int Ask(int Child1, int Child2, int T);
void Answer(int Ans); 【评分方法】
如果你的程序有下列情况之一，得0分：
-
访问了任何文件(包括临时文件)或者自行终止；
-
非法调用库函数；
-
让测试库异常退出。
否则每个测试点你的得分按这样来计算：
- 你只猜对了裁判是谁而没有完全猜对其余孩子所在的队。在这种情况下，如果你对某个小孩提了三个以上（含三个）的问题，那么你只能得40%的分，否则可以得60%的分；
- 你猜对了裁判是谁以及其余所有孩子所在的队。在这种情况下，如果你对某个小孩提了三个以上（含三个）的问题，那么你只能得70%的分，否则你将得到该测试点的满分。
- 在工作目录下建立一个文本文件child.in，文件第一行包括两个整数N，M，第二行包括N+M+1个数（数的取值为0,1,2），第k个数为小孩k所在的队，0表示星星队，1表示月亮队，2表示裁判。样例输入文件存放在用户目录中。
- 执行你的程序，此时测试库会产生输出文件child.log。
- 如果程序正常结束，child.log的第一行包含一个整数P，即被询问次数最多的小孩被问了多少次（超过10次的按10次计）。第二 行包含N+M+1个数，依次为你的程序对每个孩子的猜测结果。如果程序非法退出，则child.log会记录如下内容:“Abnormal Termination”。
- 在工作目录下执行程序check，会在屏幕上看到你的得分。
上次修改时间 2017-05-22