JOIN
Get Time

   Problem Statement  

 Problem Statement for Over9000Rocks

Problem Statement

    You used to have only 30 rocks, but now you have plenty of them. In fact, we will assume that you have a potentially infinite supply of rocks. You would like to show that you own over 9000 rocks. You have a set of boxes. You will choose a subset of those boxes and fill them with rocks so that the total number of rocks will be over 9000. Each box has a lower and an upper bound on the number of rocks it may contain.



You are given the int[]s lowerBound and upperBound. For each i, the values lowerBound[i] and upperBound[i] have the following meaning: If you decide to use box i, the number of rocks you may put inside the box must be between lowerBound[i] and upperBound[i], inclusive.



X is a positive integer that has two properties:
  • X is over 9000.
  • It is possible to select some of the boxes and fill them with appropriate numbers of rocks in such a way that the total number of rocks used is exactly X.
Compute and return the number of possible values of X.
 

Definition

    
Class:Over9000Rocks
Method:countPossibilities
Parameters:int[], int[]
Returns:int
Method signature:int countPossibilities(int[] lowerBound, int[] upperBound)
(be sure your method is public)
    
 

Constraints

-lowerBound will contain between 1 and 15, elements, inclusive.
-upperBound will contain the same number of elements as lowerBound.
-Each element of lowerBound will be between 1 and 1,000,000 (10^6), inclusive.
-Each element i of upperBound will be between lowerBound[i] and 1,000,000 (10^6), inclusive.
 

Examples

0)
    
{9000}
{9001}
Returns: 1
You can place 9000 or 9001 rocks in the single box. Of the allowed values, only 9001 is over 9000.
1)
    
{9000, 1, 10}
{9000, 2, 20}
Returns: 15
You have to choose box 0 and at least one other box, otherwise you have no chance of placing over 9000 rocks. If you only choose boxes 0 and 1, you can place 9001 or 9002 rocks. If you only choose boxes 0 and 2, you can place between 9010 and 9020 rocks, inclusive. If you choose all three boxes, you can place between 9011 and 9022 rocks, inclusive. Hence all possible values of X are 9001, 9002, and everything from 9010 to 9022, inclusive.
2)
    
{1001, 2001, 3001, 3001}
{1003, 2003, 3003, 3003}
Returns: 9
3)
    
{9000,90000,1,10}
{9000,90000,3,15}
Returns: 38
4)
    
{1,1,1,1,1,1}
{3,4,5,6,7,8}
Returns: 0

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 539 Round 1 - Division I, Level One
       Single Round Match 539 Round 1 - Division II, Level Two