Sharing Chocolate (UVA 1099, UVALive 4794, World Finals >> 2010 - Harbin)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100000

bool dp[(1<<15) + 2][100+2];
bool vis[(1<<15) + 2][100+2];
int arr[15+2], n, sum[(1<<15)+2];

void maskSum()
{
    int limit = (1<<n);
    for(int mask=0; mask<limit; mask++)
    {
        int tot = 0;
        for(int i=0; i<n; i++)
            if((mask & (1<<i)))
                tot+=arr[i];
        sum[mask]=tot;
    }
return;
}

bool func(int mask, int row)
{
    int inverse = ((1<<n)-1)^mask;
    if(__builtin_popcount(inverse)==1) return true;

    bool &ret = dp[mask][row];
    if(vis[mask][row]) return ret;

    vis[mask][row]=true;
    ret = false;

    int col = sum[inverse]/row;

    for(int split = inverse & (inverse-1); split; split = (split-1) & inverse) //find all subsets of the mask
    {
        int split2 = inverse^split;
        if(split2>split) break;

        if(sum[split]%row==0 && sum[split2]%row==0)
            ret = ret | (func(mask | split, row) & func(mask | split2, row));
         if(sum[split]%col==0 && sum[split2]%col==0)
            ret = ret | (func(mask | split, sum[split2]/col) & func(mask | split2, sum[split]/col));
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc, kk=1, tot, row, col;
    string s;
    char ch;
    while(cin>>n && n)
    {
        cin>>row>>col;
        tot=0;
        for(int i=0; i<n; i++)
        {
            cin>>arr[i];
            tot+=arr[i];
        }
        if(tot!=row*col)
        {
            cout<<"Case "<<kk++<<": No\n";
            continue;
        }

        maskSum();
        CLR(vis);

        if(func(0, row))    cout<<"Case "<<kk++<<": Yes\n";
        else    cout<<"Case "<<kk++<<": No\n";
    }
    return 0;
}