46d6ab9496 2011-12-07 kinaba: #include <iostream> 46d6ab9496 2011-12-07 kinaba: #include <sstream> 46d6ab9496 2011-12-07 kinaba: #include <iomanip> 46d6ab9496 2011-12-07 kinaba: #include <vector> 46d6ab9496 2011-12-07 kinaba: #include <string> 46d6ab9496 2011-12-07 kinaba: #include <map> 46d6ab9496 2011-12-07 kinaba: #include <set> 46d6ab9496 2011-12-07 kinaba: #include <algorithm> 46d6ab9496 2011-12-07 kinaba: #include <numeric> 46d6ab9496 2011-12-07 kinaba: #include <iterator> 46d6ab9496 2011-12-07 kinaba: #include <functional> 46d6ab9496 2011-12-07 kinaba: #include <complex> 46d6ab9496 2011-12-07 kinaba: #include <queue> 46d6ab9496 2011-12-07 kinaba: #include <stack> 46d6ab9496 2011-12-07 kinaba: #include <cmath> 46d6ab9496 2011-12-07 kinaba: #include <cassert> 46d6ab9496 2011-12-07 kinaba: #include <cstring> 46d6ab9496 2011-12-07 kinaba: #ifdef __GNUC__ 46d6ab9496 2011-12-07 kinaba: #include <ext/hash_map> 46d6ab9496 2011-12-07 kinaba: #define unordered_map __gnu_cxx::hash_map 46d6ab9496 2011-12-07 kinaba: #else 46d6ab9496 2011-12-07 kinaba: #include <unordered_map> 46d6ab9496 2011-12-07 kinaba: #endif 46d6ab9496 2011-12-07 kinaba: using namespace std; 46d6ab9496 2011-12-07 kinaba: typedef long long LL; 46d6ab9496 2011-12-07 kinaba: typedef complex<double> CMP; 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: class Rumor { public: 46d6ab9496 2011-12-07 kinaba: int getMinimum(string knowledge, vector <string> graph) 46d6ab9496 2011-12-07 kinaba: { 46d6ab9496 2011-12-07 kinaba: const int N = knowledge.size(); 46d6ab9496 2011-12-07 kinaba: const int ALL = (1<<N) - 1; 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: // Turn the input into bit-vectors. 46d6ab9496 2011-12-07 kinaba: int know=0; 46d6ab9496 2011-12-07 kinaba: for(int v=0; v<N; ++v) 46d6ab9496 2011-12-07 kinaba: know |= (knowledge[v]=='Y') << v; 46d6ab9496 2011-12-07 kinaba: vector<int> g(N); 46d6ab9496 2011-12-07 kinaba: for(int v=0; v<N; ++v) 46d6ab9496 2011-12-07 kinaba: for(int u=0; u<N; ++u) 46d6ab9496 2011-12-07 kinaba: g[v] |= (graph[v][u]=='Y') << u; 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: // Try all possible patterns (which rumor each rabit spreads first when she knows both), and simulate. 46d6ab9496 2011-12-07 kinaba: int best = N+1; 46d6ab9496 2011-12-07 kinaba: for(int preferA=0; preferA<(1<<N); ++preferA) 46d6ab9496 2011-12-07 kinaba: for(int knowA=know, knowB=know, didA=0, didB=0, step=0; step<best; ++step) { 46d6ab9496 2011-12-07 kinaba: if( knowA==ALL && knowB==ALL ) 46d6ab9496 2011-12-07 kinaba: {best=step; break;} 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: int doA=0, doB=0; 46d6ab9496 2011-12-07 kinaba: for(int v=0; v<N; ++v) { 46d6ab9496 2011-12-07 kinaba: bool a_ok = (knowA & 1<<v) && !(didA & 1<<v); 46d6ab9496 2011-12-07 kinaba: bool b_ok = (knowB & 1<<v) && !(didB & 1<<v); 46d6ab9496 2011-12-07 kinaba: doA |= (a_ok && b_ok && (preferA & 1<<v) || a_ok && !b_ok) << v; 46d6ab9496 2011-12-07 kinaba: doB |= (a_ok && b_ok && !(preferA & 1<<v) || !a_ok && b_ok) << v; 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: didA |= doA; 46d6ab9496 2011-12-07 kinaba: didB |= doB; 46d6ab9496 2011-12-07 kinaba: for(int v=0; v<N; ++v) { 46d6ab9496 2011-12-07 kinaba: if(doA & 1<<v) knowA |= g[v]; 46d6ab9496 2011-12-07 kinaba: if(doB & 1<<v) knowB |= g[v]; 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: return best==N+1 ? -1 : best; 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: }; 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: // BEGIN CUT HERE 46d6ab9496 2011-12-07 kinaba: #include <ctime> 46d6ab9496 2011-12-07 kinaba: double start_time; string timer() 46d6ab9496 2011-12-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 46d6ab9496 2011-12-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 46d6ab9496 2011-12-07 kinaba: { os << "{ "; 46d6ab9496 2011-12-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 46d6ab9496 2011-12-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 46d6ab9496 2011-12-07 kinaba: void verify_case(const int& Expected, const int& Received) { 46d6ab9496 2011-12-07 kinaba: bool ok = (Expected == Received); 46d6ab9496 2011-12-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 46d6ab9496 2011-12-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 46d6ab9496 2011-12-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 46d6ab9496 2011-12-07 kinaba: #define END verify_case(_, Rumor().getMinimum(knowledge, graph));} 46d6ab9496 2011-12-07 kinaba: int main(){ 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: CASE(0) 46d6ab9496 2011-12-07 kinaba: string knowledge = "YNN"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = {"NYN" 46d6ab9496 2011-12-07 kinaba: ,"NNY" 46d6ab9496 2011-12-07 kinaba: ,"NNN"}; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = 3; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(1) 46d6ab9496 2011-12-07 kinaba: string knowledge = "YNNY"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = {"NYYN" 46d6ab9496 2011-12-07 kinaba: ,"YNNY" 46d6ab9496 2011-12-07 kinaba: ,"YNNY" 46d6ab9496 2011-12-07 kinaba: ,"NYYN"}; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = 1; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(2) 46d6ab9496 2011-12-07 kinaba: string knowledge = "YYYY"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = {"NYNN" 46d6ab9496 2011-12-07 kinaba: ,"YNYN" 46d6ab9496 2011-12-07 kinaba: ,"NYNY" 46d6ab9496 2011-12-07 kinaba: ,"NNYN"}; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = 0; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(3) 46d6ab9496 2011-12-07 kinaba: string knowledge = "YYYYYN"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = {"NYYYYN" 46d6ab9496 2011-12-07 kinaba: ,"YNYYYN" 46d6ab9496 2011-12-07 kinaba: ,"YYNYYN" 46d6ab9496 2011-12-07 kinaba: ,"YYYNYN" 46d6ab9496 2011-12-07 kinaba: ,"YYYYNN" 46d6ab9496 2011-12-07 kinaba: ,"NNNNNN"}; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = -1; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(4) 46d6ab9496 2011-12-07 kinaba: string knowledge = "NNNY"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = {"NNNN" 46d6ab9496 2011-12-07 kinaba: ,"YNNN" 46d6ab9496 2011-12-07 kinaba: ,"YNNN" 46d6ab9496 2011-12-07 kinaba: ,"NYYN"}; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = 3; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(5) 46d6ab9496 2011-12-07 kinaba: string knowledge = "NNNNNNNYYY"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = {"NYNNYNNYNN" 46d6ab9496 2011-12-07 kinaba: ,"NNYNYNNNNY" 46d6ab9496 2011-12-07 kinaba: ,"YYNNNYNNNN" 46d6ab9496 2011-12-07 kinaba: ,"YNNNYNYNNN" 46d6ab9496 2011-12-07 kinaba: ,"NNYNNYNNYN" 46d6ab9496 2011-12-07 kinaba: ,"NNNNYNNNYY" 46d6ab9496 2011-12-07 kinaba: ,"NYNYNYNNNN" 46d6ab9496 2011-12-07 kinaba: ,"NNNNNNYNYY" 46d6ab9496 2011-12-07 kinaba: ,"NNNYNNNYNY" 46d6ab9496 2011-12-07 kinaba: ,"NYYNNNNYNN"} 46d6ab9496 2011-12-07 kinaba: ; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = 2; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(6) 46d6ab9496 2011-12-07 kinaba: string knowledge = "YYYNNN"; 46d6ab9496 2011-12-07 kinaba: string graph_[] = { 46d6ab9496 2011-12-07 kinaba: "NNNYNY", 46d6ab9496 2011-12-07 kinaba: "NNNYYN", 46d6ab9496 2011-12-07 kinaba: "NNNNYY", 46d6ab9496 2011-12-07 kinaba: "NNNNNN", 46d6ab9496 2011-12-07 kinaba: "NNNNNN", 46d6ab9496 2011-12-07 kinaba: "NNNNNN" 46d6ab9496 2011-12-07 kinaba: }; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = 2; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: /* 46d6ab9496 2011-12-07 kinaba: CASE(7) 46d6ab9496 2011-12-07 kinaba: string knowledge = ; 46d6ab9496 2011-12-07 kinaba: string graph_[] = ; 46d6ab9496 2011-12-07 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 46d6ab9496 2011-12-07 kinaba: int _ = ; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: */ 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: // END CUT HERE