A case of Effective Packing!
“Boxes Unlimited” is a company founded by Mr. Dibba Hoshiyar that specializes in manufacturing cartons of all sizes that are used for packing purposes. All cartons are rectangular (cuboid) in shape but vary in the three dimensions namely, the length, breadth & height. Whenever Mr. Dibba deals with potentially large orders, he sends samples of these cartons to the prospective company to help secure his order. Mr. Dibba makes sure that he sends as many cartons of various sizes as requested by the prospective company but at the same time, wants to keep the shipping cost to a minimum. To do this, Mr. Dibba packs the cartons within one another: the smallest carton is put placed inside a slightly larger carton, which is in turn is placed in a slightly larger carton and so on. He also has the option of packing as many small cartons as possible into a single large carton without them being inside one another. Eventually, the outermost carton is closed, sealed and shipped, thus paying shipping cost for just one carton (the outermost one). It may be noted that while a smaller carton is packed inside a bigger carton, the smaller carton may not fit inside the bigger one in all orientations, but only in certain orientations. For example, a 3x4x5 carton would fit inside a 5x6x4 carton, but not in all orientations.
To make things simpler, let us ignore the thickness of the carton sides. This means that, a 3x4x5 carton would fit inside another 3x4x5 carton (although two cartons of the same dimension will not occur for us). If Mr. Dibba gets a request for sending five sample cartons of the following dimensions: 3x4x5, 5x6x3, 1x4x10, 4x4x4 and 6x6x5, he would have to send these samples in a minimum of 3 cartons. There are several ways to arrive at this solution.
1. Put the 3x4x5 carton into the 5x6x3 which then, is put into the 6x6x5 carton. So the 3 cartons shipped would be 6x6x5, 1x4x10 and 4x4x4.
2. Put the 3x4x5 carton into the 5x6x3 carton and put the 4x4x4 carton into the 6x6x5 carton. In this case, the three cartons shipped would be 5x6x3, 6x6x5 and the 1x4x10.
It should also be noted that more than one carton can be packed within a larger carton without them being inside one another. Take the case of five sample cartons of the following dimensions: 3x3x3, 2x2x2, 3x3x1, 2x3x1 and 2x2x1. In this example, the cartons 2x2x2, 3x3x1, 2x3x1 and 2x2x1 would fit into the 3x3x3 carton and hence, only one carton (which is 3x3x3) needs to be shipped.
Your aim is to help Mr. Dibba find out the minimum number of cartons that needs to be shipped with all the samples of cartons requested (remember, you are helping Mr. Dibba in cutting shipping costs).
Input
The input file may contain multiple test cases. Input to each test case starts with a single integer m (0 < m <= 50) that denotes the number of cartons in that test case. This is followed by m lines, each with three positive integers l b h (each not greater than 100) separated by a single white space between each of them, corresponding to the length, breadth and height of each sample carton. No two cartons would have the exact same dimensions. The end of all test cases (and hence, the input itself) is signified by m having a value of 0.
Output
For each test case, output the number of cartons that would have to be shipped separately.
An example of multiple test cases
Input Output
5
3 4 5
5 6 3
1 4 10
4 4 4
6 6 5
3
3 1 7
5 1 4
2 5 3
5
3 3 3
2 2 2
3 3 1
2 3 1
2 2 1
0 3
3
1
As an example, there are two attachments here (input.txt and output.txt) for you to visualize how the input file would look like and how your program should create the output file.
General Instructions
• Please adhere to the rules document on the Code Mania Portal so that the Automated Solution Validator (ASV) can validate your solution.
• The format of the input and the output files are strictly governed by the ASV. Therefore, you are requested to adhere to the exact formats mentioned above
• The solution submitted is liable to rejection if
o it is found to be copied from the internet or any other source
o the source code has compilation errors
• In case of any dispute, the decision of the judges would be final.