runtah

UVa 11000 Bee

UVa 11000 Bee

This is all about careful reading and a very bit of analysis.
First analyze what happens with a Male bee. Youll see every year the number of bees in that tree is a Fibonacci number, since all the past bees are dead by then.
Then for a Female be, its actually the same, because it gives birth to a Male bee the next year. And since the special bee produces one Male bee each year, so the result is actually the sum of Fibonacci numbers till n.

#include <iostream>
#include <cmath>
using namespace std;
long long sum[100], fibs[100];
int fib( ) {
 int i;
 long long lim = (long long)pow(2.00,32);

 fibs[0]=0LL; sum[0]=0LL;
 fibs[1]=1LL; sum[1]=1LL;
 fibs[2]=1LL; sum[2]=2LL;
 for (i=3 ; sum[i-1]<lim ; i++) {
 fibs[i]=fibs[i-1]+fibs[i-2];
 sum[i]=sum[i-1]+fibs[i];
 }

 return i;
}

int main( ) {
 fib();
 int n;
 while (cin >> n && n>=0)
 {
 cout << sum[n] << " " << sum[n+1] << endl;
 }
 return 0;
}

Go to link download