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,会在屏幕上看到你的得分。

相关日志