Q1. String to Integer

implement a similar atoi function to convert a string to integer(int type)

hint:
the string may start with continuous whitespaces, you should ignore them.

the string may end with continuous invalid characters, you should ignore them, too.

find the first valid integer you can find in this string as the result.

there may be some strings which can not be convertd to an intrger. in this case, return -1.

there may be some strings  which are out of the range of int.type, return -1.

Input
A single line of string.

output
A single integer

************************************************************************************************************

Q2.ZigZag

A sequence of number is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. the first difference(if one exists)may be either positive or negative. A sequence with fewer than elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences(6,-3,5,-7,3)are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequense. A subsequence is obtained by deleting some number of elements(possibly zero) from the original sequence, leaving the remaining elements in their original order.
************
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Input
First line is the number of elements in the sequence.
second line contains the sequence of numbers split by whitespaces.
Each sequence contains between 1 and 50 elements.
Each element of sequence is between 1 and 1000.

Output
The length of the longest sequence.

Sample input 1:
6
1 7 4 9 2 5
Sample output 1:
6

Sample input 2:
1
44
Sample output 2:
1

************************************************************************************************************

Q3.Fibonacci Representation

We define Fibonacci number as follow:
F(1)=1
F(2)=2
F(i)=F(i-1)+F(i-2),(i>=3)
Given any onee number M, we can represent it by using the sum of some different
Fibonacci numbers.

For example:
Given "13",you can represent it as 3 ways:
they are
13 = 13
13 = 5 + 8
13 = 2 + 3 + 8
You cannot represent like this:
13 = 2 + 3 + 5 +3
Because there are two same "3".
It is easy for case of 13. Bur how many ways we can represent M by using the sum of different Fibonacci numbers when M is so large(for example 10^8)that we cannot enumerate?

Input
There is only line which containsone number that is smaller than 2^31.You should
give that how many ways we can represent this number by using the sum of different Fibonacci numbers.

Output
One line only with a number indicating the number of ways that the input number can be represented by the sum of different Fibonacci numbers.

Sample Input 1:
6
Sample Output 1:
2

Sample Input 2:
13
Samplr Output 2:
3

三道题目