SRM569 Div1 Easy "TheDevice"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12388
訳
ある特別な装置(デバイス)があり、その構造を正確に知る必要がある。
その装置は、特殊なプレートによって動作する。
各プレートには左から右にM個のビットが書かれている。
装置にはプレートをはめ込む場所が2つと、結果を出力するスクリーンがあった。
装置にプレートを2つはめ込むと、M個のビットがスクリーンに映し出される。
出力されるそれぞれのビットは、その場所に関連する、入力した2つのビットを
OR AND XORのいずれかのビット演算をしたものとなる。
それぞれのビットにおいて、どの演算が使われているかを知りたい。
現在N枚のプレートを持っている。
装置の構造を知るために、任意の2枚のプレートを入力に使うことができる。
もしかしたら、持っているプレートで全てのパターンをテストしても、
装置の構造を一意に判定する事はできないかもしれない。
N枚のプレートの情報platesが与えられる。
装置の構造を正確に把握するために、あと何枚のプレートを追加すればいいかを返せ。
制約
1 <= プレートの数 <= 50
1 <= 各プレートのビット数 <= 50
考えた事
現状のままでOKかはDiv2 Mediumと同じように、
1列に0が1つ、1が2つ以上あるかどうかで。
追加するプレートは任意のビット長にできるため、
列ごとの0と1の足りない分の最大値でいける。
最初、答えは0か1かだと思ってよく考えずにサブミットして
WAしまくった・・
ソースコード
class TheDevice { public: int minimumAdditional(vector <string> plates){ int res = 0; for( int i = 0; i < plates[0].length(); i++ ){ int one = 0; int zero = 0; for( int j = 0; j < plates.size(); j++ ){ if( plates[j][i] == '0' ) zero++; if( plates[j][i] == '1' ) one++; } int nOne = max( 0, 2 - one ); int nZero = max( 0, 1 - zero ); res = max( res, nOne + nZero ); } return res; } };