2014年12月15日 星期一

2014/12/15 ACM-ICPC Liva Archive 4794 - Sharing Chocolate

/* https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2795 */
#include <iostream>
#include <cstdio>

using namespace std;

int area[1<<15];

int N;
int x0, y0;
int num[20];

bool DP[200][1<<15];
bool OK[200][1<<15];

bool search(int x, int h, int cnt)
{
    int y = area[h]/x;
    
    if( cnt == 1 ) OK[min(x, y)][h] = DP[min(x, y)][h] = true;
    if( OK[min(x, y)][h] ) return DP[min(x, y)][h];
    
    for(int i = 1; i < (1<<cnt)-1; i++)
    {
        int ci = 0, di = 0;
        int now = 0;
        
        for(int bi = 0, vi = 1; bi < N; bi++, vi<<=1)
        {
            if( h&vi ) 
            {
                if( 1<<ci & i ) now += vi, di++;
                ci++;
            }
        }
        
        if( area[now]%x == 0 )
            if( search(x, now, di) && search(x, h-now, ci-di) ) 
            {
                OK[min(x, y)][h] = DP[min(x, y)][h] = true;
                return true;
            }
                
        if( area[now]%y == 0 )
            if( search(y, now, di) && search(y, h-now, ci-di) ) 
            {
                OK[min(x, y)][h] = DP[min(x, y)][h] = true;
                return true;
            }
    }
    
    OK[min(x, y)][h] = true;
    DP[min(x, y)][h] = false;
    return false;    
}

int Ti = 0;

int main()
{
    while(1)
    {
        Ti++;
        
        scanf("%d", &N);
        if( !N ) break;
        
        scanf("%d %d", &x0, &y0);
        
        for(int i = 0; i < 1<<N; i++)
            for(int j = 0; j <= min(x0, y0); j++)
                OK[j][i] = false;
        
        for(int Ni = 0; Ni < N; Ni++)
            scanf("%d", &num[Ni]);
        
        area[0] = 0;
        
        for(int bi = 0, vi = 1; bi < N; bi++, vi<<=1) area[vi] = num[bi];
        
        for(int i = 1; i < 1<<N; i++)
        {
            int v = i&-i;
            area[i] = area[i-v]+area[v];
        }
        
        printf("Case %d: ", Ti);
        if( area[(1<<N)-1] != x0*y0 ) puts("No");
        else if( !search(x0, (1<<N)-1, N) ) puts("No");
        else puts("Yes");
    }
}

沒有留言:

張貼留言