// One-star problem // Problem UVA103 Stacking Boxes /* This program is written by Prof. Chua-Huang Huang Department of Information Engineering and Computer Science Feng Chia University Taichung, Taiwan Disclaimer: The programming problem is downloaded from UVa Online Judge (https://uva.onlinejudge.org/). The program solution is provided for helping students to prepare Collegiate Programming Examination (CPE). The author does not guarantee the program is completely correct to pass UVa Online Judge platform or CPE examination platform. This program is not intended for a student to copy only. He/She should practice the programming problem himself/herself. Only use the program solution as a reference. The author is not responsible if the program causes any damage of your computer or personal properties. No commercial use of this program is allowed without the author's written permission. */ #include #include // Alphabetical order less than comparison operator. // Return 1 if box1 is less than box2; otherwise, return 0. int seq_lessp(int box1[10], int box2[10], int dim) { int i; // Loop variable. for (i=0; ibox2[i]) return 0; // box1 is greater than box2 in dimension i. return 0; // box1 and box2 have the same size, i.e., box1==box2. } // Test whether box1 can be nested in box2. // Return 1, if box1 can be nested in box2; return 0, otherwise. int nested(int box1[10], int box2[10], int dim) { int i; for (i=0; i=box2[i]) return 0; // box1 cannot be nested in box2 on dimension i. return 1; // box1 is nested in box2. } int main(void) { // The maximum dimensionality is 10 and the minimum dimensionality is 1. // The maximum number of boxes in a sequence is 30. int boxes[30][10]; int num_of_boxes; // Number of boxes. int dimension; // Dimension of boxes. int ordered[30]; // Boxes in alphabetical order. int nest[30][30]; // The nested relation between boxes. int non_nested[30]; // Count the number of non-nested boxes. int removed[30]; // Box removed from nested sequence. int removed_next; // Search the next box to be removed. int max_non_nested; // The largest count of the non-nested boxes. int nested_chain_found; // 1: a chain of nested boxes is found; 0:, otherwise. int temp; // Temporary variable. int i, j, k; // Loop variables. int cases=0; while (scanf("%d %d", &num_of_boxes, &dimension)==2) { // Input the box dimensions. for (k=0; k0; i--) // Using selection sort algorithm. for (j=1; j<=i; j++) { if (boxes[k][j-1]>boxes[k][j]) { // Compare and swap operation. temp = boxes[k][j-1]; boxes[k][j-1] = boxes[k][j]; boxes[k][j] = temp; } } for (k=0; k0; i--) for (j=1; j<=i; j++) // If boxes[ordered[j-1]] and boxes[ordered[j]] are out of order, // swap their position. if (seq_lessp(boxes[ordered[j]], boxes[ordered[j-1]], dimension)) { temp = ordered[j-1]; ordered[j-1] = ordered[j]; ordered[j] = temp; } // Calculate nested relation for all boxes. // Assume a box can be nested in itself. // If (box[ordered[i]], box[ordered[j]]) are nested, also mark (box[ordered[j]], // box[ordered[i]]) as nested. Hence, the square matrix forms a symmetric matrix. for (i=0; i=0; i--) if (non_nested[i]>max_non_nested && removed[i]==0) { removed_next = i; max_non_nested = non_nested[i]; } // The removed_next is the box to be removed. if (removed_next>=0 && max_non_nested>0) removed[removed_next] = 1; // If all unremoved boxes are nested, these boxes form the longest nested chain. // That is, all unremoved box i and box j, they are nested. // The submatrix of unremoved boxes have nested[i][j]==1. // If one pair of boxes i and j are not nested, i.e., nest[i][j]==0, // set nested_chain_found to false and continue to remove anohter box. for (i=0; i