1070.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1070 on 2006-01-21 at 03:55:05 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int L_MAX = 16;
const int S_MAX = 1 << (L_MAX-1);

int rule[8], n;

int hash(const char*);
char* unhash(const int);
int rewrite(int);
int rotate(int);

int main()
{
	char word[L_MAX];
	int step[S_MAX], time[S_MAX], tar, i;

	while(scanf("%d\n", &n) != EOF) {
		int status = rotate(hash(gets(word)));
		for(i = 0; i < 8; i++) {
			char rulec[8];
			int p = hash(gets(rulec));
			rule[p>>1] = p & 1;
		}
		memset(time, -1, sizeof(time));
		step[0] = status; time[status] = 0;
		scanf("%d", &tar);
		bool end = false;
		for(i = 0; !end; i++) {
			if(i == tar) printf("%s\n", unhash(status)), end = true;
			else {
				status = rotate(rewrite(status));
				step[i+1] = status;
				if(time[status] == -1) time[status] = i+1;
				else {
					int T = i+1-time[status], begin = (tar-time[status])%T+time[status];
					printf("%s\n", unhash(step[begin])); end = true;
				}
			}
		}
	}
	
	return 0;
}

int hash(const char* str)
{
	int r = 0;
	while(*str != 0) r = r * 2 + *(str++) - 'a';
	return r;
}
char* unhash(const int code)
{
	static char buf[L_MAX]; int i;
	memset(buf, 0, sizeof(buf));
	for(i = n-1; i >= 0; i--)
		if(code & (1<<i)) buf[n-1-i] = 'b';
		else buf[n-1-i] = 'a';
	return buf;
}
int rewrite(const int prev)
{
	int i, r = 0;
	char *buf = unhash(prev);
	for(i = 0; i < n; i++) {
		int index = (buf[(i+n-2)%n]-'a')*4+(buf[i]-'a')*2+buf[(i+1)%n]-'a';
		r |= rule[index] << (n-1-i);
	}
	return r;
}
int rotate(int status)
{
	int i, r = S_MAX;
	for(i = 0; i < n; i++) {
		status = ((status<<1)&((1<<n)-1))+(status>>(n-1));
		r = min(r, status);
	}
	return r;
}