TopCoder problem "RabbitIncreasing" used in SRM 475 (Division I Level Two)



Problem Statement

    Rabbits often feel lonely, even though they breed a lot.



A male rabbit and a female rabbit were born in July (the 7th month) of year 1, in a certain country. They were the only rabbits in the entire country, so they became a couple.



In March (the 3rd month) of every year, each couple who is strictly more than 1 year old will breed one male and one female rabbit. That is, couples born in year y will start breeding in the year y + 2.



Then, in April (the 4th month) of every year, all newly born rabbits will form couples among themselves. Each rabbit will be a member of exactly one couple, and each couple will contain one male and one female rabbit.



You are given a int[] leaving. Each element of leaving is a year in which half of all couples will leave the country in November (the 11th month). If there are an odd number of couples, n, then (n + 1) / 2 couples will leave. Older couples always have priority when leaving. This means that every couple who leaves will have an age greater than or equal to every couple who stays.



How many couples are in this country in December (the 12th month) of year k? Return the answer modulo 1,000,000,009.
 

Definition

    
Class:RabbitIncreasing
Method:getNumber
Parameters:int[], int
Returns:int
Method signature:int getNumber(int[] leaving, int k)
(be sure your method is public)
    
 

Constraints

-leaving will contain between 1 and 50 elements, inclusive.
-k will be between 1 and 10,000,000, inclusive.
-Each element of leaving will be between 1 and k, inclusive.
-Elements of leaving will be sorted in strictly increasing order.
 

Examples

0)
    
{ 3 }
3
Returns: 1
The first couple will breed a pair of rabbits in March of year 3. Since there are 2 couples in November, 1 old pair will leave.
1)
    
{ 5, 9 }
10
Returns: 6
In November of year 5, 3 out of 5 couples will leave.

In November of year 9, 5 out of 10 couples will leave.
2)
    
{ 5, 10, 15 }
19
Returns: 212
3)
    
{ 2 }
10000000
Returns: 0
4)
    
{ 195, 211, 227, 230, 260, 
  297, 346, 350, 403, 411, 
  428, 485, 594, 606, 876 }

1000
Returns: 975206486
There are a lot of rabbits. Be sure to return the answer modulo 1,000,000,009.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10879

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14156&pm=10879

Writer:

lyrically

Testers:

PabloGilberto , ivan_metelsky , keshav_57

Problem categories:

Math