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

2007 年 3 月 9 日 / 3 条评论

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

非传统题型练习：三道答案提交类题目

2007 年 3 月 6 日 / 4 条评论

不少人可能为找不到非传统题型的练习题而头疼。这几天我专门发出一些用于省选集训的题目供大家参考。

Problem 1: cell 手机
题目来源：USACO Contest FEB06 Gold (Translated by Matrix67)

问题描述
    奶牛们已经开始使用手机交流了，但它们发现手机的按键设计不适合它们的蹄子。它们想设计一个新的手机，让它的按键更少，但是更大。
    它们喜欢普通手机的一个功能：词语联想。每个按键都有一些字母和它对应，打出一个单词只需要按对应的按键。因为一个按键可能对应多个字母，因此某些单词可能会发生“歧意”。不过，大多数时候这种歧意可以通过用字典判断的方法来消除。
    考虑到奶牛们在自定义一款新的手机，它们还需要用奶牛字母表替换英文字母表。神奇的是，奶牛字母表中的字母恰好是英语字母表中的前L个字母，即使顺序也一样。它们想知道如何把这些字母分配给B个按键(1<=B<=L)使得在字典中不会产生歧意的单词最多。就像普通的手机一样，他们希望每个按钮上的字母都是字母表中一段连续的字母。

    这是一个答案提交类的题目。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件cell.3.in相对应的输出文件应该为cell.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入数据
    第一行：一个整数N，表示这是第N个输入文件。
    第二行：两个用空格隔开的整数：B和L
    第三行：D，字典中的单词数(1<=D<=1000)
    第四行到第D+3行：每一行包含一个字典中的单词，用1到10个大写字母表示。这些单词按照字典序给出，并且保证没有重复。

输出数据
    第一行：字典中具有唯一的按钮序列的单词数。
    第二行到第B+1行：其中的第n行包含有第n个按钮上的字母，用大写的字母按照字典的顺序表示。所有行必须按照字典序排列，每个字母出现恰好一次。如果有多个最优解，选用第一个按键上字母最多的解。如果最优解仍然不唯一，考虑第二个按键上字母最多，依此类推。

样例输入(cell.1.in)
1
3 13
11
ALL
BALL
BELL
CALK
CALL
CELL
DILL
FILL
FILM
ILL
MILK

样例输出(cell.1.out)
7
AB
CDEFGHIJK
LM

样例说明
    第一个按键上只有AB两个字母，第二个按键上含有C到K，第三个按键上为LM。单词CELL、DILL、FILL和FILM的输入都是2233，其它7个单词的输入都是唯一的。

题解(Ctrl+A)：
这道题目……搜索，乱搞。

Problem 2: selfstr 自描述序列
题目来源：Matrix67根据经典问题改编

问题描述
    “这句话里有1个数字零，2个数字一，1个数字二，0个数字三”。

    在N(N>=2)进制中只允许0到N-1这N个数字出现。一个N位的N进制数（允许有前导0）可以由另一个同样多位的数来描述。我们定义一个N位N进制数的描述序列为：左起第i个数字为原数中数字i-1出现的次数。
    例如，在4进制中，0023的描述序列为2011，因为0023中有2个0，0个1，1个2和1个3。
    我们惊奇地发现，4进制数1210的描述序列是它本身！我们称这样的数叫做“自描述序列”。

    你需要编写程序计算出在某个进制下的自描述序列。一个进制下的自描述序列可能有很多个，你只需要给出其中一个即可。
    这是一个答案提交类的问题。你只需要在你自己的计算机上计算出你的答案，然后把输出文件提交上来。与输入文件selfstr.3.in相对应的输出文件应该为selfstr.3.out，这里“3”表示你提交的答案是第3个输入文件的解。当然，其它输出文件需要把这个3替换成相应的数字。你不需要提交任何其它的文件。

输入格式
    输入数据只有一个正整数N

输出格式
    输出N个字符，它表示N进制下的自描述序列。在高于10的进位制下，大于9的数字请用大写字母表示。
    如果有多种可能的解，你只需要输出其中一个。
    如果该进制下无解，请输出“NONE”。

样例输入(selfstr.1.in)
4

样例输出(selfstr.1.out)
1210

题解：
这道题太有意思了！首先，你需要先算几个小数据。你会发现，算到N>=6后，渐渐有规律了：

   N   N进制下的自描述序列
   4    1210 or 2020
   5    21200
   6    NONE
   7    3211000
   8    42101000
   9    521001000

事实上，这道题目就是考你当搜索到一些解后能不能找到规律得到所有解。这里我们发现，对所有N>6，至少存在一个解为R21(0…0)1000，其中R=N-4，中间0的个数为N-7。结论显然正确。
有可能除了这个之外存在其它的解，因此我们仍然需要写一个check来核对答案。

Problem 3: relation 大小关系
题目来源：Matrix67根据经典问题改编

问题描述
    用关系“ < ”和“ = ”将3个数a、b、c依次序排列时，有13种不同的序列关系：
      a=b=c, a=b<c, a<b=c, a<b<c, a<c<b
      a=c<b, b<a=c, b<a<c, b<c<a, b=c<a
      c<a=b, c<a<b, c<b<a

    用这两种关系连接N个数有多少种不同的方案？

    这是一个答案提交类的问题。所有选手将得到10个输入数据，你只需要在你自己的计算机上计算出你的答案，然后把你的答案提交上来。与输入文件relation.x.in相对应的输出文件应该为relation.x.out，这里x表示一个1到10之间的数。

输入格式
    输入一个整数，表示N。

输出格式
    输出用小于和等于符号将N个数进行有序排列的方案数。

样例输入(relation.1.in)
3

样例输出(relation.1.out)
13

题解：
    组合数学+高精度。由于数据规模很小，我就直接搞成了答案提交类的题目。
    下面给出两种递推方法：
    Solution 1: N个数中必然存在一个最大的“等价类”，如果这个等价类里有k个数，那么剩下的数就有F(N-k)种排列方案。别忘了我们需要枚举这k个数是哪k个数。于是，F(N)
=C(N,1)F(N-1)+C(N,2)F(N-2)+C(N,3)F(N-3)+ … +C(N,N)F(0)
    Solution 2: 用F[ i, j]表示 i个数中有j 个等价类的排列方案（就是说有j-1个小于符号）。第 i个数有可能并入了F[i-1, j]中的 j个等价类中的一个，也有可能不与任何一个已有的数相等，独自成为一个等价类插入F[i-1, j-1]里产生的 j个空位中。于是，F[ i,j ]=F[i-1, j]*j + F[i-1,j-1]*j。

其它问题：
    如何用Cena评测答案提交类问题？
        见http://www.matrix67.com/blog/article.asp?id=176
    这些题的数据哪里有？
        第一题：http://ace.delos.com/FEB06，GOLD DIVISION里面的第三个
        第二题：自己写check，不需要数据
        第三题：http://www.research.att.com/~njas/sequences/b000670.txt，吓死你

Matrix67原创
转贴请注明出处

我见过的最大的Flash游戏，最有意思的Puzzle类游戏

2007 年 2 月 23 日 / 8 条评论

一个30M的Flash游戏让我入迷。
http://www.handmadegame.com/Game_Rooms.htm

现在的智力游戏非常令人失望，不是什么三个三个的消除，就是什么单词拼写之类的东西。有创意的解谜游戏也见到过，但可玩性不高，不一会儿就搞烦了。今天看到了一个叫做Rooms的游戏，实在让我眼前一亮。或许是神秘的气氛吸引了我，或许是谜题设计很有意思，我很喜欢。
在Rooms中，你处在一个时空混乱的地方，你可以从游戏的背景音乐中感受到《The Lost Room》般的神秘感觉。每一次谜题初始时你都在其中一个房间中，你需要使用各种工具到达那个有出口大门的房间。你可以把你所在的房间当作滑块来移动，也可以使用房间里或者自己携带的各种物品。这个游戏有多么奇妙我完全无法解释，因此给大家看一个完整的过关过程。大家可以看一看其中一关我的解法。

Step 1: 初始状态。我在那个有天空的房间里，我要想办法到右下角去；
Step 2: 对我所在的房间进行操作，把这个房间滑动到右边去；
Step 3: 房间滑过来了；
Step 4: 爬梯子上去，到另外一个写有“Exit”的房间；

Step 5: 把我现在所在的（写有“Exit”的房间）移动到我初始时的位置，然后顺着梯子下去；
Step 6: 使用这个房间的道具——电话，像The Matrix一样瞬移到另外一个房间里；
Step 7: 瞬移过来了；
Step 8: 把这个房间移动上去，然后打电话回来；

Step 9: 瞬移过来后顺着楼梯爬上去，把写有“Exit”的房间移动到大门的正上方；
Step 10: 爬楼梯下去；
Step 11: Stage Clear With一个很酷的转身动作。

做人要厚道
转贴请注明出处

2.14 送大家一个我很喜欢的图片

2007 年 2 月 14 日 / 6 条评论

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

2007 年 2 月 14 日 / 5 条评论

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

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

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

