tyvj1194 划分大理石

描述

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

输入格式

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

输出格式

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

测试样例1

输入

输出

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

const int maxn = ;

int n,sum,a[],w[maxn];

bool f[maxn];

int main(){

    bool ok = true,ans = false;

    while(ok){

        ok = false;

        n = sum = ;

        for(int i = ;i <= ;i++){

            scanf("%d",&a[i]);

            if(a[i]) ok = true;

            sum += a[i]*i;

            for(int j = ;j <= a[i];j<<=){

                w[++n] = j * i;

                a[i] -= j;

            }

            w[++n] = a[i] * i;

        }

        if(!ok) break;

        if(sum & ){

            puts("Can't");

            continue;

        }

        memset(f,false,sizeof(f));

        f[] = true;

        for(int i = ;i <= n;i++){

            for(int j = sum >> ;j >= w[i];j--){

                if(f[j - w[i]]) f[j] = true;

            }

            if(f[sum>>]){

                ans = true;

                break;

            }

        }

        if(ans) puts("Can");

        else puts("Can't");

    }

    return ;

}