4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class T9 { public: 4fd800b3a8 2011-02-23 kinaba: string message(vector <string> part, vector <string> dict, vector <string> keystr) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: string key; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<keystr.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: key += keystr[i]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: sort(dict.begin(), dict.end()); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: string answer; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: const char* p = key.c_str(); 4fd800b3a8 2011-02-23 kinaba: while( *p ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( *p == '0' ) { 4fd800b3a8 2011-02-23 kinaba: answer += ' '; 4fd800b3a8 2011-02-23 kinaba: ++p; 4fd800b3a8 2011-02-23 kinaba: } else { 4fd800b3a8 2011-02-23 kinaba: vector<int> alp; 4fd800b3a8 2011-02-23 kinaba: while( '1' <= *p && *p <= '9' ) 4fd800b3a8 2011-02-23 kinaba: alp.push_back( *p++ - '1' ); 4fd800b3a8 2011-02-23 kinaba: int cnt = 0; 4fd800b3a8 2011-02-23 kinaba: while( *p=='*' || *p=='#' ) 4fd800b3a8 2011-02-23 kinaba: cnt += (*p++=='*' ? 5 : 1); 4fd800b3a8 2011-02-23 kinaba: answer += decode(part, dict, alp, cnt); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return answer; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: string decode(const vector<string>& part, const vector<string>& dict, const vector<int>& alp, int cnt) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<dict.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( match(dict[i], part, alp) ) 4fd800b3a8 2011-02-23 kinaba: if( cnt-- == 0 ) 4fd800b3a8 2011-02-23 kinaba: return dict[i]; 4fd800b3a8 2011-02-23 kinaba: assert(false); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: bool match(const string& d, const vector<string>& part, const vector<int>& alp) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( d.size() != alp.size() ) 4fd800b3a8 2011-02-23 kinaba: return false; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<d.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( part[alp[i]].find(d[i]) == string::npos ) 4fd800b3a8 2011-02-23 kinaba: return false; 4fd800b3a8 2011-02-23 kinaba: return true; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const string& Expected, const string& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (Expected == Received); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, T9().message(part, dict, keystr));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: string part_[] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = {"bad"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = {"2230223"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = "bad bad"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: string part_[] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = {"the", "tie"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = {"0843#000843#000"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = " tie tie "; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: string part_[] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = {"bad", "ace", "aad", "aae", "aaf", "acf", "acd", "the", "tie"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = {"223#02", "23*#00843#0"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = "aae bad tie "; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: string part_[] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = {"the", "tie", "bad", "ace", "aad", "aae", "aaf", "acf", "acd"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = {"84300223#02", "23#*"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = "the aae bad"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: string part_[] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = {"bad", "ace", "aad", "aae", "tie", "aaf", "acf", "acd", "the"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = {"223#02", "23######"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = "aae bad"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: string part_[] = {"", "rq", "lde", "yoauz", "cbfgn", "tjkpx", "wvs", "ih", "m"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = {"xktgmfmoqlmivm", 4fd800b3a8 2011-02-23 kinaba: "hmthr", 4fd800b3a8 2011-02-23 kinaba: "tpjgmnmaremiwm", 4fd800b3a8 2011-02-23 kinaba: "tpjcmnmyrlmhvm", 4fd800b3a8 2011-02-23 kinaba: "xkpnmgmzqdmhsm", 4fd800b3a8 2011-02-23 kinaba: "wqopvvmiig", 4fd800b3a8 2011-02-23 kinaba: "melbcbqeeg", 4fd800b3a8 2011-02-23 kinaba: "jkxnmbmardmhwm", 4fd800b3a8 2011-02-23 kinaba: "kpxnmcmyqlmism", 4fd800b3a8 2011-02-23 kinaba: "wrztvsmhhf", 4fd800b3a8 2011-02-23 kinaba: "srztssmiic", 4fd800b3a8 2011-02-23 kinaba: "pxtgmfmyrdmhwm", 4fd800b3a8 2011-02-23 kinaba: "vqoxswmiin", 4fd800b3a8 2011-02-23 kinaba: "wryksvmihb", 4fd800b3a8 2011-02-23 kinaba: "ptjfmbmoremhvm"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = {"00", 4fd800b3a8 2011-02-23 kinaba: "7246779885##00000089682000007246779885##0000724677", 4fd800b3a8 2011-02-23 kinaba: "9885#000089682000093355523350066659594239879###000"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = " wqopvvmiig hmthr wqopvvmiig vqoxswmiin hmthr melbcbqeeg pxtgmfmyrdmhwm "; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(6) 4fd800b3a8 2011-02-23 kinaba: string part_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = ; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(7) 4fd800b3a8 2011-02-23 kinaba: string part_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> part(part_, part_+sizeof(part_)/sizeof(*part_)); 4fd800b3a8 2011-02-23 kinaba: string dict_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> dict(dict_, dict_+sizeof(dict_)/sizeof(*dict_)); 4fd800b3a8 2011-02-23 kinaba: string keystr_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> keystr(keystr_, keystr_+sizeof(keystr_)/sizeof(*keystr_)); 4fd800b3a8 2011-02-23 kinaba: string _ = ; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE