WinterAndShopping
SRM 601 · 2013-06-25 · by Witaliy
Problem Statement
It's winter time! Time to do some shopping.
You want to buy some colored balls.
The only balls that are on the market nowadays are red, green and blue balls.
There are several shops in your city.
You are given four
You also know that the opening days and numbers of balls are such that on any given day at most two shops will be open. Additionally, if there are two shops open on the same day, they are required to sell balls of the same color. You want to know the number X of different orders in which the shops can sell the balls. (Two selling orders are considered different if there is a day and a shop such that in one order the shop sold a ball of a different color than in the other.) Return the value (X modulo 1,000,000,007).
Constraints
- first, red, green and blue will contain between 1 and 50 elements, inclusive.
- first, red, green and blue will contain the same number of elements.
- Each element of first will be between 1 and 500, inclusive.
- Each element of red, green and blue will be between 0 and 100, inclusive.
- For each valid i, the value red[i]+green[i]+blue[i] will be strictly greater than 0.
- For each valid i, the value first[i]+red[i]+green[i]+blue[i]-1 will be less than or equal to 500.
- For each day, at most two shops will be opened.
{1}
{1}
{1}
{1}
Returns: 6
There is one shop in this case, selling three different balls in three days. All permutations are possible, thus the answer is 6.
{1}
{3}
{0}
{0}
Returns: 1
In this case, the shop is selling only balls of red color. Thus, there is only one possibility.
{1, 2}
{1, 1}
{1, 1}
{1, 1}
Returns: 6
One of the six valid orders in which all balls can be sold: The first shop sells a red ball, then a blue one, and finally a green one. The second shop (which opens a day later) first sells a blue ball, then a green one, and finally the remaining red one.
{47, 47}
{1, 0}
{0, 1}
{0, 0}
Returns: 0
Both stores are open on the same day. However, one store only has a red ball and the other store only has a green ball. The balls don't have the same color, thus the stores cannot sell them on the same day. Hence there is no valid way to sell the balls. In such a case the correct return value is obviously 0.
{1, 100, 200}
{100, 1, 0}
{100, 3, 7}
{100, 2, 4}
Returns: 79290907
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WinterAndShopping with a public method int getNumber(vector<int> first, vector<int> red, vector<int> green, vector<int> blue) · 84 test cases · 2 s / 256 MB per case