ADDED SRM/590-U/1A.cpp Index: SRM/590-U/1A.cpp ================================================================== --- SRM/590-U/1A.cpp +++ SRM/590-U/1A.cpp @@ -0,0 +1,112 @@ +#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 FoxAndChess { public: + string ableToMove(string begin, string target) + { + return solve(cb(begin), cb(target)) ? "Possible" : "Impossible"; + } + + vector> cb(string s) + { + vector> v; + for(int i=0; i>& b, const vector>& e) + { + if(b.size() != e.size()) + return false; + for(int i=0; ie[i].second) + return false; + } + return true; + } +}; + +// 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(_, FoxAndChess().ableToMove(begin, target));} +int main(){ + +CASE(0) + string begin = "R..."; + string target = "..R."; + string _ = "Possible"; +END +CASE(1) + string begin = "..R."; + string target = "R..."; + string _ = "Impossible"; +END +CASE(2) + string begin = ".L.R.R."; + string target = "L...R.R"; + string _ = "Possible"; +END +CASE(3) + string begin = ".L.R."; + string target = ".R.L."; + string _ = "Impossible"; +END +CASE(4) + string begin = "LRLLRLRLLRLLRLRLRL"; + string target = "LRLLRLRLLRLLRLRLRL"; + string _ = "Possible"; +END +CASE(5) + string begin = "L"; + string target = "."; + string _ = "Impossible"; +END +/* +CASE(6) + string begin = ; + string target = ; + string _ = ; +END +CASE(7) + string begin = ; + string target = ; + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/590-U/1B.cpp Index: SRM/590-U/1B.cpp ================================================================== --- SRM/590-U/1B.cpp +++ SRM/590-U/1B.cpp @@ -0,0 +1,159 @@ +#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 XorCards { public: + long long numberOfWays(vector number, long long limit) + { + LL total = 0; + LL req = 0; + for(int k=62; k>=0; --k) + if(limit & (1LL< num, int k, LL req) + { + for(auto& v : num) v>>=k; + return exact_equal(num, req>>k); + } + + LL exact_equal(const vector& xs, LL target) + { + int H = 50; + int W = xs.size(); + vector> M(H, vector(W)); + for(int y=0; y>y)&1; + vector V(H); + for(int y=0; y>y)&1; + return num_solution(H, W, M, V); + } + + LL num_solution(int H, int W, vector>& M, vector& V) + { + int skipx = 0; + int y = 0; + for(int x=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 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(_, XorCards().numberOfWays(number, limit));} +int main(){ + +CASE(0) + long long number_[] = {1,2}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 2LL; + long long _ = 3LL; +END +CASE(1) + long long number_[] = {5,5}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 3LL; + long long _ = 2LL; +END +CASE(2) + long long number_[] = {1,2,3,4,5,6,7}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 5LL; + long long _ = 96LL; +END +CASE(3) + long long number_[] = {123, 456, 789, 147, 258, 369, 159, 357}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 500LL; + long long _ = 125LL; +END +CASE(4) + long long number_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 1000000000000000LL; + long long _ = 4294967296LL; +END +CASE(5) + long long number_[] = {1000000000000000, 999999999999999}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 65535LL; + long long _ = 2LL; +END +CASE(6) + long long number_[] = {892821358,637693537,31021825,911417798,989152798,284478611,929786194,624328131,349242118,86796344,350424823,336624178,632226779,266072173,568692508,711852205,512468333,579346169,469280619,720923652,106128825,932999125,57927219,490494892,140637785,916813689,793075515,469189529,107539985,793418872,865662420,451333923,555332979,862325752,89326522,290303848,701668240,319909799,418021685,730702785,515002318,381415044,165516801,881368921,604262389,333836176,678197867,988945968,594771926,214252143}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 225387446LL; + long long _ = -1LL; +END +CASE(7) +long long number_[] = {0}; + vector number(number_, number_+sizeof(number_)/sizeof(*number_)); + long long limit = 1LL; + long long _ = 2LL; +END + +} +// END CUT HERE