JOIN
Get Time

   Problem Statement  

 Problem Statement for WinterAndShopping

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 int[]'s first, red, green and blue. For each i, the i-th shop starts working on first[i]-th day, works for red[i]+green[i]+blue[i] consecutive days and sells exactly red[i] red balls, green[i] green balls, blue[i] blue balls. Each shop sells exactly one ball on each day it is working.

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).

 

Definition

    
Class:WinterAndShopping
Method:getNumber
Parameters:int[], int[], int[], int[]
Returns:int
Method signature:int getNumber(int[] first, int[] red, int[] green, int[] blue)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{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)
    
{1}
{3}
{0}
{0}
Returns: 1
In this case, the shop is selling only balls of red color. Thus, there is only one possibility.
2)
    
{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.
3)
    
{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.
4)
    
{1, 100, 200}
{100, 1, 0}
{100, 3, 7}
{100, 2, 4}
Returns: 79290907
5)
    
{1, 3}
{3, 4}
{4, 4}
{2, 1}
Returns: 840
6)
    
{2, 1}
{100, 100}
{100, 100}
{99, 100}
Returns: 412784747
7)
    
{1, 220, 150}
{70, 70, 50}
{70, 70, 50}
{70, 70, 50}
Returns: 291495139
8)
    
{2, 2, 70, 159}
{100, 20, 21, 52}
{100, 20, 29, 45}
{100, 22, 39, 30}
Returns: 139586270

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 601 Round 1 - Division I, Level Three