Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Bandwidth

140.c

/* 140 - Bandwidth */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int fact[13]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600};

void
num2perm(int num, int *p, int n) {
	int set[12];
	int i,k;

	for (i=0; i<n; i++) {
		set[i]=i;
	}
	for (i=n-1; i>0; i--) {
		k=0;
		while (num>=fact[i]) {
			num-=fact[i];
			k++;
		}
		p[n-1-i]=set[k];
		memmove(&set[k], &set[k+1], (i-k)*sizeof(int));
	}
	p[n-1]=set[0];
}

int n;
char nam[10];
char arr[10][10];

int
compar(const void *a, const void *b) {
	return *(char *)a - *(char *)b;
}

void
input_edge(char a, char b) {
	int i,j;
	for (i=0; i<n; i++) {
		if (a==nam[i]) {
			break;
		}
	}
	for (j=0; j<n; j++) {
		if (b==nam[j]) {
			break;
		}
	}
	arr[i][j] = arr[j][i] = 1;
}

void
input(char * buf) {
	int i,j;
	int orig=-1;

	memset(nam, 0, sizeof(nam));
	memset(arr, 0, sizeof(arr));
	n = 0;
	for (i=0; i<strlen(buf); i++) {
		if (buf[i] >= 'A' && buf[i] <= 'Z') {
			for (j=0; j<n; j++) {
				if (nam[j]==buf[i]) {
					goto next;
				}
			}
			nam[n++]=buf[i];
		}
next:
		;
	}
	qsort(nam, n, sizeof(char), compar);
	for (i=0; i<strlen(buf); i++) {
		if (buf[i] >= 'A' && buf[i] <= 'Z') {
			if (orig<0) {
				orig=buf[i];
			} else {
				input_edge(orig, buf[i]);
			}
		} else if (buf[i]==';') {
			orig=-1;
		}
	}
}

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

int
band(char *p) {
	int i,j;
	int max=0;
	for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			if (arr[(int)p[i]][(int)p[j]]) {
				max = MAX(max,abs(i-j));
			}
		}
	}
	return max;
}

void
permuta(char *p, int np) {
	int i,j;
	int min;
	char c;

	for (i=np-2; i>=0; i--) {
		if (p[i] < p[i+1]) {
			break;
		}
	}
	min=i+1;
	for (j=i+2; j<np; j++) {
		if (p[j]>p[i] && p[j]<p[min]) {
			min=j;
		}
	}
	c = p[min];
	p[min] = p[i];
	p[i] = c;
	qsort(&p[i+1], np-i-1, sizeof(char), compar);
}

void
calc(void) {
	int i;
	char perm[10];
	int minban=100;
	char minperm[10];

	for (i=0; i<n; i++) {
		perm[i] = i;
	}
	for (i=0; i<fact[n]; i++) {
		int a;
		if (i) permuta(perm, n);
		a = band(perm);
		if (a < minban) {
			minban = a;
			memcpy(minperm, perm, sizeof(perm));
		}
	}
	for (i=0; i<n; i++) {
		printf("%c ", nam[(int)minperm[i]]);
	}
	printf("-> %d\n", minban);
}

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

	while (1) {
		if (scanf(" %s", buf)!=1) {
			break;
		}
		if (buf[0]=='#') {
			break;
		}
		input(buf);
		calc();
	}
	return 0;
}