4794_alt.cpp

#include <cstdio>

#include <iostream>

#include <map>

#include <set>

#include <vector>

#include <cstdlib>

#include <cstring>

using namespace std;

const int MAX_WIDTH = 100;

const int MAX_HEIGHT = 100;

const int MAX_PIECES = 15;

int heightTable[1<<MAX_PIECES][MAX_WIDTH+1];

const int IMPOSSIBLE = -1;

const int UNKNOWN = 0;

int nrPieces = -1;

int pieceSetToSize[1<<MAX_PIECES];

map<int, set<int> > sizeToPieceSets;

int computeSizeOfSet(int set)

{

    int sum = 0;

    for (int i = 1; i <= set; i <<= 1)

    {

        if (set & i) sum += pieceSetToSize[i];

    }

    return sum;

}

void precomputeSizes()

{

    sizeToPieceSets.clear();

    for (int pieceSet = 1; pieceSet < (1 << nrPieces); pieceSet++)

    {

        int size = computeSizeOfSet(pieceSet);

        pieceSetToSize[pieceSet] = size;

        if (sizeToPieceSets.find(size) == sizeToPieceSets.end())

        {

            sizeToPieceSets.insert(make_pair(size, set<int>()));

        }

        sizeToPieceSets[size].insert(pieceSet);

    }

}

int countPieces(int pieceSet)

{

    int count = 0;

    while (pieceSet > 0)

    {

        if (pieceSet & 1) count++;

        pieceSet >>=1;

    }

    return count;

}

int computeHeight(int pieceSet, int width, int height, int recDepth)

{   

    int currentSize = pieceSetToSize[pieceSet];

    //already calculated this combination

    if (heightTable[pieceSet][width] != UNKNOWN) return heightTable[pieceSet][width];

    //base case, one piece

    if (countPieces(pieceSet) == 1)

    {

        if (width * height == currentSize)

        {

            heightTable[pieceSet][width] = height;

        }

        else

        {

            heightTable[pieceSet][width] = IMPOSSIBLE;

        }

        return heightTable[pieceSet][width];

    }

    //try to split up the set and place the sets into the bar

    for (int possiblePieceSet = 1; possiblePieceSet < pieceSet; possiblePieceSet++)

    {

        int complimentaryPieceSet = pieceSet ^ possiblePieceSet;

        int possibleSize = pieceSetToSize[possiblePieceSet];

        int complimentarySize = pieceSetToSize[complimentaryPieceSet];

        //is it a proper subset

        if ((pieceSet & possiblePieceSet) != possiblePieceSet) continue;

        //can they fit

        if (possibleSize + complimentarySize != currentSize) continue;

        //can they fit vertically stacked

        if (possibleSize % width == 0 && complimentarySize % width == 0)

        {

            int possibleHeight = computeHeight(possiblePieceSet, width, possibleSize / width, recDepth + 1);

            int complimentaryHeight = computeHeight(complimentaryPieceSet, width, complimentarySize / width, recDepth + 1);

            if (possibleHeight != IMPOSSIBLE && complimentaryHeight != IMPOSSIBLE && possibleHeight + complimentaryHeight == height)

            {

                return heightTable[pieceSet][width] = height;

            } 

        }

        //can they fit horizontally stacked

        if (possibleSize % height == 0 && complimentarySize % height == 0)

        {

            int possibleWidth = (possibleSize / height);

            int complimentaryWidth = (complimentarySize / height);

            int possibleHeight = computeHeight(possiblePieceSet, possibleWidth, height, recDepth + 1);

            int complimentaryHeight = computeHeight(complimentaryPieceSet, complimentaryWidth, height, recDepth + 1);

            int widthSum = possibleWidth + complimentaryWidth;

            if (possibleHeight != IMPOSSIBLE && complimentaryHeight != IMPOSSIBLE && 

                possibleHeight == height && complimentaryHeight == height && widthSum == width)

            {

                return heightTable[pieceSet][width] = height;

            }

        }

    }

    //no solution found

    return heightTable[pieceSet][width] = IMPOSSIBLE;

}

int main()

{

    int testcase = 0;

    while (++testcase)

    {

        cin >> nrPieces;

        if (nrPieces == 0) break;

        memset(heightTable, UNKNOWN, sizeof(heightTable));

        //read chocolate bar

        int width = -1;

        int height = -1;

        cin >> width >> height;

        //read every piece

        int sumOfSizes = 0;

        for (int i = 0; i < nrPieces; i++)

        {

            cin >> pieceSetToSize[1<<i];

            sumOfSizes += pieceSetToSize[1<<i];

        }

        precomputeSizes();

        bool result = sumOfSizes != width * height ? false : computeHeight((1<<nrPieces)-1, width, height, 0) == height;

        cout << "Case " << testcase << ": " << (result ? "Yes" : "No") << endl;

    }

    return 0;

}