《上交acm04-05赛季机试》由会员分享，可在线阅读，更多相关《上交acm04-05赛季机试（9页珍藏版）》请在金锄头文库上搜索。
1、Shanghai Jiaotong University Programming Contest 2004Problem A. Fibonacci NumberInput file:a.in Time limit:5 secondsThe Fibonacci Numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 are defined by the recurrence:F0= 0F1= 1Fi= Fi1+ Fi2for all i 2Write a program to calculate the Fibonacci Numbers.InputThe fir
2、st line of the input file contains a single integer T, the number of test cases. The following T lines, each contains an integer n ( 0 n 45 ), and you are expected to calculate Fn.Output Output Fnon a separate line.Sample input and outputa.inSTANDARD OUTPUT 5 0 3 5 9 200 2 5 34 6765Page 1 of 9Shangh
3、ai Jiaotong University Programming Contest 2004Problem B. Word ReversalInput file:b.in Time limit:5 secondsGiven a list of words, print the words reversed on separate lines. Each word consists of English letters only.InputThe input consists of T test cases. The number of test cases (T) is given in t
4、he first line of the input file. Each test case consists of a single line, each line contains a word.Output For each test case, print the word reversed on one line.Sample input and outputb.inSTANDARD OUTPUT 2 HelloWorld MadamdlroWolleH madaMPage 2 of 9Shanghai Jiaotong University Programming Contest
5、 2004Problem C. Adding 1s, 2s, and 3sInput file:c.in Time limit:5 secondsInteger 4 can be expressed as a sum of 1s, 2s, and 3s in seven different ways as follows:1 + 1 + 1 + 1,(1)1 + 1 + 2,(2)1 + 2 + 1,(3)2 + 1 + 1,(4)2 + 2,(5)1 + 3,(6)3 + 1.(7)Write a program that determines the number of ways in w
6、hich a given integer can be expressed as a sum of 1s, 2s, and 3s. You may assume that the integer is positive and less than 20.InputThe input consists of T test cases. The number of test cases (T ) is given in the first line of the inputfile. Each test case consists of an integer written in a single
7、 line.Output Print exactly one line for each test case. The line should contain an integer representing the number of ways.Sample input and outputc.inSTANDARD OUTPUT 3 4 7 107 44 274Page 3 of 9Shanghai Jiaotong University Programming Contest 2004Problem D. Triangle CentersInput file:d.in Time limit:
8、5 secondsGiven the lengths of three sides of a triangle ABC, you are asked to find the following four distances.(1) FA + FB + FC. F is the point X which minimizes the sum of distances from A, B, and C in XA+XB +XC.(2) IA + IB + IC. I is the intersection of Angle Bisectors, and it is the interior poi
9、nt for which distances to the sidelines are equal.(3) GA + GB + GC. G is the intersection of Medians, and it is the centroid of ABC.(4) OA + OB + OC. O is the intersection of Perpendicular Bisectors, and it is the point for which distances to A, B, C are equal.InputThe input consists of T test cases
10、. The number of test cases (T ) is given in the first line of the inputfile.Each of the next T lines contains one test case. Each case contains three integer numbers a, b, c where a is the distance between B and C, b is the distance between C and A and c is the distance between A and B. The importan
11、t condition is 0 a,b,c 1000, and it is guaranteed that the triangle is non-degenerate.OutputFor each set of input you should output four floating-point numbers DF, DI, DG, DO, all of which have exactly three digits after the decimal point. HereDF= FA + FB + FCDI= IA + IB + ICDG= GA + GB + GCDO= OA +
12、 OB + OCSample input and outputd.inSTANDARD OUTPUT 3 3 4 5 10 10 10 4 5 86.766 6.813 6.918 7.500 17.321 17.321 17.321 17.321 9.000 9.316 9.530 14.667Page 4 of 9Shanghai Jiaotong University Programming Contest 2004Problem E. Jimmys RiddlesInput file:e.in Time limit:5 secondsLittle Jimmy is only three
13、 years old but appears to be more intelligent than even Sir Isaac Newton at theage of three. People say that Jimmy could count up to ten when he was a child of ten months. His field ofinterest changes with his age and at present he is researching on how to trouble his mother scientifically. He has a
14、 book of 5000 riddles and applies them every now and then. For example, if his mother asks him “ Will you stop watching Tom and Jerry? ” he will say “ tom hates jerry, jimmy hates tom” which means, “ yes I will ”. Obviously his mother is in all sorts of trouble.However, Jimmy is considerate. After a
15、ll, he knows that his days will not be very smooth if he continues annoying his mother this way. So he taught her a number of ridiculous (riddle calculus) formulas so that she can quickly interpret Jimmys riddles. But, she was a student of history and doesnt know much about ridiculous formulas. So,
16、you are to help her to get out of this trouble. You are to write a program that will read a number of riddles and, by using a number of ridiculous formulas, determine what they mean. The formulas are given below: STATEMENT = ACTION | STATEMENT , ACTION ACTION = ACTIVE LIST VERB ACTIVE LIST ACTIVE LIST = ACTOR | ACTIVE LIST and ACTOR ACTOR = NOUN | ARTICLE NOUN ARTICLE = a | the NOUN = tom | jerry | goofy | mickey | jimmy | dog | cat | mouse VERB = hate | love | kno
