题目描述
玛莎和比尔各自有自己的弹珠收藏。他们想重新分配收藏品,使两人能平等拥有弹珠。如果所有的弹珠的价值相同,那么他们就可以平分。但不幸的是,有一些弹珠更大,或者更美丽,所以,玛莎和比尔给每个弹珠一个1到6的价值。现在他们想平分这些弹珠,使每个人得到的总价值相同。不幸的是,他们发现,他们可能无法以这种方式分弹珠(即使弹珠的总价值为偶数)。例如,如果有一个价值为1、一个价值为3和两个价值为4的弹珠,这样他们就不能把弹珠分为价值相等的两部分。因此,他们想要你写一个程序,告诉他们是否能将所有弹珠分成价值相等的两部分。
输入输出格式
输入格式:
输入文件有若干行,行中包含六个非负整数N1,。..,N6,其中mi是数值i的弹珠的价值。最大弹珠总数将达到20000。
输入文件的最后一行是0 0 0 0 0 0 。不要处理这一行。
输出格式:
对于每一组数据,输出"Collection #k:", k为输出的是第几组, 接着是"Can be divided." 或 "Can't be divided.".
每一组输出后多打一个空行。
输入输出样例
输入样例#1:
1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0
输出样例#1: View Code
Collection #1:Can't be divided.Collection #2:Can be divided. 朴素方法三重循环很可能超时 用setbit!!
#includeusing namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define repp(i,a,b) for(int i=(a);i>=(b);--i)#define RI(n) scanf("%d",&(n))#define RII(n,m) scanf("%d%d",&n,&m)#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)#define RS(s) scanf("%s",s);#define ll long long#define pb push_back#define CLR(A,v) memset(A,v,sizeof A)//#define inf 0x3f3f3f3f#define lson l,m,pos<<1#define rson m+1,r,pos<<1|1const int N=5e5+6;bitset<120005>bit;//不要开太大 容易超时ll sum,a[N];int main(){ int cas=0; while(1) { bit.reset(); bit[0]=1; sum=0; rep(i,1,6)scanf("%lld",&a[i]),sum+=i*a[i]; if(!sum)break; cout<<"Collection #"<<++cas<<":"<