2009程序设计竞赛复赛试题.doc

西北农林科技大学 2009年程序设计竞赛(信息类)复赛 竞赛指南 一共5个竞赛题,分值不同,竞赛时间为3小时,请参赛同学注意合理安排时间和选题. 参赛选手需要理解题意,设计有关算法,调试、运行程序,编写C/C++/JAVA/C#的源程序,并撰写纸质答题报告,报告的质量是评分的重要依据.对每道竞赛题,请至少自行设计一组测试用例,并给出该用例的计算结果,填入在答题报告中. 请竞赛选手以自己的学号建立主目录,以题号建立子目录存放竞赛题的相关文档.例如学号为l005号的参赛者应建立”l005/1”的文件夹,用以存放第一题的全部文档.如果使用VC++进行开发,需要提供C/CPP/H文件、工程文件、EXE文件等；如果使用ECLIPSE开发,需要提供JAVA文件、CLASS文件等；如果使用C#开发,要提供.CS文件、EXE文件等. 在竞赛结束后,请竞赛选手在“主目录”处打压缩包.压缩包名可以是“学号.rar”或者“学号.zip”.请将压缩包保存在桌面上. 参赛者在登记时填写真实信息,其它环节中不允许任何个人信息出现,否则取消参赛资格. 参赛者可携带纸质英汉词典,禁止携带其它资料. 2009年程序设计竞赛复赛试题 1. 悠闲的蜗牛(15分) 2 2. 数制转换(20分) 3 3. Train Problem(20分) 4 4. Lake Counting(20分) 6 5. A DP Problem(25分) 7 信息工程学院 2009年5月 悠闲的蜗牛(15分) Problem Description 小蜗牛走路非常慢而且速度不变,所以他懂得如何珍惜时间. 虽然如此,他仍然坚持每天晚饭后出去散步. 他总是绕着大小不同的正方形草坪走,为了知道自己走了多长的路程,所以每走一米他总是要在脚下标示出他所走的路程（相当于高速公路边上的里程牌）,好在他回家的时候计算出自己今天散步所花费的时间. 现在请你来编写一个程序,来帮助小蜗牛标示自己的散步路线. Input 正方形草坪的边长. Output 输出小蜗牛的散步路线,每个数字占两格,右对齐. 格式详见Sample Output. Sample Input 4 Sample Output 1 2 3 4 12 5 11 6 10 9 8 7 数制转换(20分) Problem Description 给出任意进制的一个整数，求这个数的10进制值。 Input 输入为一行数据，包括两个整数。 第一个数是任意进制的一个整数，第二个数是这个整数采用的进制。 Output 输出这个整数的10进制数值。 Sample Input1 25 6 Sample Output1 17 Sample Input2 15 8 Sample Output2 13 Hints 8进制15的数值计算方法： 1*8^1+5*8^0=13 Train Problem(20分) Problem Description As the new term comes, the Railway Station is very busy nowadays. A lot of student want to get back to school by train. But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A cant leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2. Input The input contains se