UVa 11000

From Algorithmist
Jump to: navigation, search

11000 - Bee[edit]

Summary[edit]

There is a rather strange species of bee that reproduce in the following manner: the female bees each give birth to one male bee and then die. The male bees each give birth to a male bee and a female bee and then die. However, there is one immortal female bee that doesn't die after it gives birth.

Starting with only the immortal female bee, find the number of male bees and the total number of bees after n generations.

Explanation[edit]

Using the notation M(n)= Number of males after n generations, and F(n)= Number of females after n generations, we can deduce the following relations by definition:

M(n)={\begin{cases}0&n=0\\1&n=1\\M(n-1)+F(n-1)&n\geq 2{\mbox{ (1)}}\end{cases}}
F(n)={\begin{cases}1&n=0\\M(n-1)+1&n\geq 1{\mbox{ (2)}}\end{cases}}

From {\mbox{(2)}} in {\mbox{(1)}}, we can deduce that:

M(n)={\begin{cases}0&n=0\\1&n=1\\M(n-1)+M(n-2)+1&n\geq 2\end{cases}}

which is very close in principle to the fibonacci series. As in fibonacci, you can calculate the above recurrence in O(n) using bottom-up dynamic programming.

Also note that M(n-1) is needed for M(n), and for F(n). Take care not to compute this value twice.

Gotchas[edit]

The problem asks you to output two numbers: the number of male bees and the total number of bees.

Input[edit]

0
1
2
3
4
5
6
7
8
-1

Output[edit]

0 1
1 2
2 4
4 7
7 12
12 20
20 33
33 54
54 88