记录编号	300041	评测结果	A
题目名称	[POJ 1014] 大理石分割	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-08-28 08:05:57	内存使用	0.41 MiB

#include<cstdio>
#include<cstring>
int a[8];
int w[150];int n=0;
bool able[120005];
int main(){
	freopen("dividestone.in","r",stdin);
	freopen("dividestone.out","w",stdout);
	int cases=0;
	while(scanf("%d %d %d %d %d %d",a+1,a+2,a+3,a+4,a+5,a+6)&&a[1]+a[2]+a[3]+a[4]+a[5]+a[6]!=0){
		n=0;
		int sum=0;
		for(int i=1;i<=6;++i){
			sum+=i*a[i];
		}
		if(sum&1){
			printf("Collection #%d:\nCan't be divided.\n",++cases);
			continue;
		}
		for(int i=1;i<=6;++i){
			for(int j=0;(1<<j)<=a[i];++j){
				a[i]-=(1<<j);
				w[++n]=(1<<j)*i;
			}
			w[++n]=a[i]*i;
		}
		memset(able,0,sizeof(able));
		able[0]=true;
		sum=sum/2;
		for(int i=1;i<=n;++i){
			for(int j=sum-w[i];j>=0;--j){
				if(able[j])able[j+w[i]]=true;
			}
		}
		
		if(able[sum]){
			printf("Collection #%d:\nCan be divided.\n",++cases);
		}else{
			printf("Collection #%d:\nCan't be divided.\n",++cases);
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}