UVA 11000 - Bee

http://uva.onlinejudge.org/external/110/11000.html

You are given one a very special African female bee. This bees has really interesting reproduction system. The female bees can give birth to a male bee. The male bees can give birth to one male bee and one female bee. Assuming that the bees are immortal, return the number of male bees and the overall total of bees after \(N\) years.

Is hard to think in something different from Fibonacci numbers when you heard something related with populations and growth. Let's get our hand dirty and make a diagram of what is happening:

Looking at this graph is easy to conjecture a recursion for both the males bees and the females bees. Where \(f(n)\) represent the numbers of females bees in the \(n\)-th year and \(m(n)\) represent the number of male bees in the \(n\)-th year:

$$\\ f(n) = f(n-1) + f(n-2) \\ m(n) = m(n-1) + m(n-2) + 1$$

In order to be able to answer the query's in \(O(1)\) time, we first pre-calculate all the values of both functions in two arrays.