1495.txt

杭电acm解题报告2001---2099.

#include <cstdio>
#include <memory>
#include <queue>
using namespace std;

bool v[110][110][110];
int c[3],tmin,avg;
struct inf
{
    int b[3];
    int time;

    inline bool fill(int f,int t)
    {
        int left;

        if(b[t]>=c[t] || v[ b[0] ][ b[1] ][ b[2] ] || b[f]==0)
            return false;
        else
        {
            left=c[t]-b[t];
            if(b[f]>=left)
            {
                b[f]-=left;
                b[t]=c[t];
            }
            else
            {
                b[t]+=b[f];
                b[f]=0;
            }
            time++;
            //v[ b[0] ][ b[1] ][ b[2] ]=true;
            return true;
        }
    }

    inline bool isOK()
    {
        return ((b[0]==avg && b[1]==avg) || (b[0]==avg && b[2]==avg) || (b[1]==avg && b[2]==avg));
    }
};
queue<inf> SQ;

void bfs()
{
    inf tt,t2;

    while(!SQ.empty())
    {
        tt=SQ.front();
        SQ.pop();
        if(tt.isOK())
        {
            tmin=tt.time;
            return ;
        }
        else
        {
            t2=tt;
            if( t2.fill(0,1) )
                SQ.push(t2);

            t2=tt;
            if( t2.fill(1,0) )
                SQ.push(t2);

            t2=tt;
            if( t2.fill(0,2) )
                SQ.push(t2);

            t2=tt;
            if( t2.fill(2,0) )
                SQ.push(t2);

            t2=tt;
            if( t2.fill(1,2) )
                SQ.push(t2);

            t2=tt;
            if( t2.fill(2,1) )
                SQ.push(t2);
        }
        v[ tt.b[0] ][ tt.b[1] ][ tt.b[2] ]=true;
    }
}

int main()
{
    int i;
    inf it;

    while(scanf("%d %d %d",&c[0],&c[1],&c[2])==3)
    {
        if(c[0]==0 && c[1]==0 && c[2]==0)
            return 0;
        if(c[0]%2==1)
        {
            printf("NO\n");
        }
        else
        {
            memset(v,0,sizeof(v));
            //v[c[0]][0][0]=true;
            it.b[0]=c[0];
            it.b[1]=it.b[2]=it.time=0;
            tmin=0x7ffffff;
            avg=c[0]/2;

            while(!SQ.empty())
                SQ.pop();
            SQ.push(it);

            bfs();

            if(tmin!=0x7ffffff)
                printf("%d\n",tmin);
            else
                printf("NO\n");
        }
    }
}