Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Stacking Boxes

103.c

#include <stdio.h>
#include <stdlib.h>

int num, dim;

int box[30][10];

int fits[30][30];		/* fits[a,b]=1 if box "a" fits in box "b" */

int max_length;
int ordered[35];

static int compare(const void * a, const void * b)
{
	return *(int*)a - *(int*)b;
}

int fitsp(int * box1, int * box2)
{
	int i;
	int cop1[10];
	int cop2[10];

	for(i=0; i<dim;i++) {
		cop1[i]=box1[i];
	}
	for(i=0; i<dim;i++) {
		cop2[i]=box2[i];
	}

	qsort(cop1, dim, sizeof(int), compare);
	qsort(cop2, dim, sizeof(int), compare);

	for(i=0; i<dim; i++) {
		if (cop1[i] >= cop2[i]) {
			return 0;
		}
	}

	return 1;
}

#define MAX(a,b) ((a) > (b) ? (a) : (b))

#if 1
int
calc_length(int len, int ori)
{
	int i;
	int cur_length;
	static int semi_ordered[35];

	semi_ordered[len]=ori;
	if (len>max_length) {
		memcpy(ordered, semi_ordered, sizeof(ordered));
		max_length = len;
	}
	if (len==num) {
		return len;
	}
	cur_length=len;
	for(i=0; i<num; i++) {
		if (fits[ori][i]) {
			int a=calc_length(len+1,i);
			cur_length = MAX(cur_length,a);
		}
	}
	return cur_length;
}
#else
int
calc_length(int len, int ori)
{
	static int cur_boxes[30];
	int i;

	if (len==1) {
		for(i=0; i<num; i++) {
			cur_boxes[i]=0;
		}
	}
	for(i=0; i<num; i++) {
		if (!cur_boxes[i] && fits[ori][i]) {
		}
	}
}
#endif

void doit(void)
{
	int i,j,k;

	for(i=0; i<num; i++) {
		for(j=0; j<num; j++) {
			fits[i][j] = fitsp(box[i],box[j]);
		}
	}

	for(i=0; i<num; i++) {
		for(j=0; j<num; j++) {
			if (i==j) {
				continue;
			}
			for(k=0; k<num; k++) {
				if (i==k || j==k) {
					continue;
				}
				if (fits[i][j] && fits[j][k]) {
					fits[i][k]=0;
				}
			}
		}
	}
	for(i=0; i<num; i++) {
		int todo=1;
		for(j=0; j<num; j++) {
			if (fits[j][i]) {
				todo=0;
				break;
			}
		}
		if (todo) {
			calc_length(1,i);
		}
	}
	printf("%d\n", max_length);
	for(i=0; i<max_length; i++) {
		printf("%s%d", (i==0 ? "" : " "), ordered[i+1]+1);
	}
	printf("\n");
}

int main(void)
{
	char buf[1024];
	int i,j;

	while(fgets(buf, 1024, stdin)) {
		max_length=0;
		i = sscanf(buf, "%d %d\n", &num, &dim);
		if (i!=2) {
			exit(1);
		}
		if ((num<1) || (num>30) || (dim<1) || (dim>10)) {
			exit(0);
		}
		for(i=0; i<num; i++) {
			if (fgets(buf, 1024, stdin)==NULL) {
				exit(3);
			}
			j = sscanf(buf, "%d %d %d %d %d %d %d %d %d %d\n",
				&box[i][0], &box[i][1], &box[i][2], &box[i][3],
				&box[i][4], &box[i][5], &box[i][6], &box[i][7],
				&box[i][8], &box[i][9]);
			if (j!=dim) {
				exit(4);
			}
		}
		doit();
	}
	exit(0);
}