N能研の問題
問題はid:succeed:20050823#1124816046にあります。
C++初心者による効率も何も考えてない解答。計算量はO(2^n)。
#include <iostream> #include <vector> #include <string> using namespace std; typedef pair<string, int> QPair; void add(string &v); int compare(string &a, string &b); int main() { int n,m,a; string q; vector<QPair> question; vector<string> answer; while(1) { cin >> n >> m; if (n == 0 && m == 0) break; string index; for(int i=0;i<m;i++) { cin >> q >> a; question.push_back(QPair(q,a)); } index = string("0",n); for(int j=0;j<(2<<(n-1));add(index),j++) { for(int i=0;i<question.size();i++) { if (compare(question[i].first,index) != question[i].second) { break; } if (i == question.size()-1) { answer.push_back(index); } } } if (answer.size() == 1) { cout << answer[0] << endl; /* } else if (answer.size() > 1) { cout << answer.size() << " matched answers are found" << endl; for(int i=0;i<answer.size();i++) cout << answer[i] << endl; */ } else { cout << "NO" << endl; } answer.clear(); question.clear(); } } void add(string &v) { for(int i=0;i<v.length();i++) { if (v[i] == '0') { v[i] = '1'; break; } else { v[i] = '0'; } } } int compare(string &a, string &b) { int result = 0; for(int i=0;i<a.length();i++) { if (a[i] == b[i]) result++; } return result; }
途中のコメントアウトを外すと、解答の可能性のあるものをすべて表示します。
(追記)よくみたら、mainでreturn 0すらしてませんね。