POJ 水題若干

POJ 1013 Counterfeit Dollar

 
題意：有一打硬幣，其中有一個是假幣，質量可能較輕，也可能較重。通過三次稱重將假幣找出。

由於計算機很難模仿人的想法來實現問題。這道題我糾結了很久。

最後我是通過一一枚舉的笨方法做的。就是從A硬幣開始到L硬幣結束，一一假設其為假幣，其中又分為輕和重。當符合三次稱重之後便找到了假幣。

後來看網上有人是將三次稱重這樣實現的：給這十二枚硬幣賦初值。如果是even，那麼硬幣值不變。如果是up，那麼左邊的自加，右邊的自減。由於對於不確定的硬幣還要做下一次測試。所以通過三次測試之後，偏離初值最大的必然為假幣

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int main ()
{
    int n,i,j,k;
    cin>>n;
    while(n--)
    {
        char al[3][20],ar[3][20],a[3][10];
        int v[15]= {0},visit[15]= {0};
        bool flag=true;
        for (i=0; i<3; i++)
            cin>>al[i]>>ar[i]>>a[i];
        for (i=0; i<24; i++)
        {
            flag=true;
            v[i/2]=(i%2==0?-1:1);
            for (k=0; k<3; k++)
            {
                int left=0,right=0;
                for (j=0; j<strlen(al[k]); j++)
                    left+=v[al[k][j]-'A'];
                for (j=0; j<strlen(ar[k]); j++)
                    right+=v[ar[k][j]-'A'];
                if (strcmp(a[k],"even")==0 && left!=right) flag=false;
                if (strcmp(a[k],"up")==0 && !(left>right)) flag=false;
                if (strcmp(a[k],"down")==0 && !(left<right)) flag=false;
            }
            v[i/2]=0;
            if (flag) break;
        }
        if (!(i%2)) printf("%c is the counterfeit coin and it is light. \n",i/2+'A');
        else printf("%c is the counterfeit coin and it is heavy. \n",i/2+'A');
    }
    return 0;
}