TheAnimalProgrammingCompetitions
TCO12 Semifinal 2 · 2012-03-27 · by Vasyl[alphacom]
TCO12 Semifinal 2 · 2012-03-27 · by Vasyl[alphacom] · Dynamic Programming
Problem Statement
Problem Statement
Cat Taro and rabbit Hanako are running the animal programming competitions in a forest.
John and Brus are invited as judges.
Each team that takes part in the competitions consists of exactly four members.
Each team member is either a cat or a rabbit.
You are given a int[] rabbits.
The number of teams that take part in the competitions is equal to the number of elements in rabbits.
For each i, team number i (0-based index) consists of rabbits[i] rabbits and 4-rabbits[i] cats.
According to the best traditions of the animal programming competitions, each rabbit brings one carrot at the opening ceremony and presents it to some participant (either a cat or a rabbit) from a different team. The rabbits always coordinate their choices in order to make sure that no participant receives more than one carrot as a present. It seems this task is not that easy for the rabbits, so they asked the judges (John and Brus) to help them. Now John and Brus are thinking of a carrot distribution plan. All the carrots are considered pairwise distinct. Hence, two distribution plans are considered distinct if and only if there is at least one participant that receives a different present (i.e., either a different carrot in each plan, or a carrot in one plan and no carrot in the other). Return the number of different distribution plans, modulo 1,234,567,891.
According to the best traditions of the animal programming competitions, each rabbit brings one carrot at the opening ceremony and presents it to some participant (either a cat or a rabbit) from a different team. The rabbits always coordinate their choices in order to make sure that no participant receives more than one carrot as a present. It seems this task is not that easy for the rabbits, so they asked the judges (John and Brus) to help them. Now John and Brus are thinking of a carrot distribution plan. All the carrots are considered pairwise distinct. Hence, two distribution plans are considered distinct if and only if there is at least one participant that receives a different present (i.e., either a different carrot in each plan, or a carrot in one plan and no carrot in the other). Return the number of different distribution plans, modulo 1,234,567,891.
Constraints
- rabbits will contain between 1 and 47 elements, inclusive.
- Each element of rabbits will be between 0 and 4, inclusive.
Examples
0)
{0, 1, 0}
Returns: 8
There are eight options for the only rabbit in the competitions.
1)
{4}
Returns: 0
Rabbits can't present carrots to their teammates.
2)
{1, 1, 0}
Returns: 60
If the first rabbit presents their carrot to somebody from the second rabbit's team then there are eight options for the second rabbit, if not - only seven. Thus the total number of different plans is 4*8 + 4*7 = 60.
3)
{0, 1, 2, 3, 4}
Returns: 644027397
4)
{4, 0, 1, 4}
Returns: 289859328
Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheAnimalProgrammingCompetitions with a public method int find(vector<int> rabbits) · 47 test cases · 2 s / 256 MB per case