2ba3bf09a0 2013-05-11 kinaba: #include <iostream> 2ba3bf09a0 2013-05-11 kinaba: #include <sstream> 2ba3bf09a0 2013-05-11 kinaba: #include <iomanip> 2ba3bf09a0 2013-05-11 kinaba: #include <vector> 2ba3bf09a0 2013-05-11 kinaba: #include <string> 2ba3bf09a0 2013-05-11 kinaba: #include <map> 2ba3bf09a0 2013-05-11 kinaba: #include <set> 2ba3bf09a0 2013-05-11 kinaba: #include <algorithm> 2ba3bf09a0 2013-05-11 kinaba: #include <numeric> 2ba3bf09a0 2013-05-11 kinaba: #include <iterator> 2ba3bf09a0 2013-05-11 kinaba: #include <functional> 2ba3bf09a0 2013-05-11 kinaba: #include <complex> 2ba3bf09a0 2013-05-11 kinaba: #include <queue> 2ba3bf09a0 2013-05-11 kinaba: #include <stack> 2ba3bf09a0 2013-05-11 kinaba: #include <cmath> 2ba3bf09a0 2013-05-11 kinaba: #include <cassert> 2ba3bf09a0 2013-05-11 kinaba: using namespace std; 2ba3bf09a0 2013-05-11 kinaba: typedef long long LL; 2ba3bf09a0 2013-05-11 kinaba: typedef long double LD; 2ba3bf09a0 2013-05-11 kinaba: typedef complex<LD> CMP; 2ba3bf09a0 2013-05-11 kinaba: 2ba3bf09a0 2013-05-11 kinaba: class DancingFoxes { public: 2ba3bf09a0 2013-05-11 kinaba: int minimalDays(vector <string> friendship) 2ba3bf09a0 2013-05-11 kinaba: { 2ba3bf09a0 2013-05-11 kinaba: static const int INF = 0x1fffffff; 2ba3bf09a0 2013-05-11 kinaba: int N = friendship.size(); 2ba3bf09a0 2013-05-11 kinaba: vector< vector<int> > M(N, vector<int>(N)); 2ba3bf09a0 2013-05-11 kinaba: for(int i=0; i<N; ++i) 2ba3bf09a0 2013-05-11 kinaba: for(int k=0; k<N; ++k) 2ba3bf09a0 2013-05-11 kinaba: M[i][k] = (friendship[i][k]=='Y' ? 1 : INF); 2ba3bf09a0 2013-05-11 kinaba: 2ba3bf09a0 2013-05-11 kinaba: for(int k=0; k<N; ++k) 2ba3bf09a0 2013-05-11 kinaba: for(int i=0; i<N; ++i) 2ba3bf09a0 2013-05-11 kinaba: for(int j=0; j<N; ++j) 2ba3bf09a0 2013-05-11 kinaba: M[i][j] = min(M[i][j], M[i][k]+M[k][j]); 2ba3bf09a0 2013-05-11 kinaba: 2ba3bf09a0 2013-05-11 kinaba: if(M[0][1] == INF) 2ba3bf09a0 2013-05-11 kinaba: return -1; 2ba3bf09a0 2013-05-11 kinaba: 2ba3bf09a0 2013-05-11 kinaba: int s = 0; 2ba3bf09a0 2013-05-11 kinaba: for(int d = M[0][1]; d>1; ++s) 2ba3bf09a0 2013-05-11 kinaba: d -= (d+1)/3; 2ba3bf09a0 2013-05-11 kinaba: return s; 2ba3bf09a0 2013-05-11 kinaba: } 2ba3bf09a0 2013-05-11 kinaba: }; 2ba3bf09a0 2013-05-11 kinaba: 2ba3bf09a0 2013-05-11 kinaba: // BEGIN CUT HERE 2ba3bf09a0 2013-05-11 kinaba: #include <ctime> 2ba3bf09a0 2013-05-11 kinaba: double start_time; string timer() 2ba3bf09a0 2013-05-11 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 2ba3bf09a0 2013-05-11 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 2ba3bf09a0 2013-05-11 kinaba: { os << "{ "; 2ba3bf09a0 2013-05-11 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 2ba3bf09a0 2013-05-11 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 2ba3bf09a0 2013-05-11 kinaba: void verify_case(const int& Expected, const int& Received) { 2ba3bf09a0 2013-05-11 kinaba: bool ok = (Expected == Received); 2ba3bf09a0 2013-05-11 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 2ba3bf09a0 2013-05-11 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 2ba3bf09a0 2013-05-11 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 2ba3bf09a0 2013-05-11 kinaba: #define END verify_case(_, DancingFoxes().minimalDays(friendship));} 2ba3bf09a0 2013-05-11 kinaba: int main(){ 2ba3bf09a0 2013-05-11 kinaba: 2ba3bf09a0 2013-05-11 kinaba: CASE(0) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = {"NNY", 2ba3bf09a0 2013-05-11 kinaba: "NNY", 2ba3bf09a0 2013-05-11 kinaba: "YYN"}; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int _ = 1; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: CASE(1) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = {"NNNNN", 2ba3bf09a0 2013-05-11 kinaba: "NNYYY", 2ba3bf09a0 2013-05-11 kinaba: "NYNYY", 2ba3bf09a0 2013-05-11 kinaba: "NYYNY", 2ba3bf09a0 2013-05-11 kinaba: "NYYYN"}; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int _ = -1; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: CASE(2) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = {"NNYYNN", 2ba3bf09a0 2013-05-11 kinaba: "NNNNYY", 2ba3bf09a0 2013-05-11 kinaba: "YNNNYN", 2ba3bf09a0 2013-05-11 kinaba: "YNNNNY", 2ba3bf09a0 2013-05-11 kinaba: "NYYNNN", 2ba3bf09a0 2013-05-11 kinaba: "NYNYNN"}; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int _ = 2; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: CASE(3) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = {"NNYNNNNYN", 2ba3bf09a0 2013-05-11 kinaba: "NNNNYNYNN", 2ba3bf09a0 2013-05-11 kinaba: "YNNYNYNNN", 2ba3bf09a0 2013-05-11 kinaba: "NNYNYNYYN", 2ba3bf09a0 2013-05-11 kinaba: "NYNYNNNNY", 2ba3bf09a0 2013-05-11 kinaba: "NNYNNNYNN", 2ba3bf09a0 2013-05-11 kinaba: "NYNYNYNNN", 2ba3bf09a0 2013-05-11 kinaba: "YNNYNNNNY", 2ba3bf09a0 2013-05-11 kinaba: "NNNNYNNYN"}; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int _ = 3; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: CASE(4) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = {"NY", 2ba3bf09a0 2013-05-11 kinaba: "YN"}; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int _ = 0; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: CASE(5) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = { 2ba3bf09a0 2013-05-11 kinaba: "NNYNNNNNN", 2ba3bf09a0 2013-05-11 kinaba: "NNNNNNNNY", 2ba3bf09a0 2013-05-11 kinaba: "YNNYNNNNN", 2ba3bf09a0 2013-05-11 kinaba: "NNYNYNNNN", 2ba3bf09a0 2013-05-11 kinaba: "NNNYNYNNN", 2ba3bf09a0 2013-05-11 kinaba: "NNNNYNYNN", 2ba3bf09a0 2013-05-11 kinaba: "NNNNNYNYN", 2ba3bf09a0 2013-05-11 kinaba: "NNNNNNYNY", 2ba3bf09a0 2013-05-11 kinaba: "NYNNNNNYN" 2ba3bf09a0 2013-05-11 kinaba: }; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int N = friendship.size(); 2ba3bf09a0 2013-05-11 kinaba: int idx[] = {0,8,1,2,3,4,5,6,7}; 2ba3bf09a0 2013-05-11 kinaba: for(int y=0; y<N; ++y, cout<<endl) 2ba3bf09a0 2013-05-11 kinaba: for(int x=0; x<N; ++x) { 2ba3bf09a0 2013-05-11 kinaba: cout << friendship[idx[y]][idx[x]]; 2ba3bf09a0 2013-05-11 kinaba: } 2ba3bf09a0 2013-05-11 kinaba: int _ = -1; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: /* 2ba3bf09a0 2013-05-11 kinaba: CASE(6) 2ba3bf09a0 2013-05-11 kinaba: string friendship_[] = ; 2ba3bf09a0 2013-05-11 kinaba: vector <string> friendship(friendship_, friendship_+sizeof(friendship_)/sizeof(*friendship_)); 2ba3bf09a0 2013-05-11 kinaba: int _ = ; 2ba3bf09a0 2013-05-11 kinaba: END 2ba3bf09a0 2013-05-11 kinaba: */ 2ba3bf09a0 2013-05-11 kinaba: } 2ba3bf09a0 2013-05-11 kinaba: // END CUT HERE