UTS Programming Competition 2013 Problem 5

From ProgSoc Wiki

Jump to: navigation, search

Problem 5: Bob's Box Boutique

NB: This question first appeared in the 2012 ACM-ICPC East Central North America Regional Programming Contest (freely available online -- Problem A as "Babs' Box Boutique")

Problem Description

Bob sells boxes and lots of them. All his boxes are rectangular but come in many different sizes. Bob wants to create a really eye-catching display by stacking, one on top of another, as many boxes as he can outside his store. To maintain neatness and stability, he will always have the sides of the boxes parallel but will never put a box on top of another if the top box sticks out over the bottom one. For example, a box with base 5-by-10 can not be placed on a box with base 12-by-4.

Of course the boxes have three dimensions and Bob can orient the boxes anyway he wishes. Thus a 5-by-10-by-12 box may be stacked so the base is 5-by-10, 5-by-12, or 10-by-12.

For example, if Bob currently has 4 boxes of dimensions 2-2-9, 6-5-5, 1-4-9, and 3-1-1, he could stack up to 3 boxes but not all four. (For example, the third box, the first box, then the last box, appropriately oriented. Alternatively, the second box could replace the third (bottom) box.)

Bob's stock rotates, so the boxes he stacks outside change frequently. It's just too much for Bob to figure out and so he has come to you for help. Your job is to find the most boxes Bob can stack up given his current inventory. Bob will have no more than 10 different sized boxes and will use at most one box of any size in his display.

Problem Task

Input: Input: A positive integer n (n <= 10) will be on the first input line for each test case. Each of the next n lines will contain three positive integers giving the dimensions of a box. No two boxes will have identical dimensions. None of the dimensions will exceed 20. A line with 0 will follow the last test case...

Output: For each test case, output the maximum number of boxes Bob can stack using the format given below.

Sample Input

4
2 2 9
6 5 5
1 4 9
3 1 1
3
2 4 2
1 5 2
3 4 1
0

Sample Output

Case 1: 3 
Case 2: 3 

Solutions

Put your solutions here!

Personal tools