• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/574-U/1A-U.cpp version [03cf07f878cb3074]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class TheNumberGame { public:
           23  + string determineOutcome(int A, int B)
           24  + {
           25  +  string S; {stringstream sin; sin<<A; sin>>S;}
           26  +  string T; {stringstream sin; sin<<B; sin>>T;}
           27  +  return rec(S,T) ? "Manao wins" : "Manao loses";
           28  + }
           29  +
           30  + map<pair<string,string>, bool> memo;
           31  + bool rec(const string& S, const string& T)
           32  + {
           33  +  if(S == T)
           34  +   return false;
           35  +  pair<string, string> key(S, T);
           36  +  if(memo.count(key))
           37  +   return memo[key];
           38  +
           39  +  bool aWin = false;
           40  +  for(int a=0; a<2; ++a)
           41  +  {
           42  +   string S1 = op(S, a);
           43  +   aWin |= (S1 == T);
           44  +
           45  +   bool bWin = false;
           46  +   for(int b=0; b<2; ++b)
           47  +   {
           48  +    string T1 = op(T, b);
           49  +    bWin |= (S1 == T1);
           50  +
           51  +    bool cWin = false;
           52  +    for(int c=0; c<2; ++c)
           53  +    {
           54  +     string S2 = op(S1, c);
           55  +     cWin |= (S2 == T1);
           56  +
           57  +     bool dWin = false;
           58  +     for(int d=0; d<2; ++d)
           59  +     {
           60  +      string T2 = op(T1, d);
           61  +      dWin |= (S2 == T2);
           62  +
           63  +      if(S==S2 || T==T2)
           64  +       dWin |= true;
           65  +      else
           66  +       dWin |= !rec(S2, T2);
           67  +     }
           68  +     cWin |= !dWin;
           69  +    }
           70  +    bWin |= !cWin;
           71  +   }
           72  +   aWin |= !bWin;
           73  +  }
           74  +  return memo[key] = aWin;
           75  + }
           76  +
           77  + string op(const string& s, int i)
           78  + {
           79  +  if(i==0)
           80  +   return s.empty() ? s : s.substr(0, s.size()-1);
           81  +  else
           82  +   return string(s.rbegin(), s.rend());
           83  + }
           84  +};
           85  +
           86  +// BEGIN CUT HERE
           87  +#include <ctime>
           88  +double start_time; string timer()
           89  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           90  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           91  + { os << "{ ";
           92  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           93  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           94  +void verify_case(const string& Expected, const string& Received) {
           95  + bool ok = (Expected == Received);
           96  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           97  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           98  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           99  +#define END  verify_case(_, TheNumberGame().determineOutcome(A, B));}
          100  +int main(){
          101  +
          102  +CASE(0)
          103  + int A = 45;
          104  + int B = 4;
          105  + string _ = "Manao wins";
          106  +END
          107  +CASE(1)
          108  + int A = 45;
          109  + int B = 5;
          110  + string _ = "Manao wins";
          111  +END
          112  +CASE(2)
          113  + int A = 99;
          114  + int B = 123;
          115  + string _ = "Manao loses";
          116  +END
          117  +CASE(3)
          118  + int A = 2356236;
          119  + int B = 5666;
          120  + string _ = "Manao loses";
          121  +END
          122  +/*
          123  +CASE(4)
          124  + int A = ;
          125  + int B = ;
          126  + string _ = ;
          127  +END
          128  +CASE(5)
          129  + int A = ;
          130  + int B = ;
          131  + string _ = ;
          132  +END
          133  +*/
          134  +}
          135  +// END CUT HERE

Added SRM/574-U/1B.cpp version [46af941c66fe6efd]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class PolygonTraversal { public:
           23  + long long count(int N, vector <int> points)
           24  + {
           25  +  int p0 = points[0];
           26  +  for(int i=0; i<points.size(); ++i)
           27  +   points[i] = (points[i]-p0+N)%N;
           28  +
           29  +  int mask = 0;
           30  +  for(int i=0; i<points.size(); ++i)
           31  +   mask |= (1 << points[i]);
           32  +
           33  +  vector<LL> memo(N<<N, -1);
           34  +  return rec(mask, points.back(), N, memo);
           35  + }
           36  +
           37  + LL rec(int mask, int i, int N, vector<LL>& memo)
           38  + {
           39  +  if(mask == (1<<N)-1) {
           40  +   return (i==1 || i==N-1) ? 0 : 1;
           41  +  }
           42  +  int key = (i<<N) | mask;
           43  +  if( memo[key] != -1 )
           44  +   return memo[key];
           45  +
           46  +  LL total = 0;
           47  +  for(int k=0; k<N; ++k) if(!(mask&(1<<k))) {
           48  +   int base = min(i, k);
           49  +   int mid = max(i,k)-base;
           50  +   int left=0, right=0;
           51  +   for(int j=0; j<N; ++j) if(mask&(1<<j)) {
           52  +    int idx = (j-base+N)%N;
           53  +    if(0<idx&&idx<mid)++left;
           54  +    if(mid<idx&&idx<N)++right;
           55  +   }
           56  +   if(left&&right)
           57  +    total += rec(mask|(1<<k), k, N, memo);
           58  +  }
           59  +  return memo[key] = total;
           60  + }
           61  +};
           62  +
           63  +// BEGIN CUT HERE
           64  +#include <ctime>
           65  +double start_time; string timer()
           66  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           67  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           68  + { os << "{ ";
           69  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           70  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           71  +void verify_case(const long long& Expected, const long long& Received) {
           72  + bool ok = (Expected == Received);
           73  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           74  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           75  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           76  +#define END  verify_case(_, PolygonTraversal().count(N, points));}
           77  +int main(){
           78  +
           79  +CASE(0)
           80  + int N = 5;
           81  + int points_[] = {1, 3, 5};
           82  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           83  + long long _ = 1LL;
           84  +END
           85  +CASE(1)
           86  + int N = 6;
           87  + int points_[] = {1, 4, 2};
           88  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           89  + long long _ = 1LL;
           90  +END
           91  +CASE(2)
           92  + int N = 7;
           93  + int points_[] = {2, 4, 7};
           94  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           95  + long long _ = 2LL;
           96  +END
           97  +CASE(3)
           98  + int N = 7;
           99  + int points_[] = {1, 2, 3, 4, 6, 5};
          100  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          101  + long long _ = 0LL;
          102  +END
          103  +CASE(4)
          104  + int N = 18;
          105  + int points_[] = {1, 7, 18};
          106  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          107  + long long _ = 4374612736LL;
          108  +END
          109  +CASE(5)
          110  +int N = 18;
          111  +int points_[] = {1,8};
          112  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          113  + long long _ = -2LL;
          114  +END
          115  +/*
          116  +CASE(6)
          117  + int N = ;
          118  + int points_[] = ;
          119  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          120  + long long _ = LL;
          121  +END
          122  +*/
          123  +}
          124  +// END CUT HERE