BottlesOnShelf
Member SRM 491 · 2010-03-12 · by Mimino
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.
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.
6
{1,4}
{4,5}
{4,2}
Returns: 1
20
{9,12}
{12,17}
{4,6}
Returns: 1
20
{9,12}
{12,17}
{2,3}
Returns: 3
20
{1,6,9,12,12}
{6,9,12,18,15}
{6,3,6,9,3}
Returns: 5
100
{1,1,1,1,1,1,1}
{100,100,100,100,100,100,100}
{2,3,5,6,10,15,30}
Returns: 74
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.
7
{1,1}
{7,7}
{2,3}
Returns: 4
Every bottle dividible by 2 or 3 has been broken. .XXX.X.
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.
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...
5
{4}
{4}
{7}
Returns: 0
None bottle has been broken.
1000000000
{1}
{1000000000}
{1}
Returns: 1000000000
Every bottle has been broken.
Submissions are judged against all 118 archived test cases, of which 11 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BottlesOnShelf with a public method int getNumBroken(int N, vector<int> left, vector<int> right, vector<int> damage) · 118 test cases · 2 s / 256 MB per case