最近无聊学着编了一下交互式类型的题目。平常网上交互式题目的库文件源码并不多见，在这里把我写的一个题目分享给大家，希望对大家能够有帮助。
题目是一个经典问题，下面所引用的内容是全部的题目描述：
Problem : famous
谁是名人
问题描述
Matrix67所在的小镇上有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.
Matrix67原创
转载请注明出处
