1538.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1538 on 2006-01-12 at 12:18:00 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 256;

class File {
public:
	char fra[MAX];
	int on, ln;
	int make();
	File set(int, int) const;
	bool operator <(const File&) const;
	bool operator !=(const File&) const;
};
int File::make() {
	if(gets(fra) == NULL) return -1;
	else if(fra[0] == 0) return 0;
	else {
		for(on = 0, ln = 0; fra[ln] != 0; ln++) on += fra[ln] - '0';
		return 1;
	}
}
File File::set(int o, int l) const {
	File f;
	f.on = o - on; f.ln = l - ln;
	return f;
}
bool File::operator <(const File& f) const {
	if(ln != f.ln) return ln < f.ln;
	else return on < f.on;
	//else return strcmp(fra, f.fra) < 0;
}
bool File::operator !=(const File& f) const {
	return (strcmp(fra, f.fra) != 0);
}

typedef pair<File*, File*> pff;

File file[MAX];
bool used[MAX];
char con[MAX];
int to, tl, n;

bool DFS(int);

int main()
{
	int r;
	bool end = false;

	while(!end) {
		to = tl = 0;
		for(n = 0; (r = file[n].make()) != 0; n++) {
			if(r == -1) { end = true; break; }
			to += file[n].on; tl += file[n].ln;
		}
		to /= n/2; tl /= n/2;
		sort(file, file+n);
		memset(used, false, sizeof(used));
		memset(con, 0, sizeof(con));
		DFS(0);
		printf("%s\n", con);
	}
}

bool DFS(int o)
{
	while(used[o]) o++;
	if(o == n) return true;
	else {
		used[o] = true;
		pff r = equal_range(file, file+n, file[o].set(to, tl));
		File* it;
		char fc[MAX] = "";
		for(it = r.first; it != r.second; it++)
			if(it == r.first || *it != *(it-1)) {
				used[it-file] = true;
				strcpy(fc, file[o].fra); strcat(fc, it->fra);
				if(o == 0) strcpy(con, fc);
				if(!strcmp(con, fc) && DFS(o+1)) return true;
				strcpy(fc, it->fra); strcat(fc, file[o].fra);
				if(o == 0) strcpy(con, fc);
				if(!strcmp(con, fc) && DFS(o+1)) return true;
				used[it-file] = false;
			}
		return false;
	}
}