Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

No Rectangles

135.c

/* 135 - No Rectangles */
#include <stdio.h>
#include <string.h>

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

int k,n;
char mat[1000][1000];

int
test(void) {
	int a,b,c;

	for (a=0; a<n-1; a++) {
		for (b=0; b<n-1; b++) {
			if (!mat[a][b]) continue;
			for (c=1; c<n-MAX(a,b); c++) {
				if (mat[a+c][b] && mat[a][b+c] && mat[a+c][b+c]) {
					return 0;
				}
			}
		}
	}
	return 1;
}

void
calc(void) {
	int i,j;
	memset(mat, 0, sizeof(mat));

	for (i=0; i<k; i++) {
		mat[0][i] = mat[i][0] = 1;
	}
	for (i=1; i<k; i++) {
		for (j=1; j<k; j++) {
			mat[i][(k-1)*i+j] = mat[(k-1)*i+j][i] = 1;
		}
	}
	for (i=0; i<k-1; i++) {
		for (j=0; j<k-1; j++) {
			int a,b;
			int c = i*j % (k-1);
			for (a=0; a<k-1; a++) {
				for (b=0; b<k-1; b++) {
					if ((k-1+a-b)%(k-1) == c) {
						mat[k+(k-1)*i+a][k+(k-1)*j+b] = 1;
					}
				}
			}
		}
	}
}

void
print(void) {
	int i,j;
#if DEBUG
	for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			if (mat[i][j]) {
				printf("X");
			} else {
				printf(".");
			}
		}
		printf("\n");
	}
#endif
	for (i=0; i<n; i++) {
		int first=1;
		for (j=0; j<n; j++) {
			if (mat[i][j]) {
				if (first) {
					first=0;
				} else {
					printf(" ");
				}
				printf("%d", j+1);
			}
		}
		printf("\n");
	}
}

int
main(void) {
	int first=1;
	while(scanf("%d", &k)==1) {
		if (first) {
			first=0;
		} else {
			printf("\n");
		}
		n = k*k-k+1;
		calc();
#if DEBUG
		if (test()) {
			printf("Ok\n");
		} else {
			printf("ERROR!\n");
			continue;
		}
#endif
		print();
	}
	return 0;
}