?
編程環境：VC++6
考試時間：3小時
Problem A.Fibonacci
Input:????????? ?fib.in
Output:??????? Standard Output
Time limit:??? ?5 second
Memory limit: 64 megabytes
Offerd by ：??
http://spaces.msn.com/davidblogs/?
The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurrence:
F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
Write a program to calculate the Fibonacci Numbers.
?
Input
The input file contains a number n and you are expected to calculate Fn.(0<=n<=30)
Output
Print a number Fn on a separate line,which means the nth Fibonacci Number.
?
Example
fib.in?????? Standard Output
1??????????? 1
2??????????? 1
3??????????? 2
4??????????? 3
5??????????? 5
6??????????? 8
?
Problem B.WERTYU
Input:????????? ?wertyu.in
Output:?????? ? Standard Output
Time limit:???? ?5 second
Memory limit:? 64 megabytes
Offerd by ：??
http://spaces.msn.com/davidblogs/
?
A common typing error is to place the hands on the keyboard one
row to the right of the correct position.So "Q" is typed as "W" and "J"
is typed as "K" and so on.You are to decode a message typed in this
manner.
?
` 1 2 3 4 5 6 7 8 9 0 - = BackSp
Tab Q W E R T Y U I O P [ ] \
A S D F G H J K L ; ' Enter
Z? X? C? V? B? N? M? ,? .? /
Control Alt? Space? Alt Control
?
Input
The input file consist of several lines of text.Each line
may contain digits,spaces,upper case letters(except Q,A,Z),or
punctuation shown above(except back-quote(') which is left to the key
"1").Keys labelled with words [Tab,BackSp,Control,etc.] are not
represented in the input.
?
Output
You are to replace each letter or punctuation symbol by
the one immediately to its left on the QWERTY keyboard shown
above.Spaces in the input should be echoed in the output.
?
Example
wertyu.in???????????????????
?Standard Output
O S, GOMR YPFSU/??????? I AM FINE TODAY.
?
?
Problem C.String Matching
Input:????????? ??matching.in
Output:?????? ? Standard Output
Time limit:???? ?5 second
Memory limit:? 64 megabytes
Offerd by ：??
http://spaces.msn.com/davidblogs/?
Finding all occurrences of a pattern in a text is a problem that
arises frequently in text-editing programs.Typically,the text is a
document being edited,and the pattern searched for is a particular word
supplied by the user.
?
We assume that the text is an array T[1..n] of length n and that
the pattern is an array P[1..m] of length m<=n.We further assume
that the elements of P and T are all alphabets(∑={a,b...,z}).The
character arrays P and T are often called strings of characters.
?
We say that pattern P occurs with shift s in the text T if
0<=s<=n and T[s+1..s+m] = P[1..m](that is if T[s+j]=P[j],for
1<=j<=m).
?
If P occurs with shift s in T,then we call s a valid shift;otherwise,we call s a invalid shift.
Your task is to calculate the number of vald shifts for the given text T and pattern P.
?
Input
In the input file,there are two strings T and P on a
line,separated by a single space.You may assume both the length of T
and P will not exceed 10^6.
?
Output
You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.
?
Example
matching.in????? ?Standard Output
aaaaaa a????????? ??6
abababab abab?? 3
abcdabc abdc??? ?0
?
Problem D.Exponential Form
Input:????????? ? form.in
Output:?????????Standard Output
Time limit:????? 5 second
Memory limit:? 64 megabytes
Offerd by ：??
http://spaces.msn.com/davidblogs/?
Every positive number can be presented by the exponential form.For example,
137 = 2^7 + 2^3 + 2^0
Let's present a^b by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0).
Since 7 = 2^2 + 2 + 2^0 and 3 = 2 + 2^0 , 137 is finally presented by 2(2(2)+2+2(0))+2(2+2(0))+2(0).
?
Given a positive number n,your task is to present n with the exponential form which only contains the digits 0 and 2.
?
Input
The input file contains a positive integer n (n<=20000).
?
Output
You should output the exponential form of n an a single
line.Note that,there should not be any additional white spaces in the
line.
?
Example
form.in
137
Stardard Output
2(2(2)+2+2(0))+2(2+2(0))+2(0)
form.in
1315
Stardard Output
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)