TopCoder problem "BottlesOnShelf" used in Member SRM 491 (Division II Level Three)



Problem Statement

    

There are N bottles on a shelf (numbered from 1 to N). Some little kids are playing football near the shelf. Sometimes it happens that their ball hits the shelf and every bottle with an index between left[i] and right[i], inclusive, that is also divisible by damage[i] falls on the ground and breaks.



Given N and the arrays left, right and damage. The ball has hit the shelf exactly M times, where M is the size of each of the three arrays. Count and return the number of bottles broken by the kids.

 

Definition

    
Class:BottlesOnShelf
Method:getNumBroken
Parameters:int, int[], int[], int[]
Returns:int
Method signature:int getNumBroken(int N, int[] left, int[] right, int[] damage)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 1,000,000,000, inclusive.
-left, right and damage will each contain between 1 and 18 elements, inclusive.
-left, right and damage will contain the same number of elements.
-Each element of left and right will be between 1 and N, inclusive.
-For each i, left[i] will be less than or equal to right[i].
-Each element of damage will be between 1 and 42, inclusive.
 

Examples

0)
    
7
{1}
{7}
{2}
Returns: 3
Every second bottle has been broken by the kids. The shelf looks like this (.-unbroken, X-broken): 
    .X.X.X.
1)
    
7
{1,1}
{7,7}
{2,3}
Returns: 4
Every bottle dividible by 2 or 3 has been broken. 
    .XXX.X.
2)
    
7
{1,1,1}
{7,7,7}
{2,3,6}
Returns: 4
Now every bottle divisible by 6 has been broken also, but the result is the same as in last example. 
    .XXX.X.
3)
    
10
{1,6}
{5,10}
{1,7}
Returns: 6
From the first half of the shelf, every bottle has been broken. From the second half only the bottle with number 7 has been broken. 
    XXXXX.X...
4)
    
5
{4}
{4}
{7}
Returns: 0
None bottle has been broken.
5)
    
1000000000
{1}
{1000000000}
{1}
Returns: 1000000000
Every bottle has been broken.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11008

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14244&pm=11008

Writer:

Mimino

Testers:

Rustyoldman , ivan_metelsky , rng_58 , wrong

Problem categories:

Math, Simple Search, Iteration