tyvj 1194

描述 Description

有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过20000。 

输入格式 InputFormat

有多组数据！
所以可能有多行
如果有0 0 0 0 0 0表示输入文件结束
其余的行为6个整数

输出格式 OutputFormat

有多少行可行数据就有几行输出
如果划分成功，输出Can，否则Can‘t

样例输入 SampleInput [复制数据]

4 7 4 5 9 1

9 8 1 7 2 4

6 6 8 5 9 2

1 6 6 1 0 7

5 9 3 8 8 4

0 0 0 0 0 0

样例输出 SampleOutput [复制数据]

Can‘t

Can

Can‘t

Can‘t

Can

#include<iostream>

using namespace std;

int n[7];  //价值为i的物品的个数

int SumValue;  //物品总价值

int HalfValue;  //物品平分价值

bool flag;    //标记是否能平分SumValue

void DFS(int value,int pre)

{

if(flag)

return;

if(value=http://www.mamicode.com/=HalfValue)

{

flag=true;

return;

}

for(int i=pre;i>=1;i--)

{

if(n[i])

{

if(value+i<=HalfValue)

{

n[i]--;

DFS(value+i,i);

if(flag)

break;

}

}

}

return;

}

int main(int i)

{

int test=1;

while(cin>>n[1]>>n[2]>>n[3]>>n[4]>>n[5]>>n[6])

{

SumValue=http://www.mamicode.com/0; //物品总价值

for(i=1;i<=6;i++)

SumValue+=i*n[i];

if(SumValue=http://www.mamicode.com/=0)

break;

if(SumValue%2)    //sum为奇数，无法平分

{

cout<<"Can‘t"<<endl;    //注意有空行

continue;

}

HalfValue=http://www.mamicode.com/SumValue/2;

flag=false;

DFS(0,6);

if(flag)

{

cout<<"Can"<<endl;

continue;

}

else

{

cout<<"Can‘t"<<endl;

continue;

}

    }

return 0;

}