ADDED SRM/TCO17-2A-U/1A.cpp Index: SRM/TCO17-2A-U/1A.cpp ================================================================== --- SRM/TCO17-2A-U/1A.cpp +++ SRM/TCO17-2A-U/1A.cpp @@ -0,0 +1,93 @@ +#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 gcd(int a, int b) +{ + while (a) + swap(a, b %= a); + return b; +} + + +class FoxAndCake2 { public: + string isPossible(int c, int s) + { + return solve(c, s) ? "Possible" : "Impossible"; + } + + bool solve(int a, int b) + { + if (gcd(a, b) != 1) + return true; + + for (int x = 2; x <= 100 && x < a; ++x) + for (int y = 2; y <= 100 && y < b; ++y) + if (gcd(x, y) != 1 && gcd(a - x, b - y) != 1) + 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(_, FoxAndCake2().isPossible(c, s));} +int main(){ + +CASE(0) + int c = 74; + int s = 109; + string _ = "Possible"; +END +CASE(1) + int c = 1000000000; + int s = 1000000000; + string _ = "Possible"; +END +CASE(2) + int c = 1; + int s = 58; + string _ = "Impossible"; +END +CASE(3) + int c = 223092871; + int s = 446185741; + string _ = "Possible"; +END +/* +CASE(4) + int c = ; + int s = ; + string _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/TCO17-2A-U/1B-C.cpp Index: SRM/TCO17-2A-U/1B-C.cpp ================================================================== --- SRM/TCO17-2A-U/1B-C.cpp +++ SRM/TCO17-2A-U/1B-C.cpp @@ -0,0 +1,188 @@ +#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 DistanceZeroAndOne { public: + vector construct(vector dist0, vector dist1) + { + const vector IMPOSSIBLE; + const int N = dist0.size(); + const int d01 = dist0[1]; + if (dist0[0] != 0) return IMPOSSIBLE; + if (dist1[1] != 0) return IMPOSSIBLE; + if (dist0[1] != dist1[0]) return IMPOSSIBLE; + + map, int> repr; + for (int x = 0; x < N; ++x) + repr[make_pair(dist0[x], dist1[x])] = x; + + vector ans(N, string(N, 'N')); + ans[0][1] = ans[1][0] = d01 == 1 ? 'Y' : 'N'; + for (int x = 2; x < N; ++x) { + const int d0 = dist0[x]; + const int d1 = dist1[x]; + if (d0==0 || d1==0 || d0+d1 +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(_, DistanceZeroAndOne().construct(dist0, dist1));} +int main(){ + +CASE(0) + int dist0_[] = {0,2,1}; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = {2,0,1}; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + string __[] = {"NNY", "NNY", "YYN" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + int dist0_[] = {0,2,1}; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = {1,0,2}; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + vector _; +END +CASE(2) + int dist0_[] = {3,1,1,1}; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = {1,0,1,1}; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + vector _; +END +CASE(3) + int dist0_[] = {0,1,1,1}; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = {1,0,1,1}; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + string __[] = {"NYYY", "YNYY", "YYNN", "YYNN" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + int dist0_[] = {0,3,1,2,2,3,4,4}; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = {3,0,2,1,2,3,4,4}; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + string __[] = {"NNYNNNNN", "NNNYNNNN", "YNNYYNNN", "NYYNYNNN", "NNYYNYNN", "NNNNYNYY", "NNNNNYNN", "NNNNNYNN" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + int dist0_[] = {0,1}; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = {1,0}; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + string __[] = {"NY", "YN" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(6) + int dist0_[] = ; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = ; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + string __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(7) + int dist0_[] = ; + vector dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); + int dist1_[] = ; + vector dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); + string __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE