编写一个最简单的交互式题目

最近无聊学着编了一下交互式类型的题目。平常网上交互式题目的库文件源码并不多见，在这里把我写的一个题目分享给大家，希望对大家能够有帮助。

题目是一个经典问题，下面所引用的内容是全部的题目描述：

Problem : famous谁是名人

问题描述

小镇上有N(2<=N<=1000)个人，它们从1到N编号。在小镇中，一些人认识另一些人，这种认识的关系是单向的。一个人是名人当且仅当小镇上所有的人都认识他，而除他之外的所有N-1个人他都不认识。假设这个小镇上有且只有一个名人，而你只能询问诸如“A是否认识B”这样的关系。请用不超过2000次的询问找到这个名人。

交互方法

这个题目是一个交互式的题目。我们不提供输入文件，同时也不需要任何输出文件。你需要调用一个我们准备好的库函数来完成所有的操作。你可以得到libfam.ppu和libfam.o两个文件。你需要把这两个文件放在和你的源程序相同的目录下，并在源程序里加入“uses libfam”完成对库文件的引用。我们的库文件提供了以下两个函数和一个过程：

function init:longint;

function know(a,b:longint):boolean;

procedure submit(sol:longint);

init函数只能调用一次。这个函数仅在程序开始时调用，他将返回N值，代表小镇上的人数。

函数know(a,b)返回一个布尔值，它告知了编号为a的人与编号为b的人的关系。如果该函数返回true，则你获得了“a认识b”这一信息；如果该函数返回false，则你获得了“a不认识b”这一信息。该函数可以多次调用，每调用一次称做为一次询问。你的询问次数不能超过2000次，也就是说，该函数最多被调用2000次。

submit过程只能调用一次。这个过程仅在程序结束时调用，用于提交你得到的答案，所带的参数即是名人的编号。调用这个过程将终止你的程序，你可以在日志文件中看到反馈信息。

一个成功交互的例子

下面这一程序代码说明了如何进行正确的操作。除了解释如何使用交互库之外，这个代码不具有任何意义。它不具有提示你询问方法的作用。

program famous;
uses libfam;

var
   n:longint;
   foo,bar:boolean;
begin
   n:=init;         //初始化，得到N的值
   foo:=know(1,3);  //询问1是否认识3
   bar:=know(n-1,4);  //询问n-1是否认识4
   submit(2);       //所提交的答案为2
end.

你如何测试自己的程序

我们为选手准备了一种自我测试的方法。你需要在程序所在目录下建立test.in文件并在此文件下输入相关信息。该文件的构成应该如下：

第一行：一个整数N，代表人数；

第二行到第N+1行：输入一个01矩阵，数字与数字间用空格分隔。其中，第i行的第j个数字表示i是否认识j，“1”表示认识，“0”表示不认识。当i和j相等时，该位置上的0或1没有意义。

一个合法的test.in文件内容可能如下：

3

1 1 0

0 0 0

1 1 1

容易看出，该输入文件表明N=3时的情况，其中第2个人是名人。

你的程序运行时将读取该文件的相关信息并作为此次测试的数据。

程序退出后该目录将生成一个名为famous.log的文件。该文件是日志文件，它详细记录了你的程序与库的交互过程。一些可能出现的情况如下（部分语句较长，用…省略）：

Init called more than once.表明你的程序调用init函数超过1次。

File not exist.表明目录里找不到test.in文件或无法打开该文件。

Error reading N. 读入数字N时出错。该位置可能有其它字符。

N must between 2 and 1000. test.in中输入的N范围不正确。N应该在2到1000之间。

Error reading the matrix.读入01矩阵时出错。该位置可能有其它字符。

Numbers in matrix should…矩阵中出现了除0和1以外的数字。

No famous person found…你的输入数据中没有名人。

Init called successfully.程序调用init成功，继续运行。

Too many queries…你的询问次数超过2000次，程序被迫终止。

Person # not exist.你所询问的人不存在。可能你的参数大于了n或小于1。

You asked a same person: #.你的程序询问了两个相同的人的关系。

No.# : # # TRUE/FALSE依次说明这是第几次询问、询问的两个编号和返回的结果。

Submitted after # queries. 你的程序成功地提交了答案。同时你可以看到你的总询问次数。

Your answer: # 这是你提交的答案。

Congrats, Your answer… 你提交的答案是正确的。你的程序通过了这次测试。

Oops, Your answer is wrong…你提交的答案是错误的。同时你可以看到正确的答案是多少。

评分方法

当你提交的答案与我们的正确答案相符时得10分。我们一共将有10次测试，总共100分。

出现以下情况均不给分：

程序提交的答案错误或没有提交答案；

程序运行时间超过1秒；

程序使用内存空间超过64M；

程序询问次数超过2000次；

程序崩溃或意外退出；

错误访问库导致测试库出错；

程序访问了其它外部文件。

数据规模

对于30%的数据，N<=40；

对于50%的数据，N<=50；

对于70%的数据，N<=200；

对于100%的数据，N<=1000。

下面是这个题目的库文件代码：

unit libfam;

interface

function init:longint;
function know(a,b:longint):boolean;
procedure submit(sol:longint);

implementation

const
   limit=2000;

var
   map:array[1..1000,1..1000]of longint;
   n,ans:longint;
   query:longint=0;
   flog:text;
   inited:boolean=false;

procedure die(msg:string);
begin
   append(flog);
   writeln(flog,msg);
   close(flog);
   halt(1);
end;

procedure wrt(msg:string);
begin
   append(flog);
   writeln(flog,msg);
   close(flog);
end;

function init:longint;
var
   i,j:longint;
   flag:boolean;
begin
   if inited then die('Init called more than once.');

   assign(flog, 'famous.log');
   rewrite(flog);
   close(flog);

   {$i-}
   assign(input,'test.in');
   reset(input);
   if ioresult<>0 then die('File not exist.');
   {$i+}

   {$i-}
   readln(n);
   {$i+}
   if ioresult<>0 then die('Error reading N.');
   if (n<=1) or (n>1000) then die('N must between 2 and 1000.');

   for i:=1 to n do
   for j:=1 to n do
   begin
      {$i-}
      read(map[i,j]);
      {$i+}
      if ioresult<>0 then die('Error reading the matrix.');
      if (map[i,j]<>0) and (map[i,j]<>1) then die('Numbers in matrix should be 0 or 1.');
   end;
   close(input);

   ans:=-1;
   for i:=1 to n do
   begin
      flag:=true;
      for j:=1 to n do if (i<>j) and (map[i,j]=1) then flag:=false;
      for j:=1 to n do if (i<>j) and (map[j,i]=0) then flag:=false;
      if flag then ans:=i;
   end;
   if ans=-1 then die('No famous person found in your input data.');

   wrt('Init called successfully.');
   inited:=true;
   init:=n;
end;

function know(a,b:longint):boolean;
var
   sta,stb,stq:string;
begin
   inc(query);
   str(a,sta);
   str(b,stb);
   str(query,stq);

   if query>limit then die('Too many queries...');
   if (a<1) or (a>n) then die('Person '+sta+' not exist.');
   if (b<1) or (b>n) then die('Person '+stb+' not exist.');
   if a=b then die('You asked a same person: '+sta+'.');

   if map[a,b]=1 then wrt('No.'+stq+': '+sta+' '+stb+' TRUE')
                 else wrt('No.'+stq+': '+sta+' '+stb+' FALSE');
   know:=(map[a,b]=1);
end;

procedure submit(sol:longint);
var
   sts,stq,sta:string;
begin
   str(sol,sts);
   str(query,stq);
   str(ans,sta);
   wrt('');
   wrt('Submitted after '+stq+' queries.');
   wrt('Your answer: '+sts);
   if sol=ans then wrt('Congrats, Your answer is correct!')
              else wrt('Oops, Your answer is wrong! The answer should be '+sta+'.');
   halt(0);
end;

end.

下面是一个数据生成器。在实际测试中使用的数据文件名并不是“test.in”，防止选手直接读入数据。因此，库的代码中读入部分也要做相应的改动。数据未经过加密，因此这种方法不能彻底防止选手作弊。使用Cena测试时，测试库需要放在Cena目录的compilersbin下。测试库还需要一些其它的改动，比如log文件可以改为只输出该测试点是否得分的信息（在Cena中设置成用答案正确时应该输出的log文件与实际输出的log文件进行对比）。

const
   c:array[0..9]of longint=
   (2,30,40,47,50,172,200,532,797,1000);
var
   a:array[1..1000,1..1000]of longint;
   i,j,k,n,t:longint;
begin
   randseed:=13875;
   for k:=0 to 9 do
   begin
      assign(output,'fam23z.'+chr(k+48)+'.in');
      rewrite(output);
      n:=c[k];
      for i:=1 to n do
      for j:=1 to n do a[i,j]:=random(2);
      t:=random(n)+1;
      for i:=1 to n do a[i,t]:=1;
      for i:=1 to n do a[t,i]:=0;
      writeln(n);
      for i:=1 to n do
      begin
         for j:=1 to n do write(a[i,j],' ');
         writeln;
      end;
      close(output);
   end;
end.

一个满分程序的代码可能如下：

uses libfam;
var
   i,t,n:integer;
begin
   n:=init;
   t:=1;
   for i:=2 to n do if know(t,i) then t:=i;
   submit(t);
end.