第二届中兴捧月校园程序设计大赛题目
一、 俄罗斯套娃奖品伊万洛夫在比武大会上力克群雄,成为新一届“草原雄鹰”,为部落赢得了莫大荣誉。首领决定要重重奖赏,他对伊万洛夫说:“孩 子,你是知道的,面前的这片草原,南北向和东西向的道路纵横交错。现在,路口放着纯金打造的俄罗斯娃娃,重量大小不等,重的 都能装下轻的。你可以沿着道路飞奔,拾取路口的娃娃,要求是任何时刻必须是一个套娃,装好后就不能再拆开了。注意不要走重复路。”请你为伊万洛夫规划路线,使得他能够有最大的收获。Input: cross.txt 输入包括多组测试用例; 每个测试用例开始是一对整数<R, C>,R表示东西向道路数,C表示南北向道路总数;接下来R行,每行包括C个正整数(或0)Wr,c,分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量(或表示没有放置娃娃)。Output: 输出能有最大收获的路径规划。假设1: cross.txt 2 7 1 2 13 6 7 12 11 14 3 4 5 8 9 10输出:1 2 3 4 5 6 7 8 9 10 11 12假设2: cross.txt 5 5 1 16 15 14 13 2 17 24 23 12 3 18 25 22 11 4 19 20 21 10 5 6 7 8 9输出:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25注释:1)从<0,0>出发;2)路线不能重复;3)不要求最后回到出发点。二、 教师家访安排输入文件:student.txt distance.txt你是小学某班主任,需要安排周六进行家访。于是打电话与家长联系,他们表示虽然比较忙,但还是会为你抽出一点时间。由于有些家长时间上有冲突,并且一天内不能拜访所有家长,你需要一个程序安排一天的工作,使得你可以拜访最多的家长。注意, 如果与某个家长见面,拜访时间不得少于45分钟(M),否则可能引起家长不满意。另外从一个家长到另外一个家长需要花费一些时间。Input1: student.txt输入包括多个测试数据,每个测试数据开头是一个整数n(1<=n<=40),表示家长总数。接下来n行每行包括三个正整数m、s、t。m表 示家长的序号,s、t分别表示该家长空闲时间段的起始时间和终止时间,s小于t。注意两个数字的最后两位表示分钟。比如1645 表示16时45分样本如下: 6 1 800 1100 2 800 900 3 845 1000 4 1300 1400 5 1345 1800 6 1500 1700Input2: distance.txt第一行为 家长总数随后为一个二维表格,记录每2个用户之间的距离。第二行和第一列数据为家长顺序编号。其他数据为2个家长之间的距离。样本如下:60 1 2 3 4 5 61 0 1 2 4 3 12 1 0 3 5 3 23 2 3 0 6 1 34 4 5 6 0 4 145 3 3 1 4 0 156 1 2 3 14 15 0Output:拜访的家长总数拜访的家长的序号和开始结束时间三、 布雷程序在一个10*10的方格中,随机分布10个地雷,并在其它没有地雷的格中显示该方格周围相邻的方格中共有几枚地雷。样例输出:(图中-1的位置表示地雷,其它值表示该位置相邻的八个格子中的地雷数)基本要求:掌握程序循环和算法设计的基本方法;掌握复杂算法设计的方法四、 电路业务合并在网络电路,为了表示1条电路表示成速率、A、方向、Z. 1、速率有VC12,VC4等。 2、方向为单向->、双向<->。 3、节点A(或Z)包括网元名称、单板、端口号。电路在开通时,为了方便管理,往往每组电路是连续的。如:VC12 22局S385扩1 EPE11-1-2 2 <-> 23局S385扩1 EPE11-1-2 2如果电路太多一条一条显示则信息量太大,用户查看很不方便。现在用户要求连续的电路合并起来显示。连续的电路是如果两条业务A1Z1,A2Z2. 如速率一样,A1和A2网元名称,单板一样,断口号相邻。Z1和Z1网元名称,单板一样,断口号相邻。且方向一致。它们就可以合并。未排序合并前:基本要求:请设计出一个合并方法,要求第一要快,第二内存消耗低。为示例下面是一张合并后的图形数据截图:一个测试数据:原始数据不一定排序,这个数据是Excel多页输出的结果,同学们可以把两页之间的页码序去掉,如excel中1 168表示168页中第1页。为简化处理,可以拷贝数据到文本文件中,输出结果也输出到文本文件中,给这样一个数据是让大家感觉到合并的作用。大图及数据表详见附件五、 网游题目收集系统在网络游戏中,为了防止外挂的使用,往往在游戏过程中会弹出一些选择题,让玩家来答题。作为游戏爱好者,又作为未来程序员的你,想做一个题目收集系统辅助答题:在游戏过程中,如果出现题目,程序首先去搜索题库,看有没有该题目及其答案,如果有就用题库的答案做答,如果没有,就立即发出告警声音,提示玩家做答。 玩家答完,此题目及其答案题库。要求:1、从游戏中取题过程作为简化手工实现,题目可以键盘录入。2、多个玩家可以共享一个题库,各玩家答各自题目。3、如果玩家A在1分钟之内没有答题,其他玩家可以替他答题。其它玩家可以指定优先顺序六、 PLL (Phase Locked Loop)锁相环某芯片中,使用了如下特征PLL。在确定的参考频率下,PLL可输出系列频点;指定任意频率,编写一段代码,计算出配置参数,使PLL输出频率最接近指定的频率。请注意,不允许使用遍历和查表方式。 PLL参数及说明:这个PLL默认输出频率为312M。只有在gsm部分时钟104M时钟占空比为1:1,它可配置为624M,否则这个PLL永远输出为312M。 PD: PLL power down控制配置位。 1:power down;0:正常模式。 LD: PLL是否锁定指示信号。1:locked; 0: unlocked。 BS1:0 频段选择。00: low-band 100M<= fvco<=300M ;01: middle_band 300M<= fvco<=600M;10: high-band, 600M<= fvco<=1000M; 11: 禁止这样配置。 OD1:0: 输出时钟分频指数,分频系数为:2od1:0.R4:0 : 参考时钟输入分频系数。F5:0 : 反馈时钟分频系数。 输出时钟的计算公式如下: NR = R4:0 +1 NF = F5:0 +1 NO= 2od1:0 FREF = Fin/NR FVCO = FREF * NF Fout = FVCO/NO电视墙也就是电视背景装饰墙,是居室装饰特别是大户型居室的重点之一,在装修中占据相当重要的地位,电视墙通常是为了弥补客厅中电视机背景墙面的空旷,同时起到修饰客厅的作用。因为电视墙是家人目光注视最多的地方,长年累月地看也会让人厌烦,所以其装修就尤为讲究