1877.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1877 on 2006-07-23 at 15:24:50 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 20;
const int S_MAX = 1 << MAX;
const double L_FUL = -1.5;
const double R_FUL = 1.5;

double leftTor, rightTor;

class Block {
public:
	int pos, w;
	void make();
	void print() const;
	void update(int) const;
};
void Block::make() {
	scanf("%d %d", &pos, &w);
	update(1);
}
void Block::print() const {
	printf("%d %d\n", pos, w);
}
void Block::update(int ex) const {
	leftTor += ex * w * (pos - L_FUL);
	rightTor += ex * w * (pos - R_FUL);
}

Block block[MAX];
bool vst[S_MAX];
int n, w, move[MAX];

bool find(int, int);

int main()
{
	int t, i, j;
	
	for(t = 1; scanf("%*d %d %d", &w, &n) != EOF && n != 0; t++) {
		leftTor = 1.5 * w; rightTor = -1.5 * w;
		for(i = 0; i < n; i++) block[i].make();
		memset(vst, false, sizeof(vst));
		printf("Case %d:\n", t);
		if(!find(0, 0)) printf("Impossible\n");
		else for(i = (1<<n)-1, j = 0; i != 0; i ^= 1<<move[j++]) block[move[j]].print();
	}
	
	return 0;
}

bool find(int status, int step)
{
	if(vst[status]) return false;
	else if(status == (1<<n)-1) return true;
	int i;
	vst[status] = true;
	if(leftTor < 0 || rightTor > 0) return false;
	for(i = 0; i < n; i++)
		if(!(status & (1<<i))) {
			block[i].update(-1); move[step] = i;
			if(find(status|(1<<i), step+1)) return true;
			block[i].update(1);
		}
	return false;
}