normalizecube.c

1995年ACM contest FINAL试题和源码

/*

1995-96 ACM International Collegiate Programming Contest
Southwestern European Regional Contest
ETH Zurich, Switzerland
December 9, 1995


Problem: Cube

Idea:			Erwin Achermann, ETH Zurich
Implementation:	Manuel Bleichenbacher, Head Judge

This program takes the file cube.out and rotates every
solution so that part a has a certain position. The result
is written to cube.norm. Sorting the solutions is done
externally.

*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <assert.h>


typedef enum {
	FALSE = 0,
	TRUE = 1
} bool;


/* rotation */

const int cRotation1[27] =
	{  2,  5,  8,  1,  4,  7,  0,  3,  6,
	  11, 14, 17, 10, 13, 16,  9, 12, 15,
	  20, 23, 26, 19, 22, 25, 18, 21, 24 };
	  
const int cRotation2[27] =
	{ 18, 19, 20,  9, 10, 11,  0,  1,  2,
	  21, 22, 23, 12, 13, 14,  3,  4,  5,
	  24, 25, 26, 15, 16, 17,  6,  7,  8 };
	 
const int cRotation3[27] =
	{  2, 11, 20,  5, 14, 23,  8, 17, 26,
	   1, 10, 19,  4, 13, 22,  7, 16, 25,
	   0,  9, 18,  3, 12, 21,  6, 15, 24 };

typedef char Cube[28];

void RotateCube (Cube cube, int r1, int r2, int r3);
bool NormalizeCube (Cube cube);


void RotateCube (Cube cube, int r1, int r2, int r3)
{
	int i, j;
	Cube c;
	
	c[27] = 0;
	
	/* rotation */
	for (i = 0; i < r1; i++) {
		for (j = 0; j < 27; j++)
			c[ cRotation1[j] ] = cube[j];
		strcpy(cube, c);
	}
	for (i = 0; i < r2; i++) {
		for (j = 0; j < 27; j++)
			c[ cRotation2[j] ] = cube[j];
		strcpy(cube, c);
	}
	for (i = 0; i < r3; i++) {
		for (j = 0; j < 27; j++)
			c[ cRotation3[j] ] = cube[j];
		strcpy(cube, c);
	}
}


bool NormalizeCube (Cube cube)
{
	Cube c;
	int i, j, k;
	char* p;
	
	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
			for (k = 0; k < 4; k++) {
				strcpy (c, cube);
				RotateCube (c, i, j, k);
				p = strstr (c, "aaaa");
				if (p != NULL && (p - c) % 3 == 0) {
					strcpy (cube, c);
					return TRUE;
				}
			}
	return FALSE;
}


int main(int argc, char* argv[])
{
	FILE *fout, *fnorm;
	char line[1024];
	
	fout = fopen("cube.out", "r");
	assert( fout != 0 );
	
	fnorm = fopen("cube.norm", "w");
	assert( fnorm != 0 );
	
	while ( !feof(fout) ) {
		if ( fgets (line, 1024, fout) == NULL )
			break;
		line[27] = '\0';
		if ( strlen(line) != 27 )
			break;
			
		if ( !NormalizeCube (line) ) {
			printf("WRONG OUTPUT.\n");
			break;
		}
		fprintf (fnorm, "%s\n", line);
	}
	
	fclose( fnorm );
	fclose( fout );

	return 0;
}