ADDED SRM/TCO14-1B/1A.cpp Index: SRM/TCO14-1B/1A.cpp ================================================================== --- SRM/TCO14-1B/1A.cpp +++ SRM/TCO14-1B/1A.cpp @@ -0,0 +1,105 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class SpamChecker { public: + string spamCheck(string judgeLog, int good, int bad) + { + return isBad(judgeLog, good, bad) ? "SPAM" : "NOT SPAM"; + } + + bool isBad(string judgeLog, int good, int bad) + { + int score = 0; + for(char c: judgeLog) + if((score += c=='o' ? good : -bad) < 0) + return true; + return false; + } +}; + +// 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 string& Expected, const string& 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(_, SpamChecker().spamCheck(judgeLog, good, bad));} +int main(){ + +CASE(0) + string judgeLog = "ooooxxxo"; + int good = 2; + int bad = 3; + string _ = "SPAM"; +END +CASE(1) + string judgeLog = "ooooxxxo"; + int good = 3; + int bad = 4; + string _ = "NOT SPAM"; +END +CASE(2) + string judgeLog = "xooooooooooooooooooooooooooo"; + int good = 1000; + int bad = 1; + string _ = "SPAM"; +END +CASE(3) + string judgeLog = "oxxxxxxxxxxxxxxxxxxxxxxxxxxxx"; + int good = 1000; + int bad = 1; + string _ = "NOT SPAM"; +END +CASE(4) + string judgeLog = "ooxoxoxooxoxxoxoxooxoxoxoxxoxx"; + int good = 15; + int bad = 17; + string _ = "SPAM"; +END +CASE(5) + string judgeLog = "oooxoxoxoxoxoxooxooxoxooxo"; + int good = 16; + int bad = 18; + string _ = "NOT SPAM"; +END +/* +CASE(6) + string judgeLog = ; + int good = ; + int bad = ; + string _ = ; +END +CASE(7) + string judgeLog = ; + int good = ; + int bad = ; + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO14-1B/1B.cpp Index: SRM/TCO14-1B/1B.cpp ================================================================== --- SRM/TCO14-1B/1B.cpp +++ SRM/TCO14-1B/1B.cpp @@ -0,0 +1,178 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +int bitcnt(int x) +{ + int c = 0; + for(; x; x>>=1) + c += x&1; + return c; +} + +class WolvesAndSheep { public: + int getmin(vector field) + { + int H = field.size(); + int W = field[0].size(); + int best = W*H; + for(int mask=0; mask<(1<<(W-1)); ++mask) + { + vector>> sw(H); + for(int y=0; y> cur(WW); + for(int y=0; y +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(_, WolvesAndSheep().getmin(field));} +int main(){ + +CASE(0) + string field_[] = {"W.WSS", + "WW.S.", + ".SSS.", + "SSS.S", + ".SS.S"}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 2; +END +CASE(1) + string field_[] = {".....", + ".....", + "....."}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 0; +END +CASE(2) + string field_[] = {".SS", + "...", + "S..", + "W.W"}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 1; +END +CASE(3) + string field_[] = {"WWWSWWSSWWW", + "WWSWW.SSWWW", + "WS.WSWWWWS."}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 10; +END +CASE(4) + string field_[] = {".W.S.W.W", + "W.W.S.W.", + ".S.S.W.W", + "S.S.S.W.", + ".S.W.W.S", + "S.S.W.W.", + ".W.W.W.S", + "W.W.S.S."}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 7; +END +CASE(5) + string field_[] = {"W.SSWWSSSW.SS", + ".SSSSW.SSWWWW", + ".WWWWS.WSSWWS", + "SS.WSS..W.WWS", + "WSSS.SSWS.W.S", + "WSS.WS...WWWS", + "S.WW.S.SWWWSW", + "WSSSS.SSW...S", + "S.WWSW.WWSWSW", + ".WSSS.WWSWWWS", + "..SSSS.WWWSSS", + "SSWSWWS.W.SSW", + "S.WSWS..WSSS.", + "WS....W..WSS."}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 24; +END +CASE(6) + string field_[] = {"WW..SS", + "WW..SS", + "......", + "......", + "SS..WW", + "SS..WW"}; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = 2; +END +/* +CASE(7) + string field_[] = ; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = ; +END +CASE(8) + string field_[] = ; + vector field(field_, field_+sizeof(field_)/sizeof(*field_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO14-1B/1C.cpp Index: SRM/TCO14-1B/1C.cpp ================================================================== --- SRM/TCO14-1B/1C.cpp +++ SRM/TCO14-1B/1C.cpp @@ -0,0 +1,131 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +double C(int n, int k) +{ + k = min(n-k, k); + double t = 1; + for(int i=1; i<=k; ++i) + t = t * (n-i+1) / i; + return t; +} + +class EagleInZoo { public: + double calc(vector parent, int K) + { + int N = parent.size() + 1; + vector> child(N); + for(int i=1; i,double> memo; + double rec(const vector>& child, int v, int K) + { + if(K == 1) + return 1.0; + if(child[v].empty()) + return 0.0; + pair key(v, K); + if(memo.count(key)) return memo[key]; + + double ans = 0.0; + for(int u: child[v]) // When K-the eagle goes to |u|. + for(int uN=0; uN<=K-2; ++uN) // When uN out of K-2 previous eagles went to |u|. + { + ans += C(K-2, uN) + * pow(1.0/child[v].size(), uN) + * pow(1.0-1.0/child[v].size(), K-2-uN) + * rec(child, u, uN+1); + } + return memo[key] = ans / child[v].size(); + } +}; + +// 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 double& Expected, const double& Received) { + bool ok = (abs(Expected - Received) < 1e-9); + 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(_, EagleInZoo().calc(parent, K));} +int main(){ + +CASE(0) + int parent_[] = {0,0}; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = 2; + double _ = 1.0; +END +CASE(1) + int parent_[] = {0,0}; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = 3; + double _ = 0.5; +END +CASE(2) + int parent_[] = {0,1,0,3}; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = 4; + double _ = 0.75; +END +CASE(3) + int parent_[] = {0,0,1,1,2,4,4,4,5,5,6,6}; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = 20; + double _ = 0.14595168754091617; +END +CASE(4) + int parent_[] = {0,1,2,3,2,1,1,7,0,9,10,11,12,13,14,15,16,17,18,14,9}; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = 24; + double _ = 0.3272154791654077; +END +CASE(5) + int parent_[] = {0,1,2,3,4,5,6,7,8,9,10}; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = 50; + double _ = 0.0; +END +/* +CASE(6) + int parent_[] = ; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = ; + double _ = ; +END +CASE(7) + int parent_[] = ; + vector parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); + int K = ; + double _ = ; +END +*/ +} +// END CUT HERE