724e2f81fd 2017-02-09 kinaba: #include <iostream> 724e2f81fd 2017-02-09 kinaba: #include <sstream> 724e2f81fd 2017-02-09 kinaba: #include <iomanip> 724e2f81fd 2017-02-09 kinaba: #include <vector> 724e2f81fd 2017-02-09 kinaba: #include <string> 724e2f81fd 2017-02-09 kinaba: #include <map> 724e2f81fd 2017-02-09 kinaba: #include <set> 724e2f81fd 2017-02-09 kinaba: #include <algorithm> 724e2f81fd 2017-02-09 kinaba: #include <numeric> 724e2f81fd 2017-02-09 kinaba: #include <iterator> 724e2f81fd 2017-02-09 kinaba: #include <functional> 724e2f81fd 2017-02-09 kinaba: #include <complex> 724e2f81fd 2017-02-09 kinaba: #include <queue> 724e2f81fd 2017-02-09 kinaba: #include <stack> 724e2f81fd 2017-02-09 kinaba: #include <cmath> 724e2f81fd 2017-02-09 kinaba: #include <cassert> 724e2f81fd 2017-02-09 kinaba: #include <tuple> 724e2f81fd 2017-02-09 kinaba: using namespace std; 724e2f81fd 2017-02-09 kinaba: typedef long long LL; 724e2f81fd 2017-02-09 kinaba: typedef complex<double> CMP; 724e2f81fd 2017-02-09 kinaba: 724e2f81fd 2017-02-09 kinaba: class BalancedStrings { public: 724e2f81fd 2017-02-09 kinaba: vector <string> findAny(int N) 724e2f81fd 2017-02-09 kinaba: { 724e2f81fd 2017-02-09 kinaba: return solve(N); 724e2f81fd 2017-02-09 kinaba: } 724e2f81fd 2017-02-09 kinaba: 724e2f81fd 2017-02-09 kinaba: int sim(const vector<string>& S) { 724e2f81fd 2017-02-09 kinaba: int cnt = 0; 724e2f81fd 2017-02-09 kinaba: for (int i = 0; i < S.size(); ++i) 724e2f81fd 2017-02-09 kinaba: for (int k = i + 1; k < S.size(); ++k) 724e2f81fd 2017-02-09 kinaba: for (char c1 : S[i]) 724e2f81fd 2017-02-09 kinaba: for (char c2 : S[k]) 724e2f81fd 2017-02-09 kinaba: if (c1 == c2) 724e2f81fd 2017-02-09 kinaba: ++cnt; 724e2f81fd 2017-02-09 kinaba: return cnt; 724e2f81fd 2017-02-09 kinaba: } 724e2f81fd 2017-02-09 kinaba: 724e2f81fd 2017-02-09 kinaba: vector<string> solve(int N) 724e2f81fd 2017-02-09 kinaba: { 724e2f81fd 2017-02-09 kinaba: if (N <= 26) { 724e2f81fd 2017-02-09 kinaba: vector<string> ans; 724e2f81fd 2017-02-09 kinaba: for (int i = 0; i < N; ++i) 724e2f81fd 2017-02-09 kinaba: ans.push_back(string(1, 'a' + i)); 724e2f81fd 2017-02-09 kinaba: return ans; 724e2f81fd 2017-02-09 kinaba: } 724e2f81fd 2017-02-09 kinaba: 724e2f81fd 2017-02-09 kinaba: vector<string> ans; 724e2f81fd 2017-02-09 kinaba: for (int i = 0; i < N-2; ++i) 724e2f81fd 2017-02-09 kinaba: ans.push_back(string(1, 'e' + i%20)); 724e2f81fd 2017-02-09 kinaba: int s = sim(ans); 724e2f81fd 2017-02-09 kinaba: string a = "b"; 724e2f81fd 2017-02-09 kinaba: string c = "d"; 724e2f81fd 2017-02-09 kinaba: while (s && a.size() < 100) a += (a.back()=='a' ? 'b' : 'a'), --s; 724e2f81fd 2017-02-09 kinaba: while (s && c.size() < 100) c += (c.back()=='c' ? 'd' : 'c'), --s; 724e2f81fd 2017-02-09 kinaba: ans.push_back(a); 724e2f81fd 2017-02-09 kinaba: ans.push_back(c); 724e2f81fd 2017-02-09 kinaba: return ans; 724e2f81fd 2017-02-09 kinaba: } 724e2f81fd 2017-02-09 kinaba: }; 724e2f81fd 2017-02-09 kinaba: 724e2f81fd 2017-02-09 kinaba: // BEGIN CUT HERE 724e2f81fd 2017-02-09 kinaba: #include <ctime> 724e2f81fd 2017-02-09 kinaba: double start_time; string timer() 724e2f81fd 2017-02-09 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 724e2f81fd 2017-02-09 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 724e2f81fd 2017-02-09 kinaba: { os << "{ "; 724e2f81fd 2017-02-09 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 724e2f81fd 2017-02-09 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 724e2f81fd 2017-02-09 kinaba: void verify_case(const vector <string>& Expected, const vector <string>& Received) { 724e2f81fd 2017-02-09 kinaba: bool ok = (Expected == Received); 724e2f81fd 2017-02-09 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 724e2f81fd 2017-02-09 kinaba: cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 724e2f81fd 2017-02-09 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 724e2f81fd 2017-02-09 kinaba: #define END verify_case(_, BalancedStrings().findAny(N));} 724e2f81fd 2017-02-09 kinaba: int main(){ 724e2f81fd 2017-02-09 kinaba: 724e2f81fd 2017-02-09 kinaba: CASE(0) 724e2f81fd 2017-02-09 kinaba: int N = 3; 724e2f81fd 2017-02-09 kinaba: string __[] = {"eertree", "topcoder", "arena" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: CASE(1) 724e2f81fd 2017-02-09 kinaba: int N = 4; 724e2f81fd 2017-02-09 kinaba: string __[] = {"hello", "little", "polar", "bear" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: CASE(2) 724e2f81fd 2017-02-09 kinaba: int N = 5; 724e2f81fd 2017-02-09 kinaba: string __[] = {"abbbbbbbbbbbbczaaaaaao", "c", "zz", "c", "xxxyyyzvvv" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: CASE(3) 724e2f81fd 2017-02-09 kinaba: int N = 1; 724e2f81fd 2017-02-09 kinaba: string __[] = {"kkkkkkkkkkkkkkkkkkk" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: CASE(4) 724e2f81fd 2017-02-09 kinaba: int N = 10; 724e2f81fd 2017-02-09 kinaba: string __[] = {"asdflkjhsdfsfffkdhjfdlshlfds", "pudelek", "xo", "xo", "mnbvmnmbbr", "plox", "qqwwrrttyyy", "you", "are", "awesome" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: CASE(5) 724e2f81fd 2017-02-09 kinaba: int N = 100; 724e2f81fd 2017-02-09 kinaba: string __[] = { "" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: CASE(6) 724e2f81fd 2017-02-09 kinaba: int N = 40; 724e2f81fd 2017-02-09 kinaba: string __[] = { "" }; 724e2f81fd 2017-02-09 kinaba: vector <string> _(__, __+sizeof(__)/sizeof(*__)); 724e2f81fd 2017-02-09 kinaba: END 724e2f81fd 2017-02-09 kinaba: } 724e2f81fd 2017-02-09 kinaba: // END CUT HERE