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

The 3rd Programming Contest Of NWSUAF西北农林科技大学2009年程序设计竞赛(信息类)复赛l 竞赛指南1、 一共5个竞赛题,分值不同,竞赛时间为3小时,请参赛同学注意合理安排时间和选题.2、 参赛选手需要理解题意,设计有关算法,调试、运行程序,编写C/C+/JAVA/C#的源程序,并撰写纸质答题报告,报告的质量是评分的重要依据.对每道竞赛题,请至少自行设计一组测试用例,并给出该用例的计算结果,填入在答题报告中.3、 请竞赛选手以自己的学号建立主目录,以题号建立子目录存放竞赛题的相关文档.例如学号为l005号的参赛者应建立”l005/1”的文件夹,用以存放第一题的全部文档.如果使用VC+进行开发,需要提供C/CPP/H文件、工程文件、EXE文件等；如果使用ECLIPSE开发,需要提供JAVA文件、CLASS文件等；如果使用C#开发,要提供.CS文件、EXE文件等.4、 在竞赛结束后,请竞赛选手在“主目录”处打压缩包.压缩包名可以是“学号.rar”或者“学号.zip”.请将压缩包保存在桌面上.5、 参赛者在登记时填写真实信息,其它环节中不允许任何个人信息出现,否则取消参赛资格.6、 参赛者可携带纸质英汉词典,禁止携带其它资料.2009年程序设计竞赛复赛试题1.悠闲的蜗牛(15分)22.数制转换(20分)33.Train Problem(20分)44.Lake Counting(20分)65.A DP Problem(25分)7信息工程学院2009年5月 1. 悠闲的蜗牛(15分)Problem Description小蜗牛走路非常慢而且速度不变,所以他懂得如何珍惜时间. 虽然如此,他仍然坚持每天晚饭后出去散步. 他总是绕着大小不同的正方形草坪走,为了知道自己走了多长的路程,所以每走一米他总是要在脚下标示出他所走的路程（相当于高速公路边上的里程牌）,好在他回家的时候计算出自己今天散步所花费的时间. 现在请你来编写一个程序,来帮助小蜗牛标示自己的散步路线. Input正方形草坪的边长. Output输出小蜗牛的散步路线,每个数字占两格,右对齐. 格式详见Sample Output. Sample Input4 Sample Output 1 2 3 412 511 610 9 8 72. 数制转换(20分)Problem Description给出任意进制的一个整数，求这个数的10进制值。Input输入为一行数据，包括两个整数。第一个数是任意进制的一个整数，第二个数是这个整数采用的进制。Output输出这个整数的10进制数值。Sample Input125 6 Sample Output117Sample Input215 8 Sample Output213Hints8进制15的数值计算方法： 1*81+5*80=133. Train Problem(20分)Problem DescriptionAs 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.InputThe input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. More details in the Sample Input.OutputThe output contains a string No. if you cant exchange O2 to O1, or you should output a line contains Yes., and then output your way in exchanging the order(you should output in for a train getting into the railway, and out for a train getting out of the railway). Print a line contains FINISH after each test case. More details in the Sample Output.Sample Input3 123 3213 123 312Sample OutputYes.inininoutoutoutFINISHNo.FINISHHintsFor the first Sample Input, we let train 1 get in, then train 2 and train 3.So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1.In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3.Now we can let train 3 leave.But after that we cant let train 1 leave before train 2, because train 2 is at the top of the railway at the moment.So we output No.4. Lake Counting(20分)Problem DescriptionDue to recent rains, water has pooled in various places in Farmer Johns field, which is represented by a rectangle of N x M (1 = N = 100; 1 = M = 100) squares. Each square contains either water (W) or dry land (.). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.Given a diagram of Farmer Johns field, determine how many ponds he has.Input* Line 1: Two space-separated integers: N and M* Lines 2N+1: M characters per line representing one row of Farmer Johns field. Each character is either W or . . The characters do not have spaces between them.Output* Line 1: The number of ponds in Farmer Johns field.Sample Input10 12W.WW.WWW.WWW.WW.WW.WW.W.W.W.W.W.WW.W.W.W.W.W.W.W.W.W.Sample Output3HintsThere are three ponds: one in the upper left, one in the lower left,and one along the right side.5. A DP Problem(25分)DescriptionIn this problem, you are to solve a very easy linear equation with only one variable x with no parentheses! An example of such equations is like the following:2x 4 + 5x + 300 = 98xAn expression in its general form, will contain a = character with two expressions on its sides. Each expression is made up of one or more terms combined by + or - operators. No unary plus or minus operators are allowed in the expressions. Each term is either a single integer, or an integer followed by the lower-case character x or the single character x which is equivalent to 1x.You are to write a program to find the value of x that satisfies the equation. Note that it is possible for the equation to have no solution or have infinitely many. Your program must detect these cases too.InputThe first number in the input line, t (1 = t = 10) is the number of test cases, followed by t lines of length at most 260 each containing an equation. There is no blank character in the equations and the variable is always represented by the lower-case character x. The coefficients are integers in the range (0.1000) inclusive.OutputThe output contains one line per test case containing the solution of the equation. If s is the solution to the equation, the output line should contain s (the floor of s, i.