ADDED SRM/526-U/2A.cpp Index: SRM/526-U/2A.cpp ================================================================== --- SRM/526-U/2A.cpp +++ SRM/526-U/2A.cpp @@ -0,0 +1,98 @@ +#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 CheatingQuiz { public: + vector howMany(string answers) + { + int N = answers.size(); + vector re; + int A = count(answers.begin(), answers.end(), 'A'); + int B = count(answers.begin(), answers.end(), 'B'); + int C = count(answers.begin(), answers.end(), 'C'); + 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 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(_, CheatingQuiz().howMany(answers));} +int main(){ + +CASE(0) + string answers = "AAAAA"; + int __[] = {1, 1, 1, 1, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + string answers = "AAABBB"; + int __[] = {2, 2, 2, 1, 1, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + string answers = "CAAAAAC"; + int __[] = {2, 2, 2, 2, 2, 2, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + string answers = "BBCA"; + int __[] = {3, 3, 2, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + string answers = "BACACABCBBBBCAAAAACCCABBCAA"; + int __[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(5) + string answers = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(6) + string answers = ; + int __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE ADDED SRM/527-U/1A.cpp Index: SRM/527-U/1A.cpp ================================================================== --- SRM/527-U/1A.cpp +++ SRM/527-U/1A.cpp @@ -0,0 +1,110 @@ +#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 P8XGraphBuilder { public: + int solve(vector scores) + { + scores.insert(scores.begin(), 9999999); + const int N = scores.size(); + + int best = 0; + for(int leaves=1; leaves,int> memo; + int calc(int leaves, int nodes, const vector& scores) + { + if( nodes == 1 ) + return scores[leaves]; + + pair key(leaves, nodes); + if( memo.count(key) ) + return memo[key]; + + int best = 0; + for(int k=1; k<=leaves; ++k) + best = max(best, scores[k+1] + calc(leaves-k+1, nodes-1, scores)); + return memo[key] = best; + } +}; + +// 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 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(_, P8XGraphBuilder().solve(scores));} +int main(){ + +CASE(0) + int scores_[] = {1, 3, 0}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = 8; +END +CASE(1) + int scores_[] = {0, 0, 0, 10}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = 10; +END +CASE(2) + int scores_[] = {1, 2, 3, 4, 5, 6}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = 12; +END +CASE(3) + int scores_[] = {5, 0, 0}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = 15; +END +CASE(4) + int scores_[] = {1, 3, 2, 5, 3, 7, 5}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = 20; +END +CASE(5) +int scores_[] = {1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = -1; +END +CASE(6) + int scores_[] = {2}; + vector scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_)); + int _ = 4; +END + +} +// END CUT HERE ADDED SRM/527-U/1B.cpp Index: SRM/527-U/1B.cpp ================================================================== --- SRM/527-U/1B.cpp +++ SRM/527-U/1B.cpp @@ -0,0 +1,256 @@ +#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; + +typedef int vert; +typedef vert edge; +typedef vector edges; +typedef vector graph; + +bool augment( graph& G, int v, vector& matchTo, bool visited[] ) +{ + for(int i=0; i +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right + // only left->right edges are used during computation +{ + vector matchTo(G.size(), -1); + int ans = 0; + for(vert v=0; v solve(vector rows, vector columns) + { + H = rows.size(); + W = rows[0].size(); + for(int y=0; y& rows, const vector& columns) + { + graph G(W*2); + for(int x1=0; x1(G, W) == W; + } + + bool match( const string& l, const string& r ) + { + 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 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(_, P8XMatrixRecovery().solve(rows, columns));} +int main(){ + +CASE(0) + string rows_[] = {"10?" +,"?11"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"01" +,"10" +,"1?"} +; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"101", "011" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + string rows_[] = {"0" +,"?" +,"1"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"0?1"}; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"0", "0", "1" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + string rows_[] = {"10" +,"01"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"10" +,"01"}; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"10", "01" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + string rows_[] = {"??0" +,"11?" +,"?01" +,"1?1"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"1???" +,"?111" +,"0?1?"}; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"010", "110", "101", "101" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + string rows_[] = { + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + }; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = { + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + "??????????????????????????????", + }; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"?"}; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) +string rows_[] = {"?"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"?"}; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"0"}; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(6) + string rows_[] = {"??","??"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"00","11"}; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"01","01"}; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(7) + string rows_[] = {"0??", "?0?"}; + vector rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_)); + string columns_[] = {"01", "00", "10"}; + vector columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_)); + string __[] = {"001", "100"}; + vector _(__, __+sizeof(__)/sizeof(*__)); +END + +} +// END CUT HERE ADDED SRM/527-U/2A.cpp Index: SRM/527-U/2A.cpp ================================================================== --- SRM/527-U/2A.cpp +++ SRM/527-U/2A.cpp @@ -0,0 +1,133 @@ +#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 P8XMatrixTransformation { public: + string solve(vector original, vector target) + { + int so = 0, st = 0; + 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 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(_, P8XMatrixTransformation().solve(original, target));} +int main(){ + +CASE(0) + string original_[] = {"01" +,"11"}; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = {"11" +,"10"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "YES"; +END +CASE(1) + string original_[] = {"0111" +,"0011"}; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = {"1011" +,"1100"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "YES"; +END +CASE(2) + string original_[] = {"0"}; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = {"1"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "NO"; +END +CASE(3) + string original_[] = {"1111" +,"1111" +,"0000" +,"0000"}; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = {"1111" +,"1111" +,"0000" +,"0000"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "YES"; +END +CASE(4) + string original_[] = {"0110" +,"1001" +,"0110"}; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = {"1111" +,"0110" +,"0000"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "YES"; +END +CASE(5) + string original_[] = {"0000" +,"1111" +,"0000"}; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = {"1111" +,"0000" +,"1111"}; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = "NO"; +END +/* +CASE(6) + string original_[] = ; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = ; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = ; +END +CASE(7) + string original_[] = ; + vector original(original_, original_+sizeof(original_)/sizeof(*original_)); + string target_[] = ; + vector target(target_, target_+sizeof(target_)/sizeof(*target_)); + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/527-U/2C.cpp Index: SRM/527-U/2C.cpp ================================================================== --- SRM/527-U/2C.cpp +++ SRM/527-U/2C.cpp @@ -0,0 +1,115 @@ +#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 P8XCoinChangeAnother { public: + vector solve(int N, long long coins_sum, long long coins_count) + { + vector result; + for(int i=0; i>i : ((1LL<(); + + for(int i=N-1; i>0; --i) { + if( coins_count == 0 ) + return result; + else { + LL& me = result[i]; + LL dec = min(me, coins_count); + me -= dec; + result[i-1] += dec*2; + coins_count -= dec; + } + } + return coins_count == 0 ? result : vector(); + } +}; + +// 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(_, P8XCoinChangeAnother().solve(N, coins_sum, coins_count));} +int main(){ + +CASE(0) + int N = 2; + long long coins_sum = 4LL; + long long coins_count = 3LL; + long long __[] = {2, 1 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int N = 3; + long long coins_sum = 6LL; + long long coins_count = 3LL; + long long __[] = {0, 3, 0 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + int N = 2; + long long coins_sum = 8LL; + long long coins_count = 1LL; + vector _; +END +CASE(3) + int N = 1; + long long coins_sum = 10000000000LL; + long long coins_count = 10000000000LL; + long long __[] = {10000000000 }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(4) + int N = ; + long long coins_sum = LL; + long long coins_count = LL; + long long __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int N = ; + long long coins_sum = LL; + long long coins_count = LL; + long long __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE