本文正體字版由OpenCC轉換
這是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