注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

山东省信息学奥赛选拔赛第三试试题  

2014-09-02 09:16:46|  分类: 教书育人 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

山东省信息学奥赛选拔赛第三试试题
(2005年5月5日)

1.阶梯教室设备利用(REZ.PAS)
问题描述:
我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定,如果两个演讲时间有部分或全部重复,那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室,也就是说,我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。
任务:
请写一个程序:
? 在文本文件REZ.IN中读入所有演讲的起始和终止时间;
? 计算最大的可能演讲总时间;
? 把结果输出到文本文件REZ.OUT中。
输入格式(REZ.IN):
文本文件REZ.IN的第一行包括一个正整数n,n ? 10000,为所有的演讲的数目。以下的n行每行含有两个由空格隔开的整数p和k,0 ? p < k ? 30000。这样的一对整数表示一个演讲由时间p开始到时间k结束。
输出格式(REZ.OUT):
在文本文件REZ.OUT输出唯一的一个整数,为最长的演讲总时间。

输入输出样例:
输入(REZ.IN):
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
输出(REZ.OUT):
16



2.位图(BIT.PAS)
问题:
现在我们给出一个n?m的单色位图,且该图中至少含有一个白色的像素。我们用(i, j)来代表第i行第j列的像素,并且定义两点p1=(i1, j1)和p2=(i2, 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中输出一个n?m的数表,其中的第i行的第j个数字为f(i, j)表示像素(i, j)到最近的白色像素的距离。
输入输出样例:
输入(BIT.IN):
3 4
0001
0011
0110
输出(BIT.OUT):
3 2 1 0
2 1 0 0
1 0 0 1

3.遗传代码(PIE.PAS)
题目描述:
抽象的primitivus (Primitivus循环)的遗传代码是一系列自然数K=(A1,...,An)。我们所说的primitivus的特征是安排一对在遗传代码中接连出现的数(l,r),如果存在i则l=Ai, r=Ai+1。在primitivus的遗传代码中没有(p,p)特征。
任务:
写一个程序:
1.从文本文件读特征列表,
2.计算所给特征的最短遗传代码长度,
3.把结果写到输出文件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):
12
2 3
3 9
9 6
8 5
5 7
7 6
4 5
5 1
1 4
4 2
2 8
8 6

样例输出(PIE.OUT):
15
备注:
在下列遗传代码中来自文件PIE.IN的所有遗传代码将被列出:
(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)


4.屠龙传说-屠龙枪卷(dragon.PAS)
先知看到修玛取回的药草,满意地点了点头。他对修玛说:“跟我来”。修玛顺从地跟着先知走到了他的房间里。先知的房间很大,四周满是书架,整整齐齐地摆放着一排排书籍。房间中间的圆桌上摆放着一个巨大的水晶球,它发出的荧光照亮了整个房间。先知走到一排书架前,从中抽出一本薄薄的书来。这本书看起来十分古老,纸张都变成了黄色,有的地方已经发黑。修玛想,这本书的历史大概有好几百年了吧。先知示意修玛坐下,他翻开手中的书,对修玛说道:“我已经研究这本书很久了。它是用一种古老的文字写成的,记载了一个十分古老的传说。书中提到,普通的武器是无法伤害巨龙的,只有诸神合力锻造的屠龙枪才能消灭它。为了防止屠龙枪被滥用,神把它封印在卡基思山上,只有拥有超人的勇气、力量和智慧的人才能解开这个封印。千百年来,很多人都想得到屠龙枪的力量,然而从没有人成功过。我查阅了所有有关屠龙枪的记载,悉心地研究那些资料,得知屠龙枪被封印在山顶的神殿中,而要解开这道封印,就必须把神殿中的一块巨大的圆石推到神殿祭坛的中心,然后念出解开封印的咒语。”修玛问道:“那句咒语应该已经失传了吧?”“不,恰恰相反。”先知说,“这句咒语一直记载在这本书中,并被完好地保存下来。”“那么,剩下的只是把圆石推到祭坛的中心了。”修玛自信地笑了。然而先知却摇了摇头,“不,修玛,事情没有你想象的那么简单。爬上卡基思山就不是一件容易的事。它高耸入云,四周都是光秃秃的石壁,几乎没有落脚的地方。只有真正的勇士才能爬得上去。那块圆石也不是那么容易就能推动的,非得有超常的力量不可。这些东西,修玛你都有。但如果仅仅只有这些,那么屠龙枪早已被人拿到手了。书中不是说了么,要有勇气、力量和智慧。智慧才是真正的关键。如果在固定时间内不能把那块圆石推到祭坛的中心,那么圆石便会自动滚回原处,同时推石的人将永远无法再次推动这块圆石。而且不管你用多大力气推,这块圆石都不可能滚动得像你希望的那样快,我估计只有按照最短路线去推这块圆石,才能在固定时间内把它推到祭坛中心。神殿中又有着大大小小的石柱,有些石柱与石柱之间的空隙很小,根本就推不过去。正因为这种种困难,才没有人能够从神殿中取走屠龙枪。”修玛沉默了一会儿,说:“不管如何,我也要去试一试。如果我不能拿到屠龙枪,就没有人能够拿到它了。”先知点了点头,说:“去吧,修玛。记住,用你的智慧。”
修玛骑马奔驰了十天十夜,终于来到了卡基思山脚下。正如先知所说的那样,这座山根本就没有路可以上去,甚至找不到可以落脚的地方。然而修玛凭着他的勇气以及熟练的技巧,爬上了山顶。他走进神殿,一眼就看到了那块巨大的圆石。修玛该怎么做,才能把圆石推到祭坛的中心呢?
任务:
你的任务是计算出把圆石推到祭坛中心的最短路线长度。所谓推到祭坛中心是指圆石的中心与祭坛中心重合。圆石中心的初始位置以及祭坛中心的位置是已知的。圆石半径为R,它可以朝着任意方向滚动。洞中所有石柱均为正四棱柱,大小不一。在推动圆石的过程中,要求圆石中心与所有石柱的距离均不小于R,否则圆石将被石柱阻挡而不能继续滚动。
输入(dragon.in):
输入文件dragon.in第一行包含了五个实数,依次表示圆石中心的初始位置的x坐标、y坐标、圆石半径R、祭坛中心的位置的x坐标以及y坐标。第二行包含一个整数N(0<=N<=20),表示神殿中石柱的数目。接下去N行每行包含三个实数,给出了一根石柱的信息。第I+2行的三个实数依次表示第I根石柱左下角x坐标、y坐标以及该石柱的边长。所有实数均精确到2位小数,范围在0到1000之内。

输出(dragon.out):
输出文件dragon.out仅包含一个实数表示把圆石推到祭坛中心的最短路线长度,输出结果保留到两位小数。你可以假设总存在一条把圆石推到祭坛中心的路。

输入样例(dragon.in):
0 0 10 30 40
1
10 10 10
输出样例(dragon.out):
57.93

修玛思索良久,果断地走到圆石旁边,用力推动这块巨石。圆石在修玛的推动下,缓缓地滚动起来。修玛时不时地调整着推动的角度,以使巨石朝着自己希望的方向滚动。终于,“卡嗒”的一声,圆石安安稳稳地滚到了祭坛的中心。一束光从神殿顶上直射而下,笼罩了整个祭坛。修玛对着祭坛,大声地念出了解开封印的咒语。顿时,祭坛开始颤动,中间的圆石也随着摇摆不定。突然间,整块圆石完全爆裂开来,在祭坛的中心,出现了一柄长枪。枪身上闪烁着神圣的光芒,令人惊羡不已。修玛走上前去,拔起了这柄枪。他感到一股强大的力量从手上传了过来。修玛随手把枪一挥,只听得“哗啦”一声,一根巨大的石柱应声四分五裂了。修玛又惊又喜,他知道这一定就是屠龙枪。

  评论这张
 
阅读(67)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017