2010年7月14日 星期三

[Timus Online Judge] 1079. Maximum

Finally I got the AC.
I am so happy about this.
Step by Step to success.

According to this program.
It must consider about the time complex.








Time Limit: 2.0 second
Memory Limit: 16 MB
Consider the sequence of numbers ai, i = 0, 1, 2, …, which satisfies the following requirements:

* a0 = 0
* a1 = 1
* a2i = ai
* a2i+1 = ai + ai+1

for every i = 1, 2, 3, … .
Write a program which for a given value of N (0 < N < 100000) finds the largest number among the numbers a0, a1, …, aN.
Input
Input contains not more than 10 lines containing one number N. The last line contains 0.
Output
For every N in the input write the corresponding maximum value found.



#include

int Maximum(int N){

if (N == 0)
return 0;
else if (N == 1)
return 1;
else if( (N % 2) == 0 )
return Maximum(N/2) ;
else
return ( Maximum(N/2) + Maximum(N/2 + 1) );

}


int main(void){

long i,num,max;
long number[100001];

for(i = 0 ; i <= 100000 ; i++){
number[i]=Maximum(i);
}

while(scanf("%ld",&num)!=EOF){
if (num==0) break;
for(i=0,max=0;i<=num;i++)
if(number[i]>max) max=number[i];
printf("%ld\n",max);
}


return 0;
}

Related Posts:

0 意見:

張貼留言