Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Meta-Loopless Sorts

110.c

/* Meta-Loopless Sorts */
#include <stdio.h>
#include <string.h>

char * sangra(int ini)
{
	static char buf[1024];
	sprintf(buf, "  %*s", 2*ini, "");
	return buf;
}

void adj(int n, int copy[8][8])
{
	int i,j,k;

	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			for(k=0; k<n; k++) {
				if (copy[i][j] && copy[j][k]) {
					copy[i][k]=1;
				}
			}
		}
	}
}

void sort(int n, int vars[8][8], int ini)
{
	int i,j;
	int copy[8][8];
	int done;
	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			if (i==j) {
				continue;
			}
			if (!vars[i][j] && !vars[j][i]) {
				printf("%sif %c < %c then\n", sangra(ini), 'a'+i, 'a'+j);
				memcpy(copy, vars, sizeof(copy));
				copy[i][j]=1;
				adj(n,copy);
				sort(n, copy, ini+1);
				printf("%selse\n", sangra(ini));
				memcpy(copy, vars, sizeof(copy));
				copy[j][i]=1;
				adj(n,copy);
				sort(n, copy, ini+1);
				return;
			}
		}
	}
	printf("%swriteln(", sangra(ini));
	for(i=0; i<n; i++) {
		done=1;
		for(j=0; j<n; j++) {
			if (i==j) {
				continue;
			}
			if (!vars[i][j]) {
				done=0;
				break;
			}
		}
		if (done) {
			printf("%c", 'a'+i);
			vars[i][i]=1;
			break;
		}
	}
	while(1) {
		int all_done=1;
		for(i=0; i<n; i++) {
			if (vars[i][i]) {
				continue;
			}
			done=1;
			for(j=0; j<n; j++) {
				if (i==j || vars[j][j]) {
					continue;
				}
				if (!vars[i][j]) {
					done = 0;
					break;
				}
			}
			if (done) {
				all_done=0;
				printf(",%c", 'a'+i);
				vars[i][i]=1;
				break;
			}
		}
		if (all_done) {
			break;
		}
	}
	printf(")\n");
}

#if 0
void print_sort(int n, int ini)
{
	printf("%sif %c < %c then\n",sangra(ini),'a'+ini, 'a'+ini+1);
	if (n==2) {
		printf("%s  writeln();\n");
	}
}
#endif

void
doit(int n) {
	int i,j;
	int vars[8][8];

	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			vars[i][j] = 0;
		}
	}
	printf("program sort(input,output);\n");
	printf("var\n");
	printf("a");
	for(i=1; i<n; i++) printf(",%c", 'a'+i);
	printf(" : integer;\n");
	printf("begin\n");
	printf("  readln(a");
	for(i=1; i<n; i++) printf(",%c", 'a'+i);
	printf(");\n");
	sort(n,vars,0);
	printf("end.\n");
}

int
main(void) {
	int M, n;
	int i;

	scanf("%d", &M);
	for (i=0; i<M; i++) {
		if (i) {
			printf("\n");
		}
		scanf("%d", &n);
		doit(n);
	}
	return 0;
}