#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/*Struct defining cube*/

typedef struct

{

int l;

int b;

int h;

}Cube;

/*Cube compare function */

int cube_compare(const void *x, const void *y)

{

const Cube *a = x;

const Cube *b = y;

if(a->l == b->l)

{

if(a->b == b->b)

return a->h - b->h;

return a->b - b->b;

}

return a->l - b->l;

}

/*Struct to hold successor info*/

typedef struct

{

int next;

int chainLength;

}Successor;

/*Checks whether cube 'a' fits into cube 'b' */

inline int cube_fits(Cube *a , Cube *b)

{

return (a->l < b-> l) && (a->b < b->b) && (a->h < b->h);

}

/*Prints all the cubes which fits into one another */

void max_fit_cubes(Cube cubes[], int n)

{

//Fill the chain

Successor nextCube[n];

memset(nextCube, 0, sizeof(nextCube));

int i = n - 1, j;

while(i--)

{

for(j = i + 1; j < n; j++)

{

if(cube_fits(cubes + i, cubes + j))

{

if((nextCube[j].chainLength + 1) > nextCube[i].chainLength)

{

nextCube[i].chainLength = nextCube[j].chainLength + 1;

nextCube[i].next = j;

}

}

}

}

//find the max chain

int m = i = n - 1;

while(i--)

{

if(nextCube[i].chainLength > nextCube[m].chainLength)

m = i;

}

//Now print the max chain

printf("Max Chain Length: %d, m: %d\n", nextCube[m].chainLength, m);

do

{

printf("(%d,%d,%d) =>", cubes[m].l, cubes[m].b, cubes[m].h);

m = nextCube[m].next;

}while(m);

printf("\n");

}

int main()

{

int n;

scanf("%d", &n);

Cube cubes[n];

int i;

for(i = 0; i < n; ++i)

{

scanf("%d%d%d", &(cubes[i].l), &(cubes[i].b), &(cubes[i].h));

}

qsort(cubes, n, sizeof(Cube), cube_compare);

max_fit_cubes(cubes, n);

return 0;

}

Advertisements