POJ 1013 C++解法

大体の問題:
1ダース(12枚)の硬貨があり、そのうち偽札は1枚、本物は11枚しかありません.
A~Lを各硬貨の代号とする
偽札は本物より軽いかもしれないし、重いかもしれない.
今では天秤を使って、Inputが入力した3回の秤量に基づいて、偽札を見つけて、偽札が軽いか重いかを出力します.
 
 
問題解決の考え方:
シミュレーション法は考慮すべき状況が煩雑で,簡単な論理推理を用いて問題を解くことができる.
 
 
注意Inputの1行は1回の秤量を表し、各行には3つの文字列があり、それぞれ
Left right status
この秤量を表すとき、天秤の左に置かれた硬貨、天秤の右に置かれた硬貨、天秤の右に置かれた状態
 
 
合計3つのステータス:
Up:右盤が上昇し、右盤に軽い偽札があるかもしれないし、左盤に重い偽札があるかもしれないことを示しています.
Down:右盤が下がると、右盤に重い偽札があるかもしれないし、左盤に軽い偽札があるかもしれない.
Even:右盤と左盤がバランスしており、偽札が1枚しかないため、天秤の両側の硬貨がすべて本物であることを示しています.
 
問題の言葉に注意:
1、偽札が1枚しかない
2、偽札は本物の貨幣の重量に対して、軽くて重いかもしれない
3、3回だけ量って、しかも3回量ってちょうど良くて、必ず偽札を見つけることができます
4、秤量するたびに天秤の両端のコインの数が同じ
5、どのコインの秤量を選ぶかはinputで決める
 
3、4、5から分かるように、秤量する硬貨を毎回選択することが分からないため、3回の秤量は硬貨がいくつかしか選択されていないかもしれないし、1、2個の硬貨しか選択されていないかもしれないので、毎回秤量に用いられる硬貨の状態(真偽、そのうち偽札には軽重の分がある)をシミュレーション法で記録し、秤量されていない硬貨の状態(または状態変化)を導くことは困難であり、人は簡単にできるが、コンピュータは「導く」ことが難しい.コインを測る方法は不規則で非常に多いからだ.
 
問題を適切に転化した後、別の有効な方法で解決するしかない.
 
コインの秤量方法は不規則で未知であるが,コインを秤量した結果は3つしかなく,up,down,evenであった.そしてevenが現れると、天秤の両側の硬貨は必ず真の硬貨であり、偽の硬貨は必ず残りの硬貨の間にある(これは偽の硬貨が1枚しかないため)ので、私たちは1つのマーク配列zero[]を定義してevenをマークする時の真の硬貨を定義し、後の処理で彼らを排除することができる.
唯一扱いにくいのはupとdownの状態で、偽札が軽くて重い可能性があるため、この2つの状態は偽札が天秤のどちらに現れているのか分からない.
 
 
upとdownのステータスを処理する方法:
upまたはdown状態が発生した場合、天秤の両方のコインはすべて偽札と疑われるべきです(必ず本物と表記されているコインは疑われる必要はありません).
まずtime[]は、各硬貨の疑念度を記録し、time[i]=0は、硬貨iが疑念されていない(すなわち、本物である可能性がある)ことを示す.upステータスディスクに定義された硬貨は「疑わしい偽札」であり、「--」操作によって疑わしい軽偽札の程度を深め、「負号」は軽偽札の疑わしい方向である.down状態盤の硬貨は「偽札を疑い直す」ため、「++」操作で重偽札と疑われる程度を深め、「正号」は重偽札と疑われる疑いの方向となる.
では、1枚の本物が「軽偽札」と疑われると、次回の秤量で「++」操作で容疑を取り消す可能性があります.すべてのコインを初期化する疑いの度合いは0です.
秤量が終わったら、最も疑わしい(絶対値を取ることに注意)コインを見つけて、それが偽札です.疑いの方向が正しければ、重偽札である.負の場合は、軽偽札です.
 

//Memory Time
//252K   0MS

#include<iostream>
#include<cmath>
using namespace std;

int main(void)
{
	int cases;
	cin>>cases;
	for(int c=1;c<=cases;c++)
	{
		char left[3][7],right[3][7],status[3][7];

		int time['L'+1]={0};  //            
		bool zero['L'+1]={false};  //          （          ）

		for(int k=0;k<3;k++)
			cin>>left[k]>>right[k]>>status[k];

		for(int i=0;i<3;i++)
		{
			switch(status[i][0])  //      
			{
			    case 'u':     //up，      
					{
						for(int j=0;left[i][j];j++)
						{
							time[ left[i][j] ]++;  //  
							time[ right[i][j] ]--;  //  
						}
						break;
					}
				case 'd':     //down，      
					{
						for(int j=0;left[i][j];j++)
						{
							time[ left[i][j] ]--;  //  
							time[ right[i][j] ]++;  //  
						}
						break;
					}
				case 'e':     //down，    
					{
						for(int j=0;left[i][j];j++)
						{
							zero[ left[i][j] ]=true;   //    
							zero[ right[i][j] ]=true;   //    
						}
						break;
					}
			}
		}

		int max=-1;  //            （  ）
		char alpha;
		for(int j='A';j<='L';j++)
		{
			if(zero[j])  //    
				continue;

			if(max<=abs(time[j]))
			{
				max=abs(time[j]);
				alpha=j;
			}
		}

		cout<<alpha<<" is the counterfeit coin and it is ";
		if(time[alpha]>0)
			cout<<"heavy."<<endl;
		else
			cout<<"light."<<endl;
	}
	return 0;
}