Problem E
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 32768/16384K (Java/Other)
Total Submission(s) : 15 Accepted Submission(s) : 7
Problem Description
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 finds the largest number among the numbers a0, a1, …, an.
Input
You are given several test cases (not more than 10). Each test case is a line containing an integer n (1 ≤ n ≤ 99 999). The last line of input contains 0.
Output
For every n in the input write the corresponding maximum value found.
Sample Input
| input | output |
|---|---|
5 |
3 |
#include<stdio.h>
int main()
{
int i,j,n,max;
int a[200005];
while(~scanf("%d",&n)&&n!=0)
{
max=0;
a[0]=0;
a[1]=1;
for(i=1;i<=n;i++)
{
a[2*i]=a[i];
a[2*i+1]=a[i]+a[i+1];
}
for(i=0;i<=n;i++)
if(a[i]>=max)
max=a[i];
printf("%d\n",max);
}
return 0;
}