SRM 144 DIV2 500
Pは0または1で構成される文字列でQ[i] = P[i-1] + P[i] + P[i+1]
となるような文字列Qが与えられるのでPを求めろという問題
多分相当いけてないけれどこれを書くのに7〜8時間かかった。
自分への戒めも含めてここに記録しておく。
#include <string> #include <vector> #include <sstream> using namespace std; class BinaryCode { public: vector <string> decode(string message) { vector <string> ret; char start; for (start = '0'; start < '2'; start++) { string original; stringstream cc; cc << start; original.append( cc.str() ); int i; for (i = 0; i < message.length(); i++) { int a, b, c, tmp; stringstream ss; a = message[i] - '0'; b = original[i] - '0'; if (i == 0) { tmp = a - b; ss << tmp; } else { c = original[i-1] - '0'; tmp = a - b - c; ss << tmp; } // last if ( i > 0 && i == message.length() - 1 ) { b = original[i-1] - '0'; // 1 c = message[i] - '0'; // 1 if ( c - b != original[i] - '0' ) { original = "NONE"; } break; } ss >> tmp; if ( tmp > 1 || tmp < 0 ) { original = "NONE"; break; } if (message.length() == 1) { if (original != message) { original = "NONE"; } break; } original.append(ss.str()); ss.clear(); ss.str(""); } ret.push_back(original); } return ret; } };