1141.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1141 on 2006-03-14 at 20:13:35 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 65536;

int main()
{
	int i, j, k, t, marb[6], stack[MAX];
	bool dvd[MAX];

	for(t = 1; true; t++) {
		int v = 0;
		for(i = 0; i < 6; i++) {
			scanf("%d", &marb[i]);
			v += marb[i] * (i+1);
		}
		if(v == 0) break;
		printf("Collection #%d:\n", t);
		if(v & 1) { printf("Can't be divided.\n\n"); continue; }
		v >>= 1;
		memset(dvd, false, sizeof(dvd)); dvd[0] = true;
		int top = 0; stack[top++] = 0;
		for(i = 0; i < 6; i++) {
			int x = top;
			for(j = 0; j < x; j++)
				for(k = 1; k <= marb[i]; k++) {
					int val = stack[j] + (i+1) * k;
					if(val > v || dvd[val]) break;
					stack[top++] = val; dvd[val] = true;
				}
		}
		printf("Can%s be divided.\n\n", dvd[v] ? "" : "'t");
	}
	
	return 0;
}