|Felix Halim .NET|
University Experience IOI 2002 Yong In, Korea ACM ICPC Regional Manila 2003 ACM ICPC Regional Manila 2004 ACM ICPC Regional Manila 2005 ACM ICPC Regional Kaohsiung 2006 ACM ICPC Regional Singapore 2007 ACM ICPC Regional Jakarta 2008 (ext) ACM ICPC Regional Jakarta 2009 (ext) ACM ICPC Regional Jakarta 2010 ACM ICPC Regional Jakarta 2012 - Problem H ACM ICPC Regional Jakarta 2013 - Problem J (new!) ACM ICPC World Final Tokyo 2007 Google India Code Jam 2005 Google India Code Jam 2006 Indonesia National Contest 2007 Indonesia National Contest 2008 Indonesia National Contest 2010 Facebook Hacker Cup 2011
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. The boxes are rectangular, but they are open at the top so their heights don't matter. If we call the smaller horizontal dimension of a box its width and the other dimension its length, a box can be nested in another box if its width is less than the other's width, and its length is less than the other's 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^(2n-1),a^(2n)) where a^j denotes (a to the j power) mod p.
Create a class UnNestable that contains a method maxCount that is given the positive integral values a, p, and n and that returns the size of the largest unnestable collection of boxes, where a collection is unnestable if no two boxes from the collection can be nested.
The sequence of boxes can be generated by
int rv=1; for(int i=0; i