贪心算法的一个出人意料的应用

    IBM Ponder This上个月的题目比较有趣:我在心里面想一个2到166之间的整数(包括2和166),你的任务是用尽可能少的是非问句(我只能回答是或者否)猜出这个数除1以外的最小约数是多少。
    (1) 寻找一种策略使得在最坏情况下猜到答案的询问次数最少。
    (2) 寻找一种策略使得在平均情况下猜到答案的期望询问次数最少。

    第一个问题很容易回答。虽然2到166之间的整数一共有165个,但它们的最小约数(以后我们说的“最小约数”都是指的不包括1的最小约数)只有38种。因此,事实上你只需要用二分法在38个可能的答案当中找出一个就可以了。由于2^5=32,2^6=64,因此最坏情况下需要6次询问才能保证猜到。
    真正困难的是后面一个问题:要想让平均猜测次数尽可能少,我们该从哪里入手呢?

Read more…

趣题:经典二分问题的一个扩展

    SETI@home可以在杂乱的射电数据中搜寻独特的讯号,你能在大街上的嘈杂声中清晰分辨出一个尖细的女声大叫“亚美蝶”。这些现象都表明,有时对集合里的所有元素进行整体考察可以很快找出我们所要找的个体。去年我们搞合唱比赛时,我又想到了一个绝佳的例子:你可以在合唱声中清楚地听到是否有人跑调。考虑这样一个问题,假如合唱团里有一个人唱歌始终走调,但我听不出来是谁走调,只能听出当前正在唱歌的人中是否有唱走调了的人。那么,我如何才能迅速地揪出那个唱走调的人?利用经典二分法,我们可以在log2(n)次合唱后找出唱走调了的人。每一次,我都把剩下的人平均分成两组,然后选其中一组来合唱:如果听不到走调的声音,这一组的人就全部过关;如果听到有人走调,那另一组里的人都可以被排除了。递归地对剩下的组进行同样的操作,log2(n)次操作后必定可以找出那个唱歌走调的人。
    现在的问题变得有些麻烦了。假如我们知道合唱队里有一个人唱歌爱跑调,但他不是总会跑调。具体地说,他只有1/2的概率唱错,但其余1/2的时间里他却唱得很准。现在,传统的二分法不再适用了,因为没有走调声已经不能起到排除的作用了。你能想出多少种可行的算法来找出那个人?下面提出一些可行的方法,你认为哪种方法更好?你能求出这些算法所需要的检测次数的期望值各是多少吗?

    1. 不断地随机生成一个大小为n/2的子集并对其进行检测,直到某次不能通过检测为止,然后递归地对其进行操作。
    2. 所选的子集大小为n/2是最优的吗?把上面这种方法的n/2改成n/a,常数a的最优值是多少?
    3. 检测次数的期望值还可以更小吗?我们想到,每次都重新生成一个新的集合其实并不科学,新集合本身是否包含老鼠屎也是得碰碰运气的。因此,对方法1的一个合理改进是:把集合平均划分为两个部分,交替对它们进行检测直到某次检测没通过为止,然后对该组递归操作下去。这种方法真的比前两种好吗?它所需要的期望次数是多少?
    4. 尝试对方法3进行改进。如果把集合平均划分成3份并循环进行检测,效果会不会更好一些?

    1. 选取的子集有1/2的概率覆盖了我们要找的那个人,子集里有他而他这次恰好又唱走调了则有1/4的概率。因此,不管规模有多大,平均需要4次才能把规模缩小一半。因此,检测次数的期望值为4*log2(n)。为了方便比较期望值的大小,后面的答案我们一律表示成一个常数乘以log2(n)的形式。
    2. 类似地,平均需要2a次检测才能把规模缩小到原来的1/a,因此总共花费的检测次数为2a*log2(n)/log2(a)。对函数求导,可得当a为e时函数值达到最小。此时的检测次数期望值为2e*log2(n)/log2(e)≈3.7683 * log2(n)。
    3. 这个就经典了。设方法3里把规模缩小一半所需要的检测的期望次数为m,下面我们来看m应该等于多少。把n个人平均分成两组,我们要找的老鼠屎有1/2的概率在第一组,有1/2的概率在第二组。因此,第一次就测出问题来有1/4的可能,第二次就测出问题也有1/4的可能。对于剩下的1/2种情况,局面变得又和最开始一样,只是平均需要的检测次数比原来多了2。根据期望值的定义,有m=(1/4)*1 + (1/4)*2 + (1/2)*(m+2),解得m=3.5。总的检测次数就是3.5 * log2(n),它比前面两种方法都要好。你可能不同意上面求m的方法。这没啥,如果你不断对m进行迭代,你会发现展开出来的式子就是最标准的期望值定义。
    4. 类似地,有m=(1/6)*1 + (1/6)*2 + (1/6)*3 + (1/2)*(m+3),解得m=5。于是,把规模缩小到原来的1/3平均需要5次检测,总的检测次数为5*log2(n)/log2(3)≈3.1546 * log2(n)。

题目来源:IBM Ponder This Dec07
原文还从熵的角度探寻了问题的最优算法,感兴趣的读者可以去看一看

计算机与拼图游戏:探讨一个交互式问题

    似乎MM都很喜欢拼图游戏。如果MM过生日你不知道送她什么,送她一副拼图是一个不错的选择(事实上原来我也曾干过这事)。如果你失恋了,或者挂科了,或者这个月没饭钱了,或者怀疑自己的性取向,感到很郁闷的时候,静下心来玩一玩拼图游戏可以让你暂时忘掉烦恼。当你最终完成整个拼图时,你会有前所未有的成就感。当然,只有那些有耐心的人才觉得拼图有趣,像我这样的人肯定拼个十几二十分钟就觉得烦了。计算机搞久了的人往往都很没耐心,同一个操作反复执行的次数多了就觉得很烦,心里总会想这种机械操作交给傻B计算机去做该多省事啊。有时我会想,计算机是否有什么牛B算法可以用来解决拼图问题。今天我们要研究的是,如何把拼图游戏描述成一个信息学问题,计算机是否有更高效的算法来解决这个问题。
    传统的拼图一共有w*h个正方形小块,最终将拼成一个w*h的矩形图案。我们大致有以下两种依据来确定一个小块的位置:根据这一小块上的图案来确定它在整幅图片中的位置,或者从形状上观察这一小块可以和其它哪些块拼接。于是,拼图游戏变成了这样一种交互式的问题:允许你询问某一块是否在指定的位置,或者某两块是否相连,你如何尽早地完成整个拼图。具体地说,你可以:

  • 询问拼块A是否在(x,y)上,交互库返回yes/no
  • 询问拼块A和拼块B是否相连,交互库返回yes/no

    有时候,你并不能把拼图完全当作一个顶点最大度为4的无向图。多数情况下两个拼块只能按某一个方向上的某一种顺序相连。为了更贴近拼图游戏的真实情况,我们可以假定,对于第二个问题如果返回的是yes,则交互库还会告诉你A应该接在B的什么方向。现在的问题是,完成整个拼图最少需要多少次询问?
    假如拼图共有n块,询问的次数不会超过O(n^2)。对于每一个拼块,我都像傻B一样挨着挨着询问“它是不是在这里”,O(n^2)次询问可以保证我完成整副拼图。我们希望知道,是否有算法可以使用O(nlogn)甚至更少的询问次数?

    答案是否定的。对于拼图问题,计算机并没有英明到哪里去,它也只能像傻B一样一个一个去试。我们下面将证明,不管你怎么努力,询问次数再怎么也不会低于O(n^2)。首先我们需要说明的是,问题2实际上并不能带给我们多大的帮助。

      
    如上图,我们把整个拼图划分成一个一个的“十字架”,并且挖掉每个十字架正中间的那个格子(深灰色的格子)。注意到关于这种划分的三个重要性质:

  • 每个浅灰色的格子最多与一个深灰色的格子相邻
  • 任何两个深灰色的格子都不相邻
  • 深灰色的格子共有n/5个(可能有常数级别的偏差)

    现在,假如整个拼图里只剩这些被挖掉的深灰色格子还没确定,其它的格子上都已经放好了正确的拼块。再换句话说,在拼图游戏过程中,拼块是否应放在浅灰色的格子里,若可以则应该放在哪个格子,以及浅灰色格子之间的邻接状态都是已经知道的了,只要是不涉及深灰色格子的信息,你要什么我就给你什么。此时,我们只剩下n/5个格子(仍然是O(n)个格子),并且询问1与询问2变得完全等价;你要问拼块A和拼块B是否相邻,还不如直接问拼块是否应放在某个洞里。于是,问题变为这样,只凭借询问1来确定O(n)个拼块的位置需要多少次询问。我们下面证明,O(n^2)次询问是必须的。
    考虑一个二分图,左边n个顶点表示n个拼块,右边n个顶点表示拼图上残留的n个洞。现在,我只能询问指定的两顶点间是否有边,只有当交互库回答了n次yes后拼图才算完成。那么,作为交互库,你应该尽可能返回对游戏者不利的信息,让整个局面往最坏的方向发展。如果叫你来写这个交互库,你该怎么写?容易想到,只要有可能,我都返回no;除非某个时候一旦我再返回一次no,所有没被问过的边和返回过yes的边所组成的二分图不存在一个完全匹配时,我才可能返回yes。我们需要一个二分图存在完全匹配的充分条件来支持我们的这个算法。
    考虑如下定理:如果一个二分图左边右边各有n个顶点,每个顶点都与对面至少n/2个顶点相连,则这个二分图一定存在一个完全匹配。定理的证明很简单。König定理告诉我们,二分图的最大匹配数应该等于最小点覆盖集,而一个图的最小点覆盖与最大点独立集是互补的,它们的和始终等于顶点数|V|(在这里|V|=2n)。因此我们只需要证明,上述二分图的最大点独立集不会超过n。假如我在左边选的顶点数不超过n/2个,则右边最多也只能选n/2个顶点(左边任一个点都已经使右边至少n/2个点废了);假如我左边选的顶点数超过了n/2个,则右边的顶点一个都不能选(右边每个点都连接了左边至少n/2个点,任选一个都会导致冲突)。总之,最大点独立集不可能超过n,但n显然是可以达到的(取同一边的所有点),那么最小点覆盖集也就是n,即二分图存在完全匹配。
    有了这个定理,下面我就好办了:任何时候,只要每个顶点你都有半数以上的边没问过,我就可以放心大胆的回答no(因为这些没问过的边总可以组成一个完全匹配);一旦某个时刻有一个顶点被问过了n/2次,那么我就随便找一个完全匹配,把这个点“亮”出来,告诉你这个点应该和哪个点匹配(不计询问次数),然后把这两个匹配了的顶点从图中删去,继续刚才的操作。每次删除一对顶点都会顺带着删掉与它们相连的至少k/2条问过的边,其中k表示当时左边右边各剩下k个顶点。删掉了多少边就表示你曾问过了多少边,因此完成整个拼图你总共问过至少n/2 + (n-1)/2 + … + 2/2 + 1/2条边,这个数量显然是O(n^2)的。

做人要厚道
转贴请注明出处
参考资料:http://www.brand.site.co.il/riddles/200710q.html

非传统题型练习:三道交互式题目

Problem 1: famous 谁是名人
题目来源:Matrix67根据经典问题改编

    题目和测试库源码直接见http://www.matrix67.com/blog/article.asp?id=179

题解:
    显然名人最多有一个。问两个还没有问过的人A和B。如果A认识B,那么A肯定不是名人;如果A不认识B,那么B肯定不是名人。总之,结果无论是什么,总有一个人要排除。由于题目说了一定有名人,那么只需要询问n-1次,每次排除一个人,剩下的肯定就是名人了。

Problem 2: meandian 中等工资
题目来源:CEOI 2006 有细节改动 (Translated by Matrix67)

问题描述
    一些公司不愿意透露员工的工资,这样可以防止工会的领导者知道员工的报酬有多低,从而避免烦人的涨工资的谈判。不过,有时公司很乐意为统计和市场目的透露一些消息。
    其中一个公司愿意回答的问题是这样的形式:“员工A、B、C、D的中等工资是多少”。四个数的“中等值”定义为中间的两个值的算术平均数。更明确的,a,b,c,d的中等值按这样的方式得到:首先对这四个数排序,然后计算排序后的第二个数x和第三个数y的平均数(x+y)/2。你的目标是通过询问一些这种形式的问题来得到员工具体的工资数。注意有一些员工的工资有可能永远不能推出(比如工资最低的那个人)即使所有可能的问题都被问过。
    该公司有N(4<=N<=100)名员工,分别用1到N标记。每个员工的工资是一个小于等于100 000的正偶数,且没有两个员工的工资相同。
    你将得到一个实现中等值的询问的库。给出四个不同的整数A,B,C,D (1<=A,B,C,D<=N),这个函数可以返回员工A、B、C、D的中等工资。
    写一个程序访问测试库,找出所有员工准确的工资数(除了永远不能确定的以外)。你的程序最多允许询问1000次问题。

交互方法
    你将获得的测试库提供了以下三个函数或过程:
       function init:longint;
       function meandian(a,b,c,d:longint):longint;
       procedure solution(var sol:array of longint);
    Init:调用该函数不带参数。这个函数必须在程序开头调用且只能调用一次。它将返回一个整数N,即公司的员工数。
    Meandian:这个函数被调用时需要带四个参数A、B、C、D。这四个数应该是从1到N的四个不同的数(包括1和N)。它返回一个整数,是员工A、B、C、D的中等工资。
    Solution:这个函数应该在程序结尾调用。你需要用一个表示员工工资的整数数组来作为它的参数。如果某个员工的工资不能确定,数组中对应的值应该为-1。
    注意这个数组必须从0开始。也就是说员工1的工资应该在数组的0位置,员工2应该在1的位置,依此类推。

    你的源程序在声明处必须包含“uses libmean”。
    编译时,你需要把库文件和源文件放在同一个目录。

一个成功交互的例子
    下面是一个程序代码的片段。它完全不能解决我们的问题,但它可以告诉你如何使用库函数。

uses libmean;
var i, n : integer;
    arr : array[0..99] of longint;
    foo, bar, quux : integer;
begin
   n := Init;
   foo := Meandian(1, 2, 3, 4);
   bar := Meandian(4, 2, 3, 1);
   quux := Meandian(n, n-1, n-2, n-3);
   for i := 1 to n do
      arr[i-1] := 2*i;
   arr[3] := -1;
   Solution(arr);
end.

你如何测试自己的程序
    我们提供的库允许你通过标准输入读进数字N和N个偶数来测试你的程序。
    这个库将输出一个信息告诉你你的答案是否正确。它同时产生一个包含有你的程序运行的详细信息的文本文件meandian.log。
    下面的例子告诉你如何为你的程序输入数据。测试库将告诉你你的答案的正确性。
10
100 500 200 400 250 300 350 600 550 410

评分方法
    当你提交的答案与我们的正确答案相符时得10分。我们一共将有10次测试,总共100分。
    出现以下情况均不给分:
      程序提交的答案错误或没有提交答案;
      程序运行时间超过0.1秒;
      程序使用内存空间超过64M;
      程序询问次数超过1000次;
      程序崩溃或意外退出;
      错误访问库导致测试库出错;
      程序访问了其它外部文件。

数据规模
    对于30%的数据,N<=10;
    对于50%的数据,N<=50;
    对于100%的数据,N<=100。

题解:
    当时我做同步赛时,只有这道题AC了,因此对这道题情有独钟。
    如果N=4,那么显然一个都问不出来。那么N=5呢?通过下面的方法可以问出这5个人中工资排在中间的那个人是谁,并且知道他的具体工资数。假如这5个人按工资从低到高排序分别为A、B、C、D、E,那么问ABCD和ABCE将得到两个相等的小值(BC的平均数),问ACDE和BCDE将得到两个相等的大值(CD的平均数)。剩下的结果由ABDE产生,其值介于前面两者之间(BD的平均数)。换句话说,把5种问法问个遍,那么得数最大的就是CD的平均数,得数最小的是BC的平均数,剩下的那个就是BD的平均数。根据这三个式子,我们就可以算出BCD的值是什么了。但我们只知道了三个人的工资数,还不知道哪个人对应哪个人。你会发现,你不能确定B和D具体是哪个人,但C是谁我们肯定知道。C所对应的人就是问出BD的平均数的那一次询问里没有被问到的人。
    询问5个人可以问出一个人来,那么我们就不断地找5个都还不知道的人重复这个过程。我们不必真的去“找”工资还没确定的人,只需要用一个新的人来代替前一个5人组中问出来了的那个人。这样下去我们只需要不到500次就可以问出N-4个人的具体工资。这种方法不能确定工资最小的两个人和工资最大的两个人。
    事实上,我们可以证明这4个人永远不可能被问出来。假如把工资最小的两个人它们对应的工资数交换一下,你会发现所有可能问到的问题答案仍然不变,因此这两个人不能判断谁是谁。对于工资最大的两个人道理相同。

Problem 3: gf 谁是我的女友
题目来源:Matrix67根据经典问题改编

问题描述
    我们学校有M个男生,N个女生(M<=N<=1000)。每个男生都在这些女生中找到了一个知己。每个男生都恰有一个女友,不同的男生有不同的女友(有N-M

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

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

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

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原创
转载请注明出处