当前位置:首页 >> 计算机软件及应用 >>

NOI2004选拔赛试卷


NOI’2004 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 Ask(3) 1 Ask(1) -1 Ask(2) 0 Ask(3) 1 Ask(2) 1 Ask(1) 0

说明 1≤ x ≤ 3,所猜的数中大于 x 的数不能超过 2 3>x,所猜的数大于 x 次数:1 次 1<x 2=x,猜数成功。猜数次数=3,自动读入下一个待猜的数 3>x,所猜的数大于 x 次数:1 次 2>x,所猜的数大于 x 次数:2 次 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%的分数。 如何测试程序: 如何测试程序: 在工作目录下建立一个文本文件 guess.in,文件第一行包括两个整数 m,n,其后若干行 每行一个整数,表示待猜的数。用整数 0 表示输入结束。 2. 在工作目录下建立一个文本文件 guess.ans, 文件第一行包括两个整数, 表示本测试的总 分 s 和参考比较次数 t。 3. 执行你的程序,此时测试库会产生输出文件 guess.log,记录每个数的猜数次数。 4. 如果程序正常结束,你的得分将会显示在屏幕上。 如果程序非法退出,则会在屏幕上显示:“Error” 。 输入文件示例 guess.in guess.ans 23 10 2 2 1 0 输出示例 Your worst calling times: 3 Your score: 5

1.

试题二、达尔文芯片问题( 试题二、达尔文芯片问题(本题满分 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 维降序排 列的位置 ( x1 , y1 ) , ( x 2 , y 2 ) ,…, ( x n , y n ) 。其中, 1 ≤ n ≤ 3000 ;

0 ≤ x1 ≤ x 2 ≤ ≤ x n ≤ 20000 ; 0 ≤ y n ≤ y n 1 ≤ ≤ y1 ≤ 20000 。
编程计算以这 n 个关键逻辑元为叶结点的正交树中, 总边长最小的最优正交树总边长的 值。 数据输入: 数据输入: 输入数据由文件名为 INPUT2.*的文本文件提供。 n 第 1 行中的整数为关键逻辑元个数 n; n 接下来的 n 行中每行一个整数,依次为 x1 , x 2 , , x n ; n 最后的 n 行中每行一个整数,依次为 y1 , y 2 , , y n 。 结果输出: 结果输出 程序运行结束时,在屏幕上输出所找到的最优正交树总边长的值。 输入文件示例 INPUT2.001 5 1 2 3 4 5 5 4 3 2 1 输出示例 12

试题三、登山机器人问题( 试题三、登山机器人问题(本题满分 40 分)
问题描述: 问题描述: 登山机器人是一个极富挑战性的高技术密集型科学研究项目。 它涉及小车机械、 飞行器 控制、机器人学、机电一体化、单片机、数据融合、精密仪器、实时数字信号处理、图像处 理与图像识别、知识工程与专家系统、决策、轨迹规划、自组织与自学习理论、多智能体协 调、以及无线通讯等多项理论和技术,是一个典型的智能机器人系统。登山机器人为研究发 展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。 登山机器人可以携带有限的能量。在登山过程中,登山机器人需要消耗一定能量,并且 可以在机器人之间通过接触传递能量。 用多个登山机器人接力登山可以极大地提高登山机器

人的攀登高度。 编程任务: 编程任务: 给定 n 个登山机器人(1<n<100) 。第 i 个登山机器人最多可以携带 xi 单位的能量,每 攀高 1 米需要消耗能量 y i 单位。 开始登山时 n 个登山机器人均处于同一水平高度 0, 并且每 个登山机器人初始时都携带了最多的能量。 计算用这 n 个登山机器人进行不返回的接力登山 可攀登的最高的高度。 数据输入: 数据输入: 输入数据由文件名为 INPUT3.*的文本文件提供。 n 第 1 行中的整数为登山机器人个数 n; n 接下来的 n 行中每行一个整数,依次为 x1 , x 2 , , x n ; n 最后的 n 行中每行一个整数,依次为 y1 , y 2 , , y n 。 结果输出: 结果输出 程序运行结束时, 在屏幕上输出所找到的这 n 个登山机器人可攀登的最高的高度, 精确 到小数点后 2 位。

输入文件示例 INPUT3.001 2 50 50 0.01 0.01

输出示例 7500

NOI’2004 NOI 2004 福建省选手选拔赛测试记录 20
姓名 学校 测试日期 总得分 实际 得分

题1 1.1 1.2 1.3 1.4 1.5 1.6 题2 2.1 2.2 2.3 2.4 2.5 2.6

输入 check 1 check 2 check 3 check 4 check 5 check 6 输入 INPUT2.001 INPUT2.002 INPUT2.003 INPUT2.004 INPUT2.005 INPUT2.006

参考次数 12 24 18 14 17 14 输出 21733 70657 87200 111611 130281 139750

满分 5 5 5 5 5 5 满分 5 5 5 5 5 5

时限 1 1 1 1 1 1 时限 1 1 1 1 1 1

用时

实际次数

用时

实际输出

实际 得分

题3 3.1 3.2 3.3 3.4 3.5 3.6

输入 INPUT3.001 INPUT3.002 INPUT3.003 INPUT3.004 INPUT3.005 INPUT3.006

输出 9674.15 3361.11 311067 178150 140727 753452

满分 5 5 5 5 10 10

时限 1 1 1 1 1 1

用时

实际输出

实际 得分

评委签名


相关文章:
更多相关标签: