NOI 2002 調皮的小孩

這是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包含進來,然後在程序頭加上一行:

        <li>include “childlib.h”</li>
      

    測試庫提供的函數原型爲:

    void GetNM(int N, int M);

    int Ask(int Child1, int Child2, int T);

    void Answer(int Ans); 【評分方法】

    如果你的程序有下列情況之一,得0分:

  • 訪問了任何文件(包括臨時文件)或者自行終止;

  • 非法調用庫函數;
  • 讓測試庫異常退出。

    否則每個測試點你的得分按這樣來計算:

    1. 你只猜對了裁判是誰而沒有完全猜對其餘孩子所在的隊。在這種情況下,如果你對某個小孩提了三個以上(含三個)的問題,那麼你只能得40%的分,否則可以得60%的分;
    2. 你猜對了裁判是誰以及其餘所有孩子所在的隊。在這種情況下,如果你對某個小孩提了三個以上(含三個)的問題,那麼你只能得70%的分,否則你將得到該測試點的滿分。
    【你如何測試自己的程序】
    1. 在工作目錄下建立一個文本文件child.in,文件第一行包括兩個整數N,M,第二行包括N+M+1個數(數的取值爲0,1,2),第k個數爲小孩k所在的隊,0表示星星隊,1表示月亮隊,2表示裁判。樣例輸入文件存放在用戶目錄中。
    2. 執行你的程序,此時測試庫會產生輸出文件child.log。
    3. 如果程序正常結束,child.log的第一行包含一個整數P,即被詢問次數最多的小孩被問了多少次(超過10次的按10次計)。第二 行包含N+M+1個數,依次爲你的程序對每個孩子的猜測結果。如果程序非法退出,則child.log會記錄如下內容:“Abnormal Termination”。
    4. 在工作目錄下執行程序check,會在屏幕上看到你的得分。

相關日誌