| We make cardboard boxes. We manufacture a variety of sizes and are concerned
that storing them and transporting them will be a problem unless we can nest
them into a reasonable number of nested stacks. Each box is a rectangular
solid and thus has three side lengths. We say that
Box A can be nested in Box B
if its smallest length is strictly less than B's smallest length, its
2nd smallest length is strictly less than B's 2nd smallest length, and its
largest length is strictly less than B's largest length.
No diagonal nesting is allowed.
We have automated the manufacturing process so that random sized boxes are
produced. We specify values a, p, and n and the machine produces n boxes with
dimensions: -
(a,a^2,a^3) (a^4,a^5,a^6) (a^7,a^8,a^9) ... (a^(3n-2),a^(3n-1),a^(3n))
where a^j denotes (a to the jth power) mod p.
Create a class Nestable that contains a method maxCount that is given the
positive integer values a, p, and n and that returns the size of the
largest nestable collection of boxes,
where a collection is nestable if every pair of boxes from
the collection can be nested.
The sequence of boxes can be generated by
int length=1;
for(int i=0; i<n; i++){
length = (length*a)%p; int x=length;
length = (length*a)%p; int y=length;
length = (length*a)%p; int z=length;
//process this box, which has dimensions x,y,z
}
|