2014 1A A - Charging Chaos

domen111

Google Code Jam 2014年 Round 1A
原題(英文): https://code.google.com/codejam/contest/2984486/dashboard#s=p0
TOJ(中文，輸出有一點不同): http://toj.twbbs.org/oj/pro/4/

題意:
有N個插座和電器產品，每個電器產品和插座用長度為L的0與1表示，必須同樣才能配對，你可以做一個操作:切換所有插座的指定位元，請問你最小操作數。

範例測資:

Input	Output
3 3 2 01 11 10 11 00 10 2 3 101 111 010 001 2 2 01 10 10 01	Case #1: 1 Case #2: NOT POSSIBLE Case #3: 0

範例測資說明:
Case #1:
切換第二個位元，變成: 00 10 11

解法:
小冊資可以暴力解，不過比賽時我寫出一堆bug，花了2個多小時才AC
正解:
參考: http://puzzlersworld.com/interview-questions/google-code-jam/charging-chaos-solution-google-codejam/


用XOR做出表格計算兩個電器產品對電源需要切換的部分，找找看要切換哪個。
由上圖紅色文字可知要用"01"去切換，這代表第一個位元不用切換(0)，第二個位元要切換(1)。

AC code:

#include<iostream>

#include<bitset>

#include<set>

#include<algorithm>

using namespace std;

int T,n,l;

long long ou[150],de[150];

int count1(long long num)

{

        int ans=0;

        while(num!=0)

        {

                if(num&1)ans++;

                num>>=1;

        }

        return ans;

}

bool check(long long data)

{

        long long ouc[150],dec[150];

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

        {

                ouc[i]=ou[i]^data;

                dec[i]=de[i];

        }

        sort(ouc,ouc+n);

        sort(dec,dec+n);

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

                if(ouc[i]!=dec[i])

                        return 0;

        return 1;

}

long long readBits()

{

        string s;

        cin>>s;

        long long ans=0;

        for(int i=0;i<s.size();i++)

                ans<<=1,ans+=s[i]-'0';

        return ans;

}

int main()

{

        cin>>T;

        for(int no=1;no<=T;no++)

        {

                cin>>n>>l;

                set<long long> ta;

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

                        ou[i]=readBits();

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

                        de[i]=readBits();

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

                        for(int j=0;j<n;j++)

                                ta.insert(ou[i]^de[j]);

                set<long long>::iterator iter;

                int best=100000;

                for(iter=ta.begin();iter!=ta.end();iter++)

                {

                        if(check(*iter))

                                best=min(count1(*iter),best);

                }

                if(best==100000)

                        printf("Case #%d: NOT POSSIBLE\n",no);

                else

                        printf("Case #%d: %d\n",no,best);

        }

}