|
|
十分十分BT的题～大家看看啦～
第一题：
牛场围栏
fence.exe
【问题描述】
John计划为他的牛场建一个围栏，以限制奶牛们的活动。他有N种可以建造围栏的
木料，长度分别是l1,l2…lN，每种长度的木料无限。修建时，他将把所有选中的
木料拼接在一起，因此围栏的长度就是他使用的木料长度之和。但是聪明的John
很快发现很多长度都是不能由这些木料长度相加得到的，于是决定在必要的时候
把这些木料砍掉一部分以后再使用。不过由于John比较节约，他给自己规定：任何
一根木料最多只能削短M米。当然，每根木料削去的木料长度不需要都一样。不过
由于测量工具太原始，John只能准确的削去整数米的木料，因此，如果他有两种长
度分别是7和11的木料，每根最多只能砍掉1米，那么实际上就有4种可以使用的木
料长度，分别是6, 7, 10, 11。
Clevow是John的牛场中的最聪明的奶牛，John请她来设计围栏。Clevow不愿意自己
和同伴在游戏时受到围栏的限制，于是想刁难一下John，希望John的木料无论经过
怎样的加工，长度之和都不可能得到她设计的围栏总长度。
不过Clevow知道，如果围栏的长度太小，John很快就能发现它是不能修建好的。因
此她希望得到你的帮助，找出无法修建的最大围栏长度。
【输入文件】
输入文件的第一行包含两个整数N, M (1<N<100, 0<M<3000)，分别表示木
料的种类和每根木料削去的最大值。以下各行每行一个整数li(1<li<3000),表示第
i根木料的原始长度。
【输出文件】
输出文件仅一行，包含一个整数，表示不能修建的最大围栏长度。如果任
何长度的围栏都可以修建或者这个最大值不存在，输出-1。
【输入输出样例】
fence.in fence.out
2 17 11 15
第二题：
奶牛浴场
happy.exe
【问题描述】
由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建
造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶
牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。
你还能帮助Clevow吗？
John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。
浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
【输入文件】
输入文件的第一行包含两个整数L和W，分别表示牛场的长和宽。文件的第二行包含一个整数n，表示产
奶点的数量。以下n行每行包含两个整数x和y，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：0<x<L，
0<y<W。
【输出文件】
输出文件仅一行，包含一个整数S，表示浴场的最大面积。
【输入输出样例】
happy.in happy.out
10 1041 19 11 99 9 80
【参数约定】
0<n<5000
1<L,W<30000
第三题：
太空站之谜
station.exe
【问题描述】
3000年的一天，人们在茫茫的宇宙中发现了一些奇怪的太空站。科学家们用高科技探测出了它们的精确位
置，并绘制了地图，准备派一批机器人到那里进行深入的研究。
地图是一个N*M的矩形网格，每个格子要么是可以穿梭自如的真空(用白色表示)，要么是无法逾越的未知物
质(用阴影表示)。机器人每次可以沿着东(E), 南(S)，西(W)，北(N)中的一个方向前进到相邻格子 (如果那里
没有未知物质阻挡)。由于太空站内没有任何光线和其他可被机器人感知的物质，机器人只有在尝试往某一个方
向行进而失败以后才能知道该方向的相邻格子无法到达，而不能事先知道某一方向上是否有障碍。
有趣的是，太空站里所有未知物质连成一片（沿东南西北四个方向连通），把所有真空格围在中间，形成
一个真空大厅，机器人从任何一个真空格出发都可以走到其他所有真空格中。另外，太空站内没有“狭窄的通
道”，即对于每个真空格子来说，它的南北方向至少有一个相邻格子是真空，东西方向也至少有一个相邻格子
是真空。为了方便，我们把所有的真空格按照从北到南，从西到东标号为1,2,3…。下图就是是其中一个叫FT的
太空站的地图标记。
1 2
3 4 5 6
7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
真空格
未知物质
传送门
太空站FT地图
机器人一号被运送到了FT的12号真空格（由于技术限制，机器人们只能被运送到某个和未知物质有公共边
的格子）后开始工作。他从起始位置出发往东走一格，再往北走一格，以为到达了8号格。但当他试着往北移动
的时候，他惊奇地发现竟然没有被阻挡，而是成功的走到8号格的上方那个地图上标记为未知物质的格子。这一
重大发现很快传遍了所有在太空站内工作的机器人。他们一致认为地图有误，因而用集体罢工的方式向人类提
出抗议。
针对这一情况，科学家们解释说：地图并没有绘制错，该现象的发生是因为太空站中存在着某种神秘的传
送装置 – 虽然机器人一号在行走中已经被瞬间转移到其他格子中去了，但他自己却一点也感觉不到。
科学家们指出，太空站中有K个传送装置，每一个装置逻辑上连接着两个不同的真空格子，称为传送门。每个传
送门只能属于一个传送装置，并且任意传送门周围的8个格子中不会有其他传送门或者未知物质。如果两个传送
门属于同一个传送装置，那么当机器人沿某一个方向进入其中一个传送门，它就会被瞬间转移到另一个传送门
并沿该方向再前进一格。在机器人看来，这一过程和普通的行走并没有区别，因此他们无法感知瞬间转移的进
行。
以FT为例，由于有一个传送装置连接着10号格和13号格，机器人一号的实际路线是12->11->5->1，根本没有到
达格子8上面那个不能去的格子。
机器人们明白了其中的奥秘以后，迫不及待的想要找出这些传送装置，但又担心自己在太空站中的工作时
间会过长。经过一番慎重的考虑，科学家们决定请你编写一个智能控制程序，帮助机器人用尽量少的步数找到
所有传送装置。
【输入文件】
输入文件station.dat的第一行包含三个整数N, M, K(6 < N, M < 15, 1 < K < 5)，即地图的大小以及传
送装置的个数。以下共N行，每行M个字符，代表该太空站的地图。真空用空格表示，未知物质用“*”表示，起
始位置用大写字母“S”表示。起始位置保证与至少一个未知物质格有公共边 ,真空格保证不出现在地图的边或
角上。输入数据保证无错，行末无多余空格。
【交互】
你的程序应当与测试库进行交互。测试库提供三个函数：Init, MoveRobot和Answer，它们的作用和用法如下：
? Init必须首先调用，且只能调用一次，以进行测试库本身的初始化。
? MoveRobot函数的作用是移动机器人。该函数仅有一个参数Direction，即行进的方向，只能是’N’
(北)，’E’(东)，’S’(南)，’W’(西)其中之一。函数的返回值表示该动作是否完成。0表示失败，1表示成
功。
? Answer函数用来告诉测试库你找到的传送装置。它有两个参数pos1, pos2, 即装置连接的两个真空格
的序号。你的程序必须调用K次Answer函数，每次给出一个不同的传送装置。只要结果正确，给出传送装置的
顺序是无关紧要的。在调用K次该函数后，测试库将自动终止你的程序。你的程序不得自行终止。
【输入和交互样例】
下面是一个合法并且得到正确结果的函数调用序列。
Station.dat 函数调用 返回值
7 8 1*************..****....**.....***S. . .**......********* Init 无
MoveRobot(‘E’) 1
MoveRobot(‘N’) 1
MoveRobot(‘N’) 1
MoveRobot(‘W’) 0
MoveRobot(‘N’) 0
MoveRobot(‘E’) 1
MoveRobot(‘E’) 0
Answer(10,13) 无
【对PASCAL程序员的提示】
你的程序应当使用下列语句引用测试库：
uses robot;
测试库提供的函数/过程原型为：
Procedure Init;
Function MoveRobot(Direction:char):integer;
Procedure Answer(pos1,pos2:integer);
【对C/C++程序员的提示】
你应当建立一个工程，把文件robot.o包含进来。
测试库提供的函数原型为：
void Init(void);
int MoveRobot(char Direction);
void Answer(int pos1, int pos2);
【评分】
如果你的程序出现以下3种情况之一，相应数据得零分：
? 打开除station.dat以外的其他文件，包括临时文件。
? 使用非法参数调用测试库中的函数。
? 程序超时，非正常退出或者未调用满K次Answer函数就自行退出。
只要结果正确，你能够得到该数据分值的50%。如果MoveRobot的调用次数不超过32767次，你的程序将得到另外
50%的分值。
【如何测试你的程序】
改用testlib库编译你的程序。如果你用Pascal，你需要把”uses robot;”改为”uses testlib;”。如果
你用c/c++，你需要把工程中的robot.o替换成testlib.o。
除了station.dat之外, 你应当另外建立一个文本文件station.lnk 来描述传送装置。该文件共K行，每行
包含一个传送装置连接的两个真空格的序号，中间用空格隔开。运行程序以后，测试库将产生输出station.log
。 该文件仅包含一个数T，代表程序调用MoveRobot函数的次数。如果有错误，station.log将仅包含一个数-1。
怎么样？够BT吧………………  |
|
IP卡
狗仔卡
发表于 2003-9-14 21:05:04
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2003-9-15 07:23:41