ADDED SRM/600-U/1A.cpp Index: SRM/600-U/1A.cpp ================================================================== --- SRM/600-U/1A.cpp +++ SRM/600-U/1A.cpp @@ -0,0 +1,104 @@ +#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 ORSolitaire { public: + int getMinimum(vector numbers, int goal) + { + vector n2; + for(int u: numbers) + if((goal&u) == u) + n2.push_back(u); + numbers.swap(n2); + + int best = 9999999; + for(int v=1; v<=goal; v<<=1) if(goal&v) { + int cnt = 0; + for(int u: numbers) + if(u&v) + ++cnt; + best = min(best, cnt); + } + return 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(_, ORSolitaire().getMinimum(numbers, goal));} +int main(){ + +CASE(0) + int numbers_[] = {1, 2, 4}; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = 7; + int _ = 1; +END +CASE(1) + int numbers_[] = {1, 2, 4, 7, 8}; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = 7; + int _ = 2; +END +CASE(2) + int numbers_[] = {12571295, 2174218, 2015120}; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = 1; + int _ = 0; +END +CASE(3) + int numbers_[] = {5,2,4,52,62,9,8,3,1,11,6}; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = 11; + int _ = 3; +END +CASE(4) + int numbers_[] = {503, 505, 152, 435, 491, 512, 1023, 355, 510, 500, 502, 255, 63, 508, 509, 511, 60, 250, 254, 346}; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = 510; + int _ = 5; +END +CASE(5) + int numbers_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = 63; + int _ = 19; +END +/* +CASE(6) + int numbers_[] = ; + vector numbers(numbers_, numbers_+sizeof(numbers_)/sizeof(*numbers_)); + int goal = ; + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/600-U/1B.cpp Index: SRM/600-U/1B.cpp ================================================================== --- SRM/600-U/1B.cpp +++ SRM/600-U/1B.cpp @@ -0,0 +1,205 @@ +#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 PalindromeMatrix { public: + int minChange(vector A, int rowCount, int columnCount) + { + const int H = A.size(), W = A[0].size(); + vector> cpp, rpp; + { + vector cp(W-columnCount, 0); cp.resize(W, 1); + do cpp.push_back(cp); while(next_permutation(cp.begin(), cp.end())); + vector rp(H-rowCount, 0); rp.resize(H, 1); + do rpp.push_back(rp); while(next_permutation(rp.begin(), rp.end())); + } + + int best = 99999999; + for(auto& cp: cpp) + { + int c_score = 0; + for(int x=0; x r_score_0(H), r_score_3(H), r_score_4(H); + 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(_, PalindromeMatrix().minChange(A, rowCount, columnCount));} +int main(){ + +CASE(0) + string A_[] = {"0000" +,"1000" +,"1100" +,"1110"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 2; + int columnCount = 2; + int _ = 1; +END +CASE(1) + string A_[] = {"0000" +,"1000" +,"1100" +,"1110"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 3; + int columnCount = 2; + int _ = 3; +END +CASE(2) + string A_[] = {"01" +,"10"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 1; + int columnCount = 1; + int _ = 1; +END +CASE(3) + string A_[] = {"1110" +,"0001"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 0; + int columnCount = 0; + int _ = 0; +END +CASE(4) + string A_[] = {"01010101" +,"01010101" +,"01010101" +,"01010101" +,"01010101" +,"01010101" +,"01010101" +,"01010101"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 2; + int columnCount = 3; + int _ = 8; +END +CASE(5) + string A_[] = {"000000000000" +,"011101110111" +,"010001010101" +,"010001010101" +,"011101010101" +,"010101010101" +,"010101010101" +,"011101110111" +,"000000000000" +,"000000000000"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 5; + int columnCount = 9; + int _ = 14; +END +CASE(6) + string A_[] = {"11111101001110" +,"11000111111111" +,"00010101111001" +,"10110000111111" +,"10000011010010" +,"10001101101101" +,"00101010000001" +,"10111010100100" +,"11010011110111" +,"11100010110110" +,"00100101010100" +,"01001011001000" +,"01010001111010" +,"10100000010011"}; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = 6; + int columnCount = 8; + int _ = 31; +END +/* +CASE(7) + string A_[] = ; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = ; + int columnCount = ; + int _ = ; +END +CASE(8) + string A_[] = ; + vector A(A_, A_+sizeof(A_)/sizeof(*A_)); + int rowCount = ; + int columnCount = ; + int _ = ; +END +*/ +} +// END CUT HERE