SRM569 Div2 Medium "TheDeviceDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12399
訳
ある特別な装置(デバイス)があり、その構造を正確に知る必要がある。
その装置は、特殊なプレートによって動作する。
各プレートには左から右にM個のビットが書かれている。
装置にはプレートをはめ込む場所が2つと、結果を出力するスクリーンがあった。
装置にプレートを2つはめ込むと、M個のビットがスクリーンに映し出される。
出力されるそれぞれのビットは、その場所に関連する、入力した2つのビットを
OR AND XORのいずれかのビット演算をしたものとなる。
それぞれのビットにおいて、どの演算が使われているかを知りたい。
現在N枚のプレートを持っている。
装置の構造を知るために、任意の2枚のプレートを入力に使うことができる。
もしかしたら、持っているプレートで全てのパターンをテストしても、
装置の構造を一意に判定する事はできないかもしれない。
N枚のプレートの情報platesが与えられる。
このプレートを使用して、装置の構造を正確に把握できるかどうかを返せ。
制約
1 <= プレートの数 <= 50
1 <= 各プレートのビット数 <= 50
考えた事
0と1でテストすると、ANDかOR,XORかを判定できる。
1と1でテストすると、XORかOR,ANDかを判定できる。
よって、全てのインデックスで、0が1つ以上、1が2つ以上ないといけない
ソースコード
class TheDeviceDiv2 { public: string identify(vector <string> plates){ int n = plates.size(); int bn = plates[0].length(); for( int b = 0; b < bn; b++ ){ int one = 0; int zero = 0; for( int i = 0; i < n; i++ ){ if( plates[i][b] == '1' ){ one++; }else{ zero++; } } if( zero == 0 || one < 2 ){ return "NO"; } } return "YES"; } };