1908.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1908 on 2005-12-14 at 13:17:26 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAX = 128;
const int S_MAX = 16;

int a, b, c, d;

int cmp(const void*, const void*);
bool check(int*, int);
int change(const int);

int main()
{
	int n, p, i;
	int on[4], off[4];
	char status[S_MAX][MAX];
	
	while(scanf("%d %d", &n, &p) != EOF) {
		memset(status, 0, sizeof(status));
		for(i = 0; scanf("%d", &on[i]) != EOF; i++) {
			if(on[i] == -1) {
				break;
			}
		}
		for(i = 0; scanf("%d", &off[i]) != EOF; i++) {
			if(off[i] == -1) {
				break;
			}
		}
		// a : all  b : odd  c : even  d : 3k+1
		a = b = c = d = 0;
		int sn = 0;
		for(a = 0; a < 2; a++) {
			for(b = 0; b < 2; b++) {
				for(c = 0; c < 2; c++) {
					for(d = 0; d < 2; d++) {
						if(a+b+c+d <= p && (p-a-b-c-d)%2 == 0) {
							if(check(on, 1) && check(off, 0)) {
								for(i = 0; i < n; i++) {
									status[sn][i] = change(i+1) + '0';
								}
								sn++;
							}
						}
					}
				}
			}
		}
		qsort(status, sn, sizeof(status[0]), cmp);
		for(i = 0; i < sn; i++) {
			printf("%s\n", status[i]);
		}
	}
	
	return 0;
}

int cmp(const void* a, const void* b)
{
	return strcmp((char*)a, (char*)b);
}
bool check(int* num, int final)
{
	int i;
	for(i = 0; num[i] != -1; i++) {
		if(change(num[i]) != final) {
			return false;
		}
	}
	return true;
}
int change(const int num)
{
	int begin = 1 + a;
	if(num % 2 == 0) {
		begin += c;
	} else {
		begin += b;
	}
	if((num - 1) % 3 == 0) {
		begin += d;
	}
	return (begin % 2);
}