Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Following Orders

124.c

/* 124 - Following Orders */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int num_vars=0;
char vars[25];

int num_cons=0;
struct cons {
	char a;
	char b;
} cons[55];

/* 1 if everything is ok
 * 0 if something is wrong
 */
int
test(int num, char *order) {
	int i;
	char *s, *t;

#if DEBUG
	printf("HCK: test('%*.*s')\n", num, num, order);
#endif
	for (i=0; i<num_cons; i++) {
		s = memchr(order, cons[i].a, num);
		t = memchr(order, cons[i].b, num);
		if (!t) continue;
		if (!s) return 0;
		if (s > t) return 0;
	}
	return 1;
}

void
print(int num, char *order) {
	int i;
	for (i=0; i<num; i++) {
		printf("%c", order[i]);
	}
	printf("\n");
}

void
doit2(int num, char *order) {
	int i;

	if (num==num_vars) {
		print(num, order);
		return;
	}
	for (i=0; i<num_vars; i++) {
		if (memchr(order, vars[i], num)) continue;
		order[num] = vars[i];
		if (test(num+1,order)) {
#if DEBUG
			printf("HCK: num=%d, trying '%c'\n", num, vars[i]);
#endif
			doit2(num+1, order);
		}
	}
}

void
doit(void) {
	char order[25];
	doit2(0, &order[0]);
}

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

int
main(void) {
	char buf[102400];
#if DEBUG
	int i;
#endif
	int blank=0;

	while(fgets(buf, 1024, stdin)) {
		char *s;
		num_vars = num_cons = 0;
		s = strtok(buf, " \t\r\n");
		while(s) {
			vars[num_vars++] = *s;
			s = strtok(NULL, " \t\r\n");
		}
		fgets(buf, 1024, stdin);
		s = strtok(buf, " \t\r\n");
		while(s) {
			cons[num_cons].a = *s;
			s = strtok(NULL, " \t\r\n");
			cons[num_cons].b = *s;
			num_cons++;
			s = strtok(NULL, " \t\r\n");
		}
		qsort(vars, num_vars, sizeof(char), compar);
#if DEBUG
		printf("%d vars:", num_vars);
		for (i=0; i<num_vars; i++) {
			printf(" %c", vars[i]);
		}
		printf("\n%d constraints:", num_cons);
		for (i=0; i<num_cons; i++) {
			printf(" %c<%c", cons[i].a, cons[i].b);
		}
		printf("\n");
#endif
		if (blank) printf("\n");
		blank=1;
		doit();
	}
	return 0;
}