NOI’2004福建省选手选拔赛试卷
|
考生须知 *若试卷中试题字迹不清，考生可以在审题时举手请求解释，由考务人员加以说明。涉及题意理解问题，则不得提问且考务人员不予解答。 *考生上机编程时应在指定目录下工作，并请每隔5分钟存盘一次。发生机器故障时由考务人员确认补给修复时间，且最长不超过10分钟。 *对考生答题测试有严格时间限制，若超时则该测试项判为0分。考生应注意优化算法。 *考生应严格遵守考场规则，不得违纪。 *考试时间为8时30分至12时，计210分钟（其中30分钟为审题时间）。 |
试卷满分为100分
试题一、猜数游戏 (本题满分30分)
«问题描述：
猜数游戏是一个古老的智力游戏。一个游戏者A首先想出一个数x（1£ x £ n），让另一个游戏者B来猜。现在由你扮演游戏者B，用尽可能少的次数猜出x，并且你所猜的数中大于x的数不能超过m个。
为了更全面测试你的程序的性能，游戏者A可能会想出多个不同的数，让你来猜。你必须依次猜出每一个数。
«交互方式：
本题是一道交互式题目，你的程序应当和测试库进行交互，而不得访问任何文件。测试库提供两个函数：Init，Ask，它们的作用和用法如下：
Ø Init(m,n)必须首先调用，用它来获得正整数m,n的值，并且读入第一个待猜的数。(1£m£n，1£n£10000)。
Ø Ask(num)的作用是询问。其中1£num£n。表示询问num是否是A所想的x。若函数返回0，表示num=x；若函数返回-1，表示num<x；若函数返回1，表示num>x。
当num=x时，测试库会自动读入下一个待猜的数，如果所有的数都已经被猜出，测试库会自动终止你的程序，切记你的程序不得自行终止。
当num>x的次数超过m次，或者出现num>n，num<1的情况，程序将会被异常终止。
对于每一个待猜的数，调用Ask函数的次数不能超过50次。
«一个成功交互的例子：
|
函数调用 |
返回值 |
说明 |
|
Init(m,n) |
m=2, n=3 |
1£ x £ 3，所猜的数中大于x的数不能超过2 |
|
Ask(3) |
1 |
3>x，所猜的数大于x次数：1次 |
|
Ask(1) |
-1 |
1<x |
|
Ask(2) |
0 |
2=x，猜数成功。猜数次数=3，自动读入下一个待猜的数 |
|
Ask(3) |
1 |
3>x，所猜的数大于x次数：1次 |
|
Ask(2) |
1 |
2>x，所猜的数大于x次数：2次 |
|
Ask(1) |
0 |
1=x，猜数成功。猜数次数=3，程序自动结束 |
«对Pascal程序员的提示：
你的程序应当使用下列语句引用测试库：
uses mylib;
测试库提供的函数/过程原型为：
procedure Init(var m,n:integer);
function Ask(num:integer):integer;
«对C/C++程序员的提示：
你应当建立一个工程，把文件mylib.obj包含进来，然后在程序头加上一行：
#include
“mylib.h”
测试库提供的函数原型为：
void Init(int
*m, int *n);
int
Ask(int num);
«评分方法：
如果你的程序有下列情况之一，得0分：
Ø 访问了任何文件(包括临时文件)或者自行终止；
Ø 非法调用库函数；
Ø 让测试库异常退出。
否则，每个测试点你的得分将按照本组中猜数次数最多的一那个数据来评分：
1. 如果你的猜数次数小于或等于我们提供的参考次数，你将得到100%的分数。
2. 如果你的猜数次数等于参考次数+1，你将得到50%的分数。
3. 否则你将得到30%的分数。
«如何测试程序：
1. 在工作目录下建立一个文本文件guess.in，文件第一行包括两个整数m，n，其后若干行每行一个整数，表示待猜的数。用整数0表示输入结束。
2. 在工作目录下建立一个文本文件guess.ans，文件第一行包括两个整数，表示本测试的总分s和参考比较次数t。
3. 执行你的程序，此时测试库会产生输出文件guess.log，记录每个数的猜数次数。
4. 如果程序正常结束，你的得分将会显示在屏幕上。
如果程序非法退出，则会在屏幕上显示:“Error”。
|
输入文件示例 |
输出示例 |
|
|
guess.in |
guess.ans |
Your worst calling times: 3 |
|
2 3 2 1 0 |
10 2 |
Your score: 5 |
试题二、达尔文芯片问题（本题满分30分）
«问题描述：
人的大脑里发生的一切是神奇的，甚至是不可理解的，正是这种神奇使得人具有自我意识。如果用普通硅片、电路、传感器制成的机器人也能进化，从而能有意识的行动，那么是否有一天，机器人也会变得和人一样有意识？电脑的硬件也许能像自然界人类和其他生物进化的方式进行进化这一想法，早在上世纪60年代就被提出，但如何着手是到1998年，因美籍华裔计算机科学家的一个灵感，才得以突破。这一灵感就是被称为达尔文芯片的高集成度可编程集成电路块，简称为DPGA。
最近，福州大学计算机学院计算机神经学研究小组的科学家们发现，对达尔文芯片的关键逻辑元进行重组后产生一种奇特的现象。将若干关键逻辑元按照电路板平面坐标系2维降序排列，经过电路演化，这些关键逻辑元自动按照x坐标和y坐标方向联接成一棵树。这棵树的每条边都平行于x坐标轴或平行于y坐标轴。关键逻辑元构成这棵树的全部叶结点。这类树称为以关键逻辑元为叶结点的正交树。有趣的是，达尔文芯片自动产生的正交树的总边长是所有这种正交树中总边长最小的。例如，将5个关键逻辑元分别置于电路板xoy坐标系中(1,5)，(2,4)，(3,3)，(4,2)和(5,1)处，则达尔文芯片自动产生的一棵正交树如下图所示，它的总边长为12。
«编程任务：
给定电路板xoy坐标系，以及电路板上n个关键逻辑元在xoy坐标系中按照2维降序排列的位置
，
，…，
。其中，
；
； 
。
编程计算以这n个关键逻辑元为叶结点的正交树中，总边长最小的最优正交树总边长的值。
«数据输入：
输入数据由文件名为INPUT2.*的文本文件提供。
n 第1行中的整数为关键逻辑元个数n；
n 接下来的n行中每行一个整数，依次为
；
n 最后的n行中每行一个整数，依次为
。
«结果输出:
程序运行结束时，在屏幕上输出所找到的最优正交树总边长的值。
|
输入文件示例 |
输出示例 |
|
INPUT2.001 |
12 |
|
5 1 2 3 4 5 5 4 3 2 1 |
|
试题三、登山机器人问题（本题满分40分）
«问题描述：
登山机器人是一个极富挑战性的高技术密集型科学研究项目。它涉及小车机械、飞行器控制、机器人学、机电一体化、单片机、数据融合、精密仪器、实时数字信号处理、图像处理与图像识别、知识工程与专家系统、决策、轨迹规划、自组织与自学习理论、多智能体协调、以及无线通讯等多项理论和技术，是一个典型的智能机器人系统。登山机器人为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。
登山机器人可以携带有限的能量。在登山过程中，登山机器人需要消耗一定能量，并且可以在机器人之间通过接触传递能量。用多个登山机器人接力登山可以极大地提高登山机器人的攀登高度。
«编程任务：
给定n个登山机器人（1<n<100）。第i个登山机器人最多可以携带
单位的能量，每攀高1米需要消耗能量
单位。开始登山时n个登山机器人均处于同一水平高度0，并且每个登山机器人初始时都携带了最多的能量。计算用这n个登山机器人进行不返回的接力登山可攀登的最高的高度。
«数据输入：
输入数据由文件名为INPUT3.*的文本文件提供。
n 第1行中的整数为登山机器人个数n；
n 接下来的n行中每行一个整数，依次为
；
n 最后的n行中每行一个整数，依次为
。
«结果输出:
程序运行结束时，在屏幕上输出所找到的这n个登山机器人可攀登的最高的高度，精确到小数点后2位。
|
输入文件示例 |
输出示例 |
|
INPUT3.001 |
7500 |
|
2 50 50 0.01 0.01 |
|
NOI’2004福建省选手选拔赛测试记录
|
姓名 |
|
学校 |
|
测试日期 |
|
总得分 |
|
|
题1 |
输入 |
参考次数 |
满分 |
时限 |
用时 |
实际次数 |
实际 得分 |
|
1.1 |
check 1 |
12 |
5 |
1 |
|
|
|
|
1.2 |
check 2 |
24 |
5 |
1 |
|
|
|
|
1.3 |
check 3 |
18 |
5 |
1 |
|
|
|
|
1.4 |
check 4 |
14 |
5 |
1 |
|
|
|
|
1.5 |
check 5 |
17 |
5 |
1 |
|
|
|
|
1.6 |
check 6 |
14 |
5 |
1 |
|
|
|
|
题2 |
输入 |
输出 |
满分 |
时限 |
用时 |
实际输出 |
实际 得分 |
|
2.1 |
INPUT2.001 |
21733 |
5 |
1 |
|
|
|
|
2.2 |
INPUT2.002 |
70657 |
5 |
1 |
|
|
|
|
2.3 |
INPUT2.003 |
87200 |
5 |
1 |
|
|
|
|
2.4 |
INPUT2.004 |
111611 |
5 |
1 |
|
|
|
|
2.5 |
INPUT2.005 |
130281 |
5 |