ADDED SRM/TCO12-1/1A.cpp Index: SRM/TCO12-1/1A.cpp ================================================================== --- SRM/TCO12-1/1A.cpp +++ SRM/TCO12-1/1A.cpp @@ -0,0 +1,118 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +class EllysJuice { public: + vector getWinners(vector players) + { + set winners; + + sort(players.begin(), players.end()); + do + winners.insert( play(players) ); + while( next_permutation(players.begin(), players.end()) ); + + winners.erase(""); + return vector(winners.begin(), winners.end()); + } + + string play(const vector& p) + { + int juice[2] = {65536, 65536}; + map total; + for(int i=0; i::iterator it=total.begin(); it!=total.end(); ++it) + if( it->second > best ) { + best_name = it->first; + best = it->second; + tie = false; + } + else if( it->second == best ) + tie = true; + return tie ? "" : best_name; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const vector & Expected, const vector & Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, EllysJuice().getWinners(players));} +int main(){ + +CASE(0) + string players_[] = { "elly", "kriss", "stancho", "elly", "stancho" }; + vector players(players_, players_+sizeof(players_)/sizeof(*players_)); + string __[] = {"elly", "stancho" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + string players_[] = {"torb", "elly", "stancho", "kriss"}; + vector players(players_, players_+sizeof(players_)/sizeof(*players_)); + vector _; +END +CASE(2) + string players_[] = {"elly", "elly", "elly", "elly", "elly"}; + vector players(players_, players_+sizeof(players_)/sizeof(*players_)); + string __[] = {"elly" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + string players_[] = { "ariadne", "elly", "ariadne", "stancho", "stancho", "kriss", "stancho", "elly" }; + vector players(players_, players_+sizeof(players_)/sizeof(*players_)); + string __[] = {"ariadne", "elly", "stancho" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + string players_[] = {"b","b","a","a"}; + vector players(players_, players_+sizeof(players_)/sizeof(*players_)); + string __[] = {"a","b"}; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(5) + string players_[] = ; + vector players(players_, players_+sizeof(players_)/sizeof(*players_)); + string __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE ADDED SRM/TCO12-1/1B.cpp Index: SRM/TCO12-1/1B.cpp ================================================================== --- SRM/TCO12-1/1B.cpp +++ SRM/TCO12-1/1B.cpp @@ -0,0 +1,103 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +class EllysFractions { public: + long long getCount(int N) + { + LL total = 0; + for(int k=2; k<=N; ++k) + total += getExact(k); + return total; + } + + LL getExact(int N) + { + int np = 0; + for(int p=2; p<=N; ++p) + if(is_prime(p)) + ++np; + LL v = 1; + for(int i=0; i +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const long long& Expected, const long long& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, EllysFractions().getCount(N));} +int main(){ + +CASE(0) + int N = 1; + long long _ = 0LL; +END +CASE(1) + int N = 2; + long long _ = 1LL; +END +CASE(2) + int N = 3; + long long _ = 3LL; +END +CASE(3) + int N = 5; + long long _ = 9LL; +END +CASE(4) + int N = 100; + long long _ = 177431885LL; +END +CASE(5) + int N = 250; + long long _ = -1LL; +END +CASE(6) + int N = 4; + long long _ = 5LL; +END +} +// END CUT HERE ADDED SRM/TCO12-1/1C.cpp Index: SRM/TCO12-1/1C.cpp ================================================================== --- SRM/TCO12-1/1C.cpp +++ SRM/TCO12-1/1C.cpp @@ -0,0 +1,273 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +struct UnionFind +{ + vector uf, sz; + int nc; + + UnionFind(int N): uf(N), sz(N,1), nc(N) + { for(int i=0; i= sz[b] ) swap(a, b); + uf[a] = b; + sz[b] += sz[a]; + --nc; + } + return (a!=b); + } +}; + +class EllysLights { public: + int getMinimum(string initial, vector switches) + { + int N = switches.size(); + UnionFind uf(N*2+2); + #define TR 0 + #define FL 1 + #define POS(x) ((x)+2) + #define NEG(x) ((x)+N+2) + + for(int i=0; i sw; + for(int k=0; k done; + for(int k=0; k pos(1, k); + vector neg; + for(int j=k+1; j +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, EllysLights().getMinimum(initial, switches));} +int main(){ + +CASE(0) + string initial = "YNYNNN"; + string switches_[] = {"YNNYNY", "NYYYNN", "YNYNYN", "NNNNYN", "NYNNNY"}; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = 2; +END +CASE(1) + string initial = "YNYNYN"; + string switches_[] = {"NNNNNN", "YYYYYY", "NYNNNN", "NNNYNN", "NNNNNY"}; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = 4; +END +CASE(2) + string initial = "YYN"; + string switches_[] = {"YNY", "NYN"}; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = -1; +END +CASE(3) + string initial = "NNYNYNYYYNNYYYYN"; + string switches_[] = {"NYNYNYNYNYNYNYNY", + "YNYNYNYNYNYNYNYN", + "NNNNNNNNNNNNNNNN", + "YNNNNNNNNNNNNNNN", + "NYNNNNNNNNNNNNNN", + "NNYNNNNNNNNNNNNN", + "NNNYNNNNNNNNNNNN", + "NNNNYNNNNNNNNNNN", + "NNNNNYNNNNNNNNNN", + "NNNNNNYNNNNNNNNN", + "NNNNNNNYNNNNNNNN", + "NNNNNNNNYNNNNNNN", + "NNNNNNNNNYNNNNNN", + "NNNNNNNNNNYNNNNN", + "NNNNNNNNNNNYNNNN", + "NNNNNNNNNNNNYNNN", + "NNNNNNNNNNNNNYNN", + "NNNNNNNNNNNNNNYN", + "NNNNNNNNNNNNNNNY"}; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = 6; +END +CASE(4) + string initial = "NYNYNYYYNNYYYNNYNNYYYYYNNYNYYYY"; + string switches_[] = {"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", + "NNNNNNNNYNNNYNNNNYYNYNNNNYNNNNN", + "NNNNNNNNNYNNNNNNNNNNNNYNNNNNNNN", + "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN", + "NYNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNYYNNNNNNNNNNNNNNNY", + "NNNNNNYNNNNNNNNNNNNYNNNNNYNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "YNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN", + "NNNYNNNNNNNNNNNNNNNNNNNYYNNNNNN", + "NYNNNNNNNNNNYNNNNNNNNNNNNNNNYNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNY", + "NNNNNNNNNNYNNNNNNNNNYYYNNNNNNNN", + "NNNYNNNNNNNNNNNNNNNNNNNNNNNYNNN", + "NNNNNNNNYNNNNNNNNNNNNNNNYNNNNNN", + "YNNNYNNNNNNNNNNNNNNNNNNNNNNYNNN", + "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN", + "NNNNYNNYNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNYNNNYNNNYNNNNNNNNNNNNNYN"}; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = 7; +END +CASE(5) + string initial = "NYNYYNYNYYYYNNYNYNNYYNNNNNYNYNNNNNYNNNYN"; + string switches_[] = {"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNN", + "NNNNNNNNNYNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNYNNNNYNNNNNNNYNNNNNNN", + "NNNNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNYNNNNNYNN", + "NNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNYNNYNNNNN", + "NNNNNYNNYNNYNNNNNNNNNNNNNNNNNNNNNYNNNNNN", + "YNNNYNNNNNNNNNNNNNYNNNYNNYNNNNNNNYNNNNNN", + "NNNNNNNNNYYNNNNNNNNNNNNYNNNNYNNNNNNNNNNN", + "NNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNY", + "NNNNNNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNN", + "NNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN", + "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNY", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNYNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNN", + "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNN", + "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNN", + "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NYNNNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", + "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", + "NNNNNNNNNNNNYNNYYNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNYNNNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNN", + "NNNNNNNNYNNNNNNNNNNNNNNNNNNNYNYNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNYNNN"}; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = -1; +END +/* +CASE(6) + string initial = ; + string switches_[] = ; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = ; +END +CASE(7) + string initial = ; + string switches_[] = ; + vector switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_)); + int _ = ; +END +*/ +} +// END CUT HERE