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

Added SRM/597-U/1A.cpp version [1d6eb8d5bd0ebac2]

            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  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class LittleElephantAndString { public:
           23  + int getNumber(string A, string B)
           24  + {
           25  +  string AA = A, BB = B;
           26  +  sort(AA.begin(), AA.end());
           27  +  sort(BB.begin(), BB.end());
           28  +  if(AA != BB)
           29  +   return -1;
           30  +  for(int n=0; n<B.size(); ++n)
           31  +   if(sup_sub(A, B.substr(n)))
           32  +    return n;
           33  +  assert(false);
           34  + }
           35  +
           36  + bool sup_sub(const string& A, const string& B)
           37  + {
           38  +  for(int a=0, b=0; b<B.size(); ++a,++b)
           39  +  {
           40  +   while(a<A.size() && A[a]!=B[b])
           41  +    ++a;
           42  +   if(a == A.size())
           43  +    return false;
           44  +  }
           45  +  return true;
           46  + }
           47  +};
           48  +
           49  +// BEGIN CUT HERE
           50  +#include <ctime>
           51  +double start_time; string timer()
           52  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           53  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           54  + { os << "{ ";
           55  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           56  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           57  +void verify_case(const int& Expected, const int& Received) {
           58  + bool ok = (Expected == Received);
           59  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           60  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           61  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           62  +#define END  verify_case(_, LittleElephantAndString().getNumber(A, B));}
           63  +int main(){
           64  +
           65  +CASE(0)
           66  + string A = "ABC";
           67  + string B = "CBA";
           68  + int _ = 2;
           69  +END
           70  +CASE(1)
           71  + string A = "A";
           72  + string B = "B";
           73  + int _ = -1;
           74  +END
           75  +CASE(2)
           76  + string A = "AAABBB";
           77  + string B = "BBBAAA";
           78  + int _ = 3;
           79  +END
           80  +CASE(3)
           81  + string A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
           82  + string B = "ZYXWVUTSRQPONMLKJIHGFEDCBA";
           83  + int _ = 25;
           84  +END
           85  +CASE(4)
           86  + string A = "A";
           87  + string B = "A";
           88  + int _ = 0;
           89  +END
           90  +CASE(5)
           91  + string A = "DCABA";
           92  + string B = "DACBA";
           93  + int _ = 2;
           94  +END
           95  +/*
           96  +CASE(6)
           97  + string A = ;
           98  + string B = ;
           99  + int _ = ;
          100  +END
          101  +CASE(7)
          102  + string A = ;
          103  + string B = ;
          104  + int _ = ;
          105  +END
          106  +*/
          107  +}
          108  +// END CUT HERE

Added SRM/597-U/1B.cpp version [ddf4c7315f5e5a02]

            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  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +LL gcd(LL a, LL b)
           23  +{
           24  + while(a)
           25  +  swap(a, b%=a);
           26  + return b;
           27  +}
           28  +
           29  +class ConvexPolygonGame { public:
           30  + string winner(vector <int> X, vector <int> Y)
           31  + {
           32  +  return has_int_triangle(X, Y) ? "Masha" : "Petya";
           33  + }
           34  +
           35  + bool has_int_triangle(const vector<int>& X, const vector<int>& Y)
           36  + {
           37  +  const int xm = *min_element(X.begin(), X.end());
           38  +  const int xM = *max_element(X.begin(), X.end());
           39  +
           40  +  vector< pair<int,int> > p;
           41  +
           42  +  int nc = 0, two = 0, dis = 0;
           43  +  for(int x=xm; x<=xM; ++x)
           44  +  {
           45  +   int ym, yM;
           46  +   tie(ym, yM) = y_range(x, X, Y);
           47  +   if(ym <= yM) {
           48  +    dis ++;
           49  +    nc += (yM - ym + 1);
           50  +    if(yM-ym+1 >= 2)
           51  +     two ++;
           52  +    else
           53  +     p.emplace_back(x, ym);
           54  +   }
           55  +//   cerr << nc << "," << two << " : " << x << " " << ym << " ~ " << yM << endl;
           56  +   if(nc>=3 && two>=1 && dis>=2)
           57  +    return true;
           58  +  }
           59  +  if(nc>=3 && two==0 && dis>=2)
           60  +  {
           61  +   double am, aM;
           62  +   for(int i=1; i<p.size(); ++i)
           63  +   {
           64  +    double a = double(p[i].second - p[0].second) / (p[i].first - p[0].first);
           65  +    if(i==1)am=aM=a;
           66  +    else am=min(am, a), aM=max(aM,a);
           67  +   }
           68  +   return (aM-am) > 1e-9;
           69  +  }
           70  +  return false;
           71  + }
           72  +
           73  + tuple<int,int> y_range(int x, const vector<int>& X, const vector<int>& Y)
           74  + {
           75  +  vector< pair<LL,LL> > cross;
           76  +  vector< pair<LL,LL> > exact;
           77  +
           78  +  const int N = X.size();
           79  +  for(int i=0; i<N; ++i)
           80  +  {
           81  +   int x1=X[i], x2=X[(i+1)%N];
           82  +   int y1=Y[i], y2=Y[(i+1)%N];
           83  +   if(x1 > x2)
           84  +    swap(x1, x2), swap(y1, y2);
           85  +
           86  +   if(x1 == x2)
           87  +   {
           88  +    if(x == x1) {
           89  +     cross.emplace_back(y1,1);
           90  +     cross.emplace_back(y2,1);
           91  +     exact.emplace_back(y1,1);
           92  +     exact.emplace_back(y2,1);
           93  +    }
           94  +   }
           95  +   else
           96  +   {
           97  +    if(x<x1 || x2<x)
           98  +     continue;
           99  +    LL q = LL(y2-y1)*(x-x1) + LL(y1)*(x2-x1);
          100  +    LL d = LL(x2-x1);
          101  +    LL g = gcd(abs(q), d);
          102  +    cross.emplace_back(q/g, d/g);
          103  +    if(x==x1 || x==x2)
          104  +     exact.emplace_back(q/g, d/g);
          105  +   }
          106  +  }
          107  +
          108  +  sort(cross.begin(), cross.end());
          109  +  cross.erase(unique(cross.begin(), cross.end()), cross.end());
          110  +  if(cross.size() == 2) {
          111  +   LL q1 = cross[0].first;
          112  +   LL d1 = cross[0].second;
          113  +   LL q2 = cross[1].first;
          114  +   LL d2 = cross[1].second;
          115  +   if(q1*d2 > q2*d1)
          116  +    swap(q1,q2), swap(d1,d2);
          117  +   int ym = ceil_div(q1, d1);
          118  +   int yM = floor_div(q2, d2);
          119  +   bool ym_exact = false, yM_exact = false;
          120  +   for(int i=0; i<exact.size(); ++i) {
          121  +    if(ym*exact[i].second == exact[i].first)
          122  +     ym_exact = true;
          123  +    if(yM*exact[i].second == exact[i].first)
          124  +     yM_exact = true;
          125  +   }
          126  +   return make_tuple(ym_exact ? ym+1 : ym, yM_exact ? yM-1 : yM);
          127  +  }
          128  +  return make_tuple(-9998, -9999);
          129  + }
          130  +
          131  + static int floor_div(LL a, LL b)
          132  + {
          133  +  if(a>=0) return int(a/b);
          134  +  return int(-((-a+b-1)/b));
          135  + }
          136  +
          137  + static int ceil_div(LL a, LL b)
          138  + {
          139  +  if(a>=0) return int((a+b-1)/b);
          140  +  return int(-((-a)/b));
          141  + }
          142  +};
          143  +
          144  +// BEGIN CUT HERE
          145  +#include <ctime>
          146  +double start_time; string timer()
          147  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          148  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          149  + { os << "{ ";
          150  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          151  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          152  +void verify_case(const string& Expected, const string& Received) {
          153  + bool ok = (Expected == Received);
          154  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          155  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          156  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          157  +#define END  verify_case(_, ConvexPolygonGame().winner(X, Y));}
          158  +int main(){
          159  +
          160  +CASE(0)
          161  + int X_[] = {0, 1, 0};
          162  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          163  + int Y_[] = {0, 0, 1};
          164  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          165  + string _ = "Petya";
          166  +END
          167  +CASE(1)
          168  + int X_[] = {0, 4, 2};
          169  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          170  + int Y_[] = {0, 0, 2};
          171  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          172  + string _ = "Masha";
          173  +END
          174  +CASE(2)
          175  + int X_[] = {0, 100, 100, 0};
          176  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          177  + int Y_[] = {0, 0, 100, 100};
          178  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          179  + string _ = "Masha";
          180  +END
          181  +CASE(3)
          182  + int X_[] = {0, 50, 100, 50};
          183  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          184  + int Y_[] = {0, -1, 0, 1};
          185  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          186  + string _ = "Petya";
          187  +END
          188  +CASE(4)
          189  + int X_[] = {-100000, 100000, 100000, -100000};
          190  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          191  + int Y_[] = {-1, -1, 1, 1};
          192  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          193  + string _ = "Masha";
          194  +END
          195  +CASE(5)
          196  + // 1 1 1 (yoko)
          197  + int X_[] = {0, 3, 5, 3};
          198  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          199  + int Y_[] = {0, 0, 1, 1};
          200  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          201  + string _ = "Masha";
          202  +END
          203  +CASE(5)
          204  + // 1 1 1 (tate)
          205  + int X_[] = {0, 1, 1, 0};
          206  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          207  + int Y_[] = {0, 3, 5, 3};
          208  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          209  + string _ = "Masha";
          210  +END
          211  +CASE(6)
          212  + // 3 (tate)  // yoko ha sample
          213  + int X_[] = {-1, 0, 1, 0};
          214  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          215  +    int Y_[] = {0, -2, 0, 2};
          216  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          217  + string _ = "Petya";
          218  +END
          219  +}
          220  +// END CUT HERE