fec4e3c3ed 2012-08-06 kinaba: #include <iostream> fec4e3c3ed 2012-08-06 kinaba: #include <sstream> fec4e3c3ed 2012-08-06 kinaba: #include <iomanip> fec4e3c3ed 2012-08-06 kinaba: #include <vector> fec4e3c3ed 2012-08-06 kinaba: #include <string> fec4e3c3ed 2012-08-06 kinaba: #include <map> fec4e3c3ed 2012-08-06 kinaba: #include <set> fec4e3c3ed 2012-08-06 kinaba: #include <algorithm> fec4e3c3ed 2012-08-06 kinaba: #include <numeric> fec4e3c3ed 2012-08-06 kinaba: #include <iterator> fec4e3c3ed 2012-08-06 kinaba: #include <functional> fec4e3c3ed 2012-08-06 kinaba: #include <complex> fec4e3c3ed 2012-08-06 kinaba: #include <queue> fec4e3c3ed 2012-08-06 kinaba: #include <stack> fec4e3c3ed 2012-08-06 kinaba: #include <cmath> fec4e3c3ed 2012-08-06 kinaba: #include <cassert> fec4e3c3ed 2012-08-06 kinaba: using namespace std; fec4e3c3ed 2012-08-06 kinaba: typedef long long LL; fec4e3c3ed 2012-08-06 kinaba: typedef long double LD; fec4e3c3ed 2012-08-06 kinaba: typedef complex<LD> CMP; fec4e3c3ed 2012-08-06 kinaba: fec4e3c3ed 2012-08-06 kinaba: class ColorfulChocolates { public: fec4e3c3ed 2012-08-06 kinaba: int maximumSpread(string chocolates, int maxSwaps) fec4e3c3ed 2012-08-06 kinaba: { fec4e3c3ed 2012-08-06 kinaba: int N = chocolates.size(); fec4e3c3ed 2012-08-06 kinaba: chocolates += '$'; fec4e3c3ed 2012-08-06 kinaba: int best = 0; fec4e3c3ed 2012-08-06 kinaba: for(int s=0; s<N; ++s) fec4e3c3ed 2012-08-06 kinaba: for(int e=s+1; e<=N; ++e) fec4e3c3ed 2012-08-06 kinaba: for(char c='A'; c<='Z'; ++c) fec4e3c3ed 2012-08-06 kinaba: if( can(chocolates, c, s, e, maxSwaps) ) fec4e3c3ed 2012-08-06 kinaba: best = max(best, count(chocolates.begin()+s, chocolates.begin()+e, c)); fec4e3c3ed 2012-08-06 kinaba: return best; fec4e3c3ed 2012-08-06 kinaba: } fec4e3c3ed 2012-08-06 kinaba: fec4e3c3ed 2012-08-06 kinaba: bool can(const string& choco, char c, int s, int e, int k) fec4e3c3ed 2012-08-06 kinaba: { fec4e3c3ed 2012-08-06 kinaba: vector<int> z; fec4e3c3ed 2012-08-06 kinaba: for(;;) { fec4e3c3ed 2012-08-06 kinaba: int i = choco.find(c, s); fec4e3c3ed 2012-08-06 kinaba: if(i>=e || i==string::npos) fec4e3c3ed 2012-08-06 kinaba: i = e; fec4e3c3ed 2012-08-06 kinaba: fec4e3c3ed 2012-08-06 kinaba: z.push_back(i-s); fec4e3c3ed 2012-08-06 kinaba: if( i == e ) fec4e3c3ed 2012-08-06 kinaba: break; fec4e3c3ed 2012-08-06 kinaba: s = i+1; fec4e3c3ed 2012-08-06 kinaba: } fec4e3c3ed 2012-08-06 kinaba: int needSwap = 0; fec4e3c3ed 2012-08-06 kinaba: for(int i=0; i<z.size(); ++i) fec4e3c3ed 2012-08-06 kinaba: needSwap += z[i] * min<int>(i, z.size()-1-i); fec4e3c3ed 2012-08-06 kinaba: return needSwap <= k; fec4e3c3ed 2012-08-06 kinaba: } fec4e3c3ed 2012-08-06 kinaba: }; fec4e3c3ed 2012-08-06 kinaba: fec4e3c3ed 2012-08-06 kinaba: // BEGIN CUT HERE fec4e3c3ed 2012-08-06 kinaba: #include <ctime> fec4e3c3ed 2012-08-06 kinaba: double start_time; string timer() fec4e3c3ed 2012-08-06 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } fec4e3c3ed 2012-08-06 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) fec4e3c3ed 2012-08-06 kinaba: { os << "{ "; fec4e3c3ed 2012-08-06 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) fec4e3c3ed 2012-08-06 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } fec4e3c3ed 2012-08-06 kinaba: void verify_case(const int& Expected, const int& Received) { fec4e3c3ed 2012-08-06 kinaba: bool ok = (Expected == Received); fec4e3c3ed 2012-08-06 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; fec4e3c3ed 2012-08-06 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } fec4e3c3ed 2012-08-06 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); fec4e3c3ed 2012-08-06 kinaba: #define END verify_case(_, ColorfulChocolates().maximumSpread(chocolates, maxSwaps));} fec4e3c3ed 2012-08-06 kinaba: int main(){ fec4e3c3ed 2012-08-06 kinaba: fec4e3c3ed 2012-08-06 kinaba: CASE(0) fec4e3c3ed 2012-08-06 kinaba: string chocolates = "ABCDCBC"; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = 1; fec4e3c3ed 2012-08-06 kinaba: int _ = 2; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: CASE(1) fec4e3c3ed 2012-08-06 kinaba: string chocolates = "ABCDCBC"; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = 2; fec4e3c3ed 2012-08-06 kinaba: int _ = 3; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: CASE(2) fec4e3c3ed 2012-08-06 kinaba: string chocolates = "ABBABABBA"; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = 3; fec4e3c3ed 2012-08-06 kinaba: int _ = 4; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: CASE(3) fec4e3c3ed 2012-08-06 kinaba: string chocolates = "ABBABABBA"; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = 4; fec4e3c3ed 2012-08-06 kinaba: int _ = 5; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: CASE(4) fec4e3c3ed 2012-08-06 kinaba: string chocolates = "QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO"; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = 77; fec4e3c3ed 2012-08-06 kinaba: int _ = 5; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: CASE(5) fec4e3c3ed 2012-08-06 kinaba: string chocolates = "ABCDEBC"; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = 1; fec4e3c3ed 2012-08-06 kinaba: int _ = 1; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: /* fec4e3c3ed 2012-08-06 kinaba: CASE(6) fec4e3c3ed 2012-08-06 kinaba: string chocolates = ; fec4e3c3ed 2012-08-06 kinaba: int maxSwaps = ; fec4e3c3ed 2012-08-06 kinaba: int _ = ; fec4e3c3ed 2012-08-06 kinaba: END fec4e3c3ed 2012-08-06 kinaba: */ fec4e3c3ed 2012-08-06 kinaba: } fec4e3c3ed 2012-08-06 kinaba: // END CUT HERE