1524.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1524 on 2005-12-13 at 21:41:24 */ 
#include <cstdio>

const char code[] = "NOP";
const int MAX = 5000;

char gene[MAX];

bool find(int);
bool legal(int);

int main()
{
	int i, n;
	
	find(0);
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) {
			putchar(gene[i]);
		}
		putchar('\n');
	}
	
	return 0;
}

bool find(int n)
{
	if(n == MAX) {
		return true;
	} else {
		int i;
		for(i = 0; i < 3; i++) {
			gene[n] = code[i];
			if(legal(n) && find(n+1)) {
				return true;
			}
		}
		return false;
	}
}

bool legal(int n)
{
	int max = (n+1) / 2, i, j;
	for(i = 1; i <= max; i++) {
		int ah = n - 2 * i + 1;
		int bh = n - i + 1;
		bool same = true;
		for(j = 0; j < i && same; j++) {
			if(gene[ah+j] != gene[bh+j]) {
				same = false;
			}
		}
		if(same) {
			return false;
		}
	}
	return true;
}