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

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

3 条评论

发表评论

2  +  7  =