RabbitIncreasing
SRM 475 · 2009-11-12 · by lyrically
SRM 475 · 2009-11-12 · by lyrically · Math
Problem Statement
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 aint[] 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.
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
How many couples are in this country in December (the 12th month) of year k? Return the answer modulo 1,000,000,009.
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.
Submissions are judged against all 117 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RabbitIncreasing with a public method int getNumber(vector<int> leaving, int k) · 117 test cases · 2 s / 256 MB per case