Poj Solution 2133

http://poj.org/problem?id=2133

#include<iostream>
using namespace std;

long a[140000],s[140000];

int main()
{
    long i,n,m,j;long result;
    long begin[200],st,k,ss;
    char c;
    while(1)
    {
    cin>>m>>n;
    if(cin.fail())break;
    
    long h;
    h=(1<<16);
    result=0;
    for(j=0;j<m;j++)
    {
        cin>>c;
        result*=2;
        result+=c-'0';
    }
            
            
    for(i=0;i<n;i++)
    {
        begin[i]=0;
        for(j=0;j<m;j++)
        {
            cin>>c;
            begin[i]*=2;
            begin[i]+=c-'0';
        }
        a[i]=begin[i];
    }
    for(i=0;i<h;i++)
    s[i]=-1;
    
    //for(i=0;i<n;i++)
    //s[begin[i]]=0;
    
    ss=0;k=0;
    for(st=n;st<h+n&&st!=k;)
    {
        k=st;
        for(i=ss;i<k;i++)
        for(j=0;j<n;j++)
        {    
            if(s[a[i]^begin[j]]<0)
            {
                s[a[i]^begin[j]]=(s[a[i]]>=0?s[a[i]]:0)+1;
                a[st++]=a[i]^begin[j];
            }
        }
        ss=k;
    }
    
    
    long best,bi,need;
    bi=-1;
    for(i=0;i<h;i++)
    if(s[i]>=0)
    {
        need=0;
        for(j=0;j<m;j++)
        if((result&(1<<j))!=(i&(1<<j)))need++;
        

        if(bi<0||(need<best||(need==best&&s[i]<s[bi])))
        {
            bi=i;
            best=need;
        }
    }
    if(bi<0)while(1)cout<<"sadfsdf";
    cout<<s[bi]<<endl;
    for(i=m-1;i>=0;i--)
    cout<<((bi>>i)&1);
    cout<<endl;
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *