ADDED SRM/574-U/1A-U.cpp
Index: SRM/574-U/1A-U.cpp
==================================================================
--- SRM/574-U/1A-U.cpp
+++ SRM/574-U/1A-U.cpp
@@ -0,0 +1,135 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class TheNumberGame { public:
+ string determineOutcome(int A, int B)
+ {
+ string S; {stringstream sin; sin<<A; sin>>S;}
+ string T; {stringstream sin; sin<<B; sin>>T;}
+ return rec(S,T) ? "Manao wins" : "Manao loses";
+ }
+
+ map<pair<string,string>, bool> memo;
+ bool rec(const string& S, const string& T)
+ {
+ if(S == T)
+ return false;
+ pair<string, string> key(S, T);
+ if(memo.count(key))
+ return memo[key];
+
+ bool aWin = false;
+ for(int a=0; a<2; ++a)
+ {
+ string S1 = op(S, a);
+ aWin |= (S1 == T);
+
+ bool bWin = false;
+ for(int b=0; b<2; ++b)
+ {
+ string T1 = op(T, b);
+ bWin |= (S1 == T1);
+
+ bool cWin = false;
+ for(int c=0; c<2; ++c)
+ {
+ string S2 = op(S1, c);
+ cWin |= (S2 == T1);
+
+ bool dWin = false;
+ for(int d=0; d<2; ++d)
+ {
+ string T2 = op(T1, d);
+ dWin |= (S2 == T2);
+
+ if(S==S2 || T==T2)
+ dWin |= true;
+ else
+ dWin |= !rec(S2, T2);
+ }
+ cWin |= !dWin;
+ }
+ bWin |= !cWin;
+ }
+ aWin |= !bWin;
+ }
+ return memo[key] = aWin;
+ }
+
+ string op(const string& s, int i)
+ {
+ if(i==0)
+ return s.empty() ? s : s.substr(0, s.size()-1);
+ else
+ return string(s.rbegin(), s.rend());
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::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(_, TheNumberGame().determineOutcome(A, B));}
+int main(){
+
+CASE(0)
+ int A = 45;
+ int B = 4;
+ string _ = "Manao wins";
+END
+CASE(1)
+ int A = 45;
+ int B = 5;
+ string _ = "Manao wins";
+END
+CASE(2)
+ int A = 99;
+ int B = 123;
+ string _ = "Manao loses";
+END
+CASE(3)
+ int A = 2356236;
+ int B = 5666;
+ string _ = "Manao loses";
+END
+/*
+CASE(4)
+ int A = ;
+ int B = ;
+ string _ = ;
+END
+CASE(5)
+ int A = ;
+ int B = ;
+ string _ = ;
+END
+*/
+}
+// END CUT HERE
ADDED SRM/574-U/1B.cpp
Index: SRM/574-U/1B.cpp
==================================================================
--- SRM/574-U/1B.cpp
+++ SRM/574-U/1B.cpp
@@ -0,0 +1,124 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class PolygonTraversal { public:
+ long long count(int N, vector <int> points)
+ {
+ int p0 = points[0];
+ for(int i=0; i<points.size(); ++i)
+ points[i] = (points[i]-p0+N)%N;
+
+ int mask = 0;
+ for(int i=0; i<points.size(); ++i)
+ mask |= (1 << points[i]);
+
+ vector<LL> memo(N<<N, -1);
+ return rec(mask, points.back(), N, memo);
+ }
+
+ LL rec(int mask, int i, int N, vector<LL>& memo)
+ {
+ if(mask == (1<<N)-1) {
+ return (i==1 || i==N-1) ? 0 : 1;
+ }
+ int key = (i<<N) | mask;
+ if( memo[key] != -1 )
+ return memo[key];
+
+ LL total = 0;
+ for(int k=0; k<N; ++k) if(!(mask&(1<<k))) {
+ int base = min(i, k);
+ int mid = max(i,k)-base;
+ int left=0, right=0;
+ for(int j=0; j<N; ++j) if(mask&(1<<j)) {
+ int idx = (j-base+N)%N;
+ if(0<idx&&idx<mid)++left;
+ if(mid<idx&&idx<N)++right;
+ }
+ if(left&&right)
+ total += rec(mask|(1<<k), k, N, memo);
+ }
+ return memo[key] = total;
+ }
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+ for(typename vector<T>::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(_, PolygonTraversal().count(N, points));}
+int main(){
+
+CASE(0)
+ int N = 5;
+ int points_[] = {1, 3, 5};
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = 1LL;
+END
+CASE(1)
+ int N = 6;
+ int points_[] = {1, 4, 2};
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = 1LL;
+END
+CASE(2)
+ int N = 7;
+ int points_[] = {2, 4, 7};
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = 2LL;
+END
+CASE(3)
+ int N = 7;
+ int points_[] = {1, 2, 3, 4, 6, 5};
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = 0LL;
+END
+CASE(4)
+ int N = 18;
+ int points_[] = {1, 7, 18};
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = 4374612736LL;
+END
+CASE(5)
+int N = 18;
+int points_[] = {1,8};
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = -2LL;
+END
+/*
+CASE(6)
+ int N = ;
+ int points_[] = ;
+ vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
+ long long _ = LL;
+END
+*/
+}
+// END CUT HERE