11000 - Bee
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.
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:
Also note that is needed for , and for . Take care not to compute this value twice.
The problem asks you to output two numbers: the number of male bees and the total number of bees.
0 1 2 3 4 5 6 7 8 -1
0 1 1 2 2 4 4 7 7 12 12 20 20 33 33 54 54 88