問題
http://community.topcoder.com/stat?c=problem_statement&pm=10846&rd=14541
解き方
すべての暗号前の文字と暗号後の文字の組み合わせで、候補となる
キーがすべて作成できる。
あるキーについて、暗号後の文字を復号した時に暗号前の文字がすべて存在すれば
有効なので、上記で生成した全てのキーに対してこの条件が成り立つか判定すればよい。
コード
class NetworkXOneTimePad {
public:
string calc(string s1,string s2){
string ret="";
FORE(i,0,s1.size()){
ret+= s1[i]==s2[i] ? '0' : '1';
}
return ret;
}
int crack(vector<string> plaintexts, vector<string> ciphertexts) {
int n=plaintexts.size(),m=ciphertexts.size();
set<string> s;
FORE(i,0,n)FORE(j,0,m){
s.insert(calc(plaintexts[i],ciphertexts[j]));
}
set<string> ans;
for(set<string>::iterator it=s.begin();it!=s.end();it++){
int valid=1;
FORE(i,0,m){
string tmp=calc(*it,ciphertexts[i]);
int invalid=1;
FORE(j,0,n)if(tmp==plaintexts[j])invalid=0;
if(invalid)valid=0;
}
if(valid)ans.insert(*it);
}
return ans.size();
}
};
public:
string calc(string s1,string s2){
string ret="";
FORE(i,0,s1.size()){
ret+= s1[i]==s2[i] ? '0' : '1';
}
return ret;
}
int crack(vector<string> plaintexts, vector<string> ciphertexts) {
int n=plaintexts.size(),m=ciphertexts.size();
set<string> s;
FORE(i,0,n)FORE(j,0,m){
s.insert(calc(plaintexts[i],ciphertexts[j]));
}
set<string> ans;
for(set<string>::iterator it=s.begin();it!=s.end();it++){
int valid=1;
FORE(i,0,m){
string tmp=calc(*it,ciphertexts[i]);
int invalid=1;
FORE(j,0,n)if(tmp==plaintexts[j])invalid=0;
if(invalid)valid=0;
}
if(valid)ans.insert(*it);
}
return ans.size();
}
};