华南农业大学 2009 ACM题目.doc

6754Keyboard of a Mobile Telephone时间限制:500MS 内存限制:1000K提交次数:0 通过次数:0 题型: 编程题语言: 无限制描述Now almost every student has a mobile telephone. But do you have making attention to the keyboard of a mobile telephone? This is the keyboard of a normal mobile telephone： It will show different letters if you press one key different times, for example you press the key “2” once it will show a letter a, twice show a b. And notice that press the key 0 once will show a space. Now give you a sentence, which contains only lowercases and space, calculate how much times to press the keyboard at least to show the sentence. InputThe first line contains an integer n, which means the number of cases. Per case consist of only one sentence, which contains only lowercases and spaces and its length less or equal 200. OutputPer case output an integer, which is the least times to press the keyboard, in one line.Sample Input1this problem is so easySample Output53 SourceBy Hanqiu6755Right-angled Triangle时间限制:612MS 内存限制:1000K提交次数:0 通过次数:0 题型: 编程题语言: 无限制描述Right-angled triangle is very important in plane geometry, just as the primes in numeral system. Now there is an interesting problem about right-angled triangle. As we all know, if we choose three points in a coordinate system and these points according to some conditions, they can form a right-angled triangle. And there is an example in the picture: the OPQ forms a right-angled triangle. If give a integer n, there are many ways to choose two points that according three condition： 1) each co-ordinate is integer 2) lies between 0 and n inclusive, that is 0 = x1, y1, x2, y2 = n, 3) the two points and the origin point can form a right-angled triangle. And the following picture is one example which n = 2, and it shows that there are 14 different ways to choose two points to forms a right-angled triangle with origin point And this is the problem, give you a integer n, you should calculate how many ways to choose two different points, both satisfy the three conditions above. InputThe first line of input is an integer m（2= m = 20）, which specifies the number of case to follow. Each case per line, contains only one integer n(2 = n = 50). OutputPer case output an integer, which is the way to choose those two points and per case one line.Sample Input223Sample Output1433SourceBy Hanqiu6756War At Trafalgar时间限制:500MS 内存限制:1000K提交次数:0 通过次数:0 题型: 编程题语言: 无限制描述A.D. 1555 , French prophet Nostradamus had predicted that a tough man would born in a poverty family and became the king of France . 1804 , his prediction came true , Napolon Bonaparte became the king of The First Empire of France . It is all known that Napoleon was defeated in Waterloo . But there was another defeat during his life . At Trafalgar , 1803 , he was defeated by the military of France and England , which was lead by General Horatio Nelson . During the war , French Army was separated into n teams , numbered from 1 to n . Since the ability of each team leader was different , each team had two damage value ai , bi . ai means the Original-Attack-Value of team i , bi means Support-Attack-Value of team i . If English Army attacked team i , team i+1 would help team i to defence . So if attacked team i it would get a(i-1)*b(i )*min(ai , bi-1) damage . If one team has been attacked , it would be defeated soon . After that , the remaining soldiers would merged with the team which was on the left an next to them . After two teams merged , ai and bi would changed , ai would became original ai of which team in the left side , and bi would became original bi in right side . But there is one important thing , Napolon was the leader of team 1, so the army could not attacked team 1 , unless there was only one team left . In this situation , it would give a1+ b1 damage . Now , we want to know , what is the minimal damage in total when we destroy French Army ? InputThe first line is an integer T(=20) , indicate the number of test cases The first line of each test case , there is an integer n (n=200) , indicate the number of teams After that there are n lines , each line have two integers ai , bi , indicate the harm value of team i . You can assume the result is fits 32bit integer . OutputFor each test case , output one integer indicate the minimal total hurt . The output format please follow sample .Sample Input22100 991 331 22 51 6Sample OutputCase 1 : 403Case 2 : 23HintIn sample 2 , the situation is as follow : There are 3 teams , a1 = 1 , b1 =2 , a2 = 2 , b2 = 5 , a3 = 1 , b3 = 6 English Army attack team2 , get a1*b2*min(b1,a2)1*5*2=10 damage , and then team1 and team2 will merge The damage will become as follow : a1 = 1 . b1 = 5 , a3 = 1 , b3 = 6 (team2 has been defeated) Then attack team3 , get a1*b3*min(b1,a3)=6 damage , and merge team1 and team3 , then a1 = 1 , b1 =6 And then attacked from left side , French Army was destroyed . The minimal total damage is 23 = 10 + 6 + 1 + 66757Busy Shopping时间限制:5000MS 内存限制:1000K提交次数:0 通过次数:0 题型: 编程题语言: 无限制描述Beijing Road is one of most famous shopping streets in Guangzhou, the Capital of Guangdong province. There are a lot of shops. Some of them sell shoes, some sell clothes, some sell food Now, Mr. Chen is going to Beijing Road for shopping. He has a lot of things need to buy. As everyone known, Mr. Chen is busy man. So he want spend less time as possible for shopping. Lets suppose that the shops in Beijing Road are arranged in a straight line, one by one. Mr. Chen can choose a shop as the beginning. Then he can move to the next nearby shop one by one. Every shop has a code which represented what kind of products the shop sells. Now, Given the codes of all shops and the codes of the products which Mr. Chen need, can you tell Mr. Chen how many shops he would pass by(or enter) at least if he get all products he need. (Suppose that Mr. Chen can find all products he need in Beijing Road) InputThe input consists of T test cases. The number of test cases (T ) is given in the first line. Each test case begins with a line containing two integer N,M , 1=M=N= 100000, N represents the number of shops in the road, and M represents the number of products Mr. Chen need. Then, One of the next two lines contains N positive integers CI, 0=I are cases test remaining the line, 5th From need. Chen Mr. which product J-th of code representing DJ 0=J OutputFor each case, output the number of shops which Mr. Chen would pass by(or enter) at least. Sample Input24 23 8 2 33 26 31 4 5 4 3 11 3 5Sample Output24HintHint: Look at the sample input above. The first line is 2, means that there are two cases. The next 3 lines belong the case No.1. The 5th-7th lines belong the case No.2. In the case 1, the answer is 2 because the short path is 2 3, which begin from No.3 shop and end at No.4 shop. In the case 2, the answer is 4 because the short path is 5 4 3 1, which begin from No.3 shop and end at No.6 shop. 6758Logic时间限制:500MS 内存限制:1000K提交次数:0 通过次数:0 题型: 编程题语言: 无限制描述Mary is a freshmen, this semester she had an elective course Discrete Mathematics. Her teacher, Miss Lin gave her an after-school problem. Poor Mary spent a long, long time on it and did not make it out. The deadline is coming up. She is very anxious, and hoped a programming expert who can do her a favor, tell an approach to solve it. The problem is as follows: Given several formula（公式） like “variable1 relation variable2”, where relation may be , variables may contain up to 10 letters or digits and are case-sensitive. Please determine whether there is a conflict. InputThere are several cases. Each case begins with a line “Case%d:”, (%d is the case number), and the followed lines contains several formulas, one per line. There are no more than 100 formulas for each case. Please see sample input for more details. Input is terminated by an EOF.OutputIf there is no conflict, output “Ac”, otherwise, output “Wa”. Please refer to sample output for the exact output format.Sample Input22xyz 123123 452x yy xSample OutputCase1:AcCase2:Wa6760Silk_Road时间限制:4170MS 内存限制:1000K提交次数:0 通过次数:0 题型: 编程题语言: 无限制描述Long time ago, there were n cities in a country named ABP(A Beautiful Place). There was an interconnected network of trade routes among some of the cities. Realized that a powerful nation was based on good connection among the cities, the King of the country make a decision to set up a freeway network, which is also known as the Silk Road Project. The king selected k wealthy cities to take the lead in setting up the freeway network. Here are the Silk Road Projects rules: 1. In order to save costs, the freeway must be built at the basis on the original routes. 2. Every two selected cities can connect to each other by the freeway. 3. There will be no more than 10