26aa079da8 2015-01-02 kinaba: #include <iostream> 26aa079da8 2015-01-02 kinaba: #include <sstream> 26aa079da8 2015-01-02 kinaba: #include <iomanip> 26aa079da8 2015-01-02 kinaba: #include <vector> 26aa079da8 2015-01-02 kinaba: #include <string> 26aa079da8 2015-01-02 kinaba: #include <map> 26aa079da8 2015-01-02 kinaba: #include <set> 26aa079da8 2015-01-02 kinaba: #include <algorithm> 26aa079da8 2015-01-02 kinaba: #include <numeric> 26aa079da8 2015-01-02 kinaba: #include <iterator> 26aa079da8 2015-01-02 kinaba: #include <functional> 26aa079da8 2015-01-02 kinaba: #include <complex> 26aa079da8 2015-01-02 kinaba: #include <queue> 26aa079da8 2015-01-02 kinaba: #include <stack> 26aa079da8 2015-01-02 kinaba: #include <cmath> 26aa079da8 2015-01-02 kinaba: #include <cassert> 26aa079da8 2015-01-02 kinaba: #include <tuple> 26aa079da8 2015-01-02 kinaba: using namespace std; 26aa079da8 2015-01-02 kinaba: typedef long long LL; 26aa079da8 2015-01-02 kinaba: typedef complex<double> CMP; 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: enum {HH, HS, SH, SS}; 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: class TheKingsArmyDiv1 { public: 26aa079da8 2015-01-02 kinaba: int getNumber(vector <string> state) 26aa079da8 2015-01-02 kinaba: { 26aa079da8 2015-01-02 kinaba: const int N = state[0].size(); 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: vector<int> s; 26aa079da8 2015-01-02 kinaba: for(int i=0; i<N; ++i) 26aa079da8 2015-01-02 kinaba: s.push_back((state[0][i]=='S')*2 + (state[1][i]=='S')); 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: const int nSS = count(s.begin(), s.end(), SS); 26aa079da8 2015-01-02 kinaba: if(nSS == N) 26aa079da8 2015-01-02 kinaba: return -1; 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: vector<vector<int>> blocks; 26aa079da8 2015-01-02 kinaba: for(int i=0; i<N; ) { 26aa079da8 2015-01-02 kinaba: while(i<N && s[i]==SS) ++i; 26aa079da8 2015-01-02 kinaba: if(i<N) { 26aa079da8 2015-01-02 kinaba: blocks.emplace_back(); 26aa079da8 2015-01-02 kinaba: while(i<N && s[i]!=SS) { 26aa079da8 2015-01-02 kinaba: if(s[i] != HH) 26aa079da8 2015-01-02 kinaba: blocks.back().push_back(s[i]); 26aa079da8 2015-01-02 kinaba: ++i; 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: if(blocks.back().empty()) 26aa079da8 2015-01-02 kinaba: blocks.pop_back(); 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: int c1=0, c2=0; 26aa079da8 2015-01-02 kinaba: for(auto& bl: blocks) { 26aa079da8 2015-01-02 kinaba: c1 += align_cost(bl, HS); 26aa079da8 2015-01-02 kinaba: c2 += align_cost(bl, SH); 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: return nSS + (blocks.empty() ? 0 : min(c1, c2)+1); 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: int align_cost(const vector<int>& b, int type) 26aa079da8 2015-01-02 kinaba: { 26aa079da8 2015-01-02 kinaba: int cost = 0; 26aa079da8 2015-01-02 kinaba: for(int i=0; i<b.size(); ) { 26aa079da8 2015-01-02 kinaba: while(i<b.size() && b[i]==type) ++i; 26aa079da8 2015-01-02 kinaba: if(i<b.size()) { 26aa079da8 2015-01-02 kinaba: while(i<b.size() && b[i]!=type) ++i; 26aa079da8 2015-01-02 kinaba: ++cost; 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: return cost; 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: }; 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: // BEGIN CUT HERE 26aa079da8 2015-01-02 kinaba: #include <ctime> 26aa079da8 2015-01-02 kinaba: double start_time; string timer() 26aa079da8 2015-01-02 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 26aa079da8 2015-01-02 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 26aa079da8 2015-01-02 kinaba: { os << "{ "; 26aa079da8 2015-01-02 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 26aa079da8 2015-01-02 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 26aa079da8 2015-01-02 kinaba: void verify_case(const int& Expected, const int& Received) { 26aa079da8 2015-01-02 kinaba: bool ok = (Expected == Received); 26aa079da8 2015-01-02 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 26aa079da8 2015-01-02 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 26aa079da8 2015-01-02 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 26aa079da8 2015-01-02 kinaba: #define END verify_case(_, TheKingsArmyDiv1().getNumber(state));} 26aa079da8 2015-01-02 kinaba: int main(){ 26aa079da8 2015-01-02 kinaba: 26aa079da8 2015-01-02 kinaba: CASE(0) 26aa079da8 2015-01-02 kinaba: string state_[] = {"HSH", 26aa079da8 2015-01-02 kinaba: "SHS"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = 2; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: CASE(1) 26aa079da8 2015-01-02 kinaba: string state_[] = {"HH", 26aa079da8 2015-01-02 kinaba: "HH"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = 0; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: CASE(2) 26aa079da8 2015-01-02 kinaba: string state_[] = {"HHHHH", 26aa079da8 2015-01-02 kinaba: "HSHSH"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = 1; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: CASE(3) 26aa079da8 2015-01-02 kinaba: string state_[] = {"S", 26aa079da8 2015-01-02 kinaba: "S"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = -1; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: CASE(4) 26aa079da8 2015-01-02 kinaba: string state_[] = {"HSHHSHSHSHHHSHSHSH", 26aa079da8 2015-01-02 kinaba: "SSSSHSSHSHSHHSSSSH"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = 8; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: CASE(5) 26aa079da8 2015-01-02 kinaba: string state_[] = {"HS", 26aa079da8 2015-01-02 kinaba: "HS"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = 1; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: CASE(6) 26aa079da8 2015-01-02 kinaba: string state_[] = {"HHH", "SSS"}; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = 1; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: /* 26aa079da8 2015-01-02 kinaba: CASE(7) 26aa079da8 2015-01-02 kinaba: string state_[] = ; 26aa079da8 2015-01-02 kinaba: vector <string> state(state_, state_+sizeof(state_)/sizeof(*state_)); 26aa079da8 2015-01-02 kinaba: int _ = ; 26aa079da8 2015-01-02 kinaba: END 26aa079da8 2015-01-02 kinaba: */ 26aa079da8 2015-01-02 kinaba: } 26aa079da8 2015-01-02 kinaba: // END CUT HERE