# UVa 11000

## 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 generations.

## Explanation[edit]

Using the notation Number of males after generations, and Number of females after generations, we can deduce the following relations by definition:

From in , we can deduce that:

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

Also note that is needed for , *and* for . 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