信息学奥赛选拔赛第三试

1、山东省信息学奥赛选拔赛第三试试题（2005 年 5 月 5 日）1阶梯教室设备利用（REZ.PAS）问题描述：现有许多要在阶梯教室中举行。每一个都可以用唯一的起始和终止时间来确定，如果两个时间有部分或全部重复，那么它们是无法同时在教室中举行的。现在想要尽最大可能的利用这个教室，也就是说，需要在这些中选择一些不重复的来举行使得他们用的总时间尽可能的长。任务：请写一个程序：假设在某一结束的瞬间就可以立即开始另一个。在文本文件 REZ.IN 中读入所有的起始和终止时间；计算最大的可能总时间；把结果输出到文本文件 REZ.OUT 中。输入格式（REZ.IN）：文本文件 REZ.IN 的第一行包括一个正

2、整数 n，n 10000，为所有的的数目。以下的 n 行每行含有两个由空格隔开的整数 p 和k，0 p k 30000。这样的一对整数表示一个时间 k 结束。输出格式（REZ.OUT）：由时间 p 开始到在文本文件 REZ.OUT 输出唯一的一个整数，为最长的总时间。输入输出样例：输入（REZ.IN）： 1213067499111514182548136101214191620输出（REZ.OUT）：162.位图(BIT.PAS)问题：现在给出一个 nm 的单色位图，且该图中至少含有一个白色的像素。用(i, j)来代表第 i行第 j 列的像素，并且定义两点 p1=(i1, j1)和p2=(i2

3、, j2)之间的距离为：d(p1, p2)=|i1 - i2| + |j1 j2|任务：请写一个程序：从文本文件 BIT.IN 中读入该位图；对于每个像素，计算出离该像素最近的白色像素与它的距离；把结果输出到文本文件 BIT.OUT 中。输入格式（BIT.IN）：在文本文件 BIT.IN 的第一行包括两个用空格分开的整数 n 和 m，1 n 182，1 m 182。以下的 n 行每行包括一个长度为 m 的用 0 和 1 组成的字符串，在第 i+1 行的第 j 个字符如果为”1”，那么表示像素(i, j)为白的，否则为黑的。输出格式（BIT.OUT）：在文本文件 BIT.OUT 中输出一个 nm

4、 的数表，其中的第 i 行的第 j 个数字为 f(i, j)表示像素(i, j)到最近的白色像素的距离。输入输出样例：输入（BIT.IN）：3 4000100110110输出（BIT.OUT）：3212101000013.遗传代码(PIE.PAS)题目描述:抽象的 primitivus (Primitivus 循环)的遗传代码是一系列自然数 K=（A1,.,An）。所说的primitivus 的特征是安排一对在遗传代码中接连出现的数(l,r)，如果存在 i 则 l=Ai, r=Ai+1。在primitivus 的遗传代码中没有(p,p)特征。任务:写一个程序：从文本文件读特征列表，计算所给特征

5、的最短遗传代码长度，把结果写到输出文件 PIE.OUT 中。输入(PIE.IN):在输入文件 PIE.IN 的首行有一个正整数 n。它是 primitivus 的不同特征数。在接下来的 n 行的每一行中有两个被空格号隔开的数字 l 和 r（1 = l = 1000, 1 = r = 1000）。数字对（l, r）是 primitivus的一个特征。在输入文件中，特征并不重复。输出(PIE.OUT):在文本文件 PIE.OUT 的首行正确的写出一个整数，它等于 primitivus 最短遗传代码的长度。样例输入(PIE.IN):122 33 99 68 55 77 64 55 11 44 22

6、88 6样例输出(PIE.OUT):15备注：在下列遗传代码中来自文件 PIE.IN 的所有遗传代码将被列出：(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)4.屠龙-屠龙枪卷(dragon.PAS)先知看到修玛取回的药草，满意地点了点头。他对修玛说：“跟我来”。修玛顺从地跟着先知走到了他的房间里。先知的房间很大，四周满是书架，整整齐齐地摆放着一排排书籍。房间中间的圆桌上摆放着一个巨大的水晶球，它发出的荧光照亮了整个房间。先知走到一排书架前，从中抽出一本薄薄的书来。这本书看起来十分古老，纸张都变成了黄色，有的地方已经发黑。修玛想，这本书的历史大概有好几

7、百年了吧。先知示意修玛坐下，他翻开手中的书，对修玛说道：“我已经研究这本书很久了。它是用一种古老的文字写成的，记载了一个十分古老的。书中提到，普通的是无法巨龙的，只有诸神合力锻造的屠龙枪才能消灭它。为了防止屠龙枪被，神把它封印在卡基思山上，只有拥有超人的勇气、力量和智慧的能解开这个封印。千百年来，很多人都想得到屠龙枪的力量，然而从没有人成功过。我查阅了所有有关屠龙枪的记载，悉心地研究那些资料，得知屠龙枪被封印在山顶的神殿中，而要解开这道封印，就必须把神殿中的一块巨大的圆石推到神殿祭坛的中心，然后念出解开封印的 语。”修玛问道：“那句 语应该已经失传了吧？”“不，恰恰相反。”先知说，“这句语一直

8、记载在这本书中，并被完好地保存下来。”“那么，剩下的只是把圆石推到祭坛的中心了。”修玛自信地笑了。然而先知却摇了摇头，“不，修玛，事情没有你那么简单。爬上卡基思山就不是一件容易的事。它高耸入云，四周都是光秃秃的石壁，几乎没有落脚的地方。只有真正的勇士才能爬得上去。那块圆石也不是那么容易就能推动的，非得有超常的力量不可。这些东西，修玛你都有。但如果仅仅只有这些，那么屠龙枪早已拿到手了。书中不是说了么，要有勇气、力量和智慧。智慧才是真正的关键。如果在固定时间内不能把那块圆石推到祭坛的中心，那么圆石便会自动滚回原处，同时推石的人将无法再次推动这块圆石。而且不管你用多大力气推，这块圆石都不可能滚动得像

9、你希望的那样快，我估计只有按照最短路线去推这块圆石，才能在固定时间内把它推到祭坛中心。神殿中又有着大大小小的石柱，有些石柱与石柱之间的空隙很小，根本就推不过去。正因为这种种，才没有人能够从神殿中取走屠龙枪。”修玛沉默了一会儿，说：“不管如何，我也要去试一试。如果我不能拿到屠龙枪，就没有人能够拿到它了。”先知点了点头，说：“去吧，修玛。记住，用你的智慧。”修玛骑马奔驰了十天十夜，终于来到了卡基思山脚下。正如先知所说的那样，这座山根本就没有路可以上去，甚至找不到可以落脚的地方。然而修玛凭着他的勇气以及熟练的技巧，爬上了山顶。他走进神殿，一眼就看到了那块巨大的圆石。修玛该怎么做，才能把圆石推到祭坛的

10、中心呢？任务：你的任务是计算出把圆石推到祭坛中心的最短路线长度。所谓推到祭坛中心是指圆石的中心与祭坛中心重合。圆石中心的初始位置以及祭坛中心的位置是已知的。圆石半径为 R，它可以朝着任意方向滚动。洞中所有石柱均为正四棱柱，大小不一。在推动圆石的过程中，要求圆石中心与所有石柱的距离均不小于 R，否则圆石将被石柱阻挡而不能继续滚动。输入(dragon.in)：输入文件 dragon.in 第一行包含了五个实数，依次表示圆石中心的初始位置的 x 坐标、y 坐标、圆石半径 R、祭坛中心的位置的 x 坐标以及 y 坐标。第二行包含一个整数 N（0=N=20），表示神殿中石柱的数目。接下去 N 行每行包含

11、三个实数，给出了一根石柱的信息。第 I+2 行的三个实数依次表示第 I根石柱左下角 x 坐标、y 坐标以及该石柱的边长。所有实数均精确到 2 位小数，范围在 0 到 1000 之内。输出(dragon.out)：输出文件 dragon.out 仅包含一个实数表示把圆石推到祭坛中心的最短路线长度，输出结果保留到两位小数。你可以假设总存在一条把圆石推到祭坛中心的路。输入样例(dragon.in)：0 0 10 30 40110 10 10输出样例(dragon.out)：5793修玛思索良久，果断地走到圆石旁边，用力推动这块巨石。圆石在修玛的推动下，缓缓地滚动起来。修玛时不时地调整着推动的角度，以使巨石朝着自己希望的方向滚动。终于，“卡嗒”的一声，圆石安安稳稳地滚到了祭坛的中心。一束光从神殿顶上直射而下，笼罩了整个祭坛。修