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

Added SRM/559-U/1A.cpp version [f6f063e1572c0239]

            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 HyperKnight { public:
           23  + long long countCells(int a_, int b_, int numRows, int numColumns, int K)
           24  + {
           25  +  if(a_>b_) swap(a_,b_);
           26  +  const LL A=a_, B=b_, W=numRows, H=numColumns;
           27  +
           28  +  LL xx[] = {0, A, B, W-B, W-A, W};
           29  +  LL yy[] = {0, A, B, H-B, H-A, H};
           30  +  LL dx[] = {+A, +A, -A, -A, +B, +B, -B, -B};
           31  +  LL dy[] = {+B, -B, +B, -B, +A, -A, +A, -A};
           32  +
           33  +  LL cnt = 0;
           34  +  for(int i=0; i+1<sizeof(xx)/sizeof(*xx); ++i)
           35  +  for(int k=0; k+1<sizeof(yy)/sizeof(*yy); ++k) {
           36  +   LL w = xx[i+1]-xx[i], x = xx[i];
           37  +   LL h = yy[k+1]-yy[k], y = yy[k];
           38  +   int av = 0;
           39  +   for(int j=0; j<8; ++j) {
           40  +    LL x2 = x + dx[j];
           41  +    LL y2 = y + dy[j];
           42  +    if(0<=x2 && x2<W && 0<=y2&&y2<H)
           43  +     ++av;
           44  +   }
           45  +   if(av==K)
           46  +    cnt += w*h;
           47  +  }
           48  +  return cnt;
           49  + }
           50  +};
           51  +
           52  +// BEGIN CUT HERE
           53  +#include <ctime>
           54  +double start_time; string timer()
           55  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           56  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           57  + { os << "{ ";
           58  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           59  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           60  +void verify_case(const long long& Expected, const long long& Received) {
           61  + bool ok = (Expected == Received);
           62  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           63  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           64  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           65  +#define END  verify_case(_, HyperKnight().countCells(a, b, numRows, numColumns, k));}
           66  +int main(){
           67  +
           68  +CASE(0)
           69  + int a = 2;
           70  + int b = 1;
           71  + int numRows = 8;
           72  + int numColumns = 8;
           73  + int k = 4;
           74  + long long _ = 20LL;
           75  +END
           76  +CASE(1)
           77  + int a = 3;
           78  + int b = 2;
           79  + int numRows = 8;
           80  + int numColumns = 8;
           81  + int k = 2;
           82  + long long _ = 16LL;
           83  +END
           84  +CASE(2)
           85  + int a = 1;
           86  + int b = 3;
           87  + int numRows = 7;
           88  + int numColumns = 11;
           89  + int k = 0;
           90  + long long _ = 0LL;
           91  +END
           92  +CASE(3)
           93  + int a = 3;
           94  + int b = 2;
           95  + int numRows = 10;
           96  + int numColumns = 20;
           97  + int k = 8;
           98  + long long _ = 56LL;
           99  +END
          100  +CASE(4)
          101  + int a = 1;
          102  + int b = 4;
          103  + int numRows = 100;
          104  + int numColumns = 10;
          105  + int k = 6;
          106  + long long _ = 564LL;
          107  +END
          108  +CASE(5)
          109  + int a = 2;
          110  + int b = 3;
          111  + int numRows = 1000000000;
          112  + int numColumns = 1000000000;
          113  + int k = 8;
          114  + long long _ = 999999988000000036LL;
          115  +END
          116  +/*
          117  +CASE(6)
          118  + int a = ;
          119  + int b = ;
          120  + int numRows = ;
          121  + int numColumns = ;
          122  + int k = ;
          123  + long long _ = LL;
          124  +END
          125  +CASE(7)
          126  + int a = ;
          127  + int b = ;
          128  + int numRows = ;
          129  + int numColumns = ;
          130  + int k = ;
          131  + long long _ = LL;
          132  +END
          133  +*/
          134  +}
          135  +// END CUT HERE

Added SRM/559-U/1B.cpp version [79806b5fc6258641]

            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  +typedef int vert;
           23  +typedef vector< vector<vert> > graph;
           24  +
           25  +class HatRack { public:
           26  + long long countWays(vector <int> knob1, vector <int> knob2)
           27  + {
           28  +  int N = knob1.size() + 1;
           29  +  graph G(N);
           30  +  for(int i=0; i<knob1.size(); ++i) {
           31  +   int u = knob1[i] - 1;
           32  +   int v = knob2[i] - 1;
           33  +   G[u].push_back(v);
           34  +   G[v].push_back(u);
           35  +  }
           36  +  memo.assign((N+1)*N*N, -1);
           37  +  LL total = 0;
           38  +  for(int root=0; root<N; ++root)
           39  +   total += solve(G, N, root);
           40  +  return total;
           41  + }
           42  +
           43  + LL solve(const graph& G, int N, vert root)
           44  + {
           45  +  return rec(G, N, N, root, 1);
           46  + }
           47  +
           48  + vector<LL> memo;
           49  + LL rec(const graph& G, const int N, int pre, int cur, int loc) {
           50  +  int key = (pre*N+cur)*N+(loc-1);
           51  +  if(memo[key] != -1)
           52  +   return memo[key];
           53  +
           54  +  vector<int> e_child;
           55  +  if(loc*2+0 <= N) e_child.push_back(loc*2+0);
           56  +  if(loc*2+1 <= N) e_child.push_back(loc*2+1);
           57  +
           58  +  vector<int> r_child;
           59  +  for(int i=0; i<G[cur].size(); ++i)
           60  +   if(G[cur][i] != pre)
           61  +    r_child.push_back(G[cur][i]);
           62  +
           63  +  if(e_child.size() != r_child.size())
           64  +   return memo[key] = 0;
           65  +
           66  +  LL total = 0;
           67  +  do {
           68  +   LL me = 1;
           69  +   for(int i=0; i<e_child.size(); ++i)
           70  +    me *= rec(G, N, cur, r_child[i], e_child[i]);
           71  +   total += me;
           72  +  } while( next_permutation(e_child.begin(), e_child.end()) );
           73  +  return memo[key] = total;
           74  + }
           75  +};
           76  +
           77  +// BEGIN CUT HERE
           78  +#include <ctime>
           79  +double start_time; string timer()
           80  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           81  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           82  + { os << "{ ";
           83  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           84  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           85  +void verify_case(const long long& Expected, const long long& Received) {
           86  + bool ok = (Expected == Received);
           87  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           88  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           89  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           90  +#define END  verify_case(_, HatRack().countWays(knob1, knob2));}
           91  +int main(){
           92  +
           93  +CASE(0)
           94  + int knob1_[] = {1};
           95  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
           96  + int knob2_[] = {2};
           97  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
           98  + long long _ = 2LL;
           99  +END
          100  +CASE(1)
          101  + int knob1_[] = {1,1};
          102  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          103  + int knob2_[] = {2,3};
          104  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          105  + long long _ = 2LL;
          106  +END
          107  +CASE(2)
          108  + int knob1_[] = {1,1,1,1};
          109  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          110  + int knob2_[] = {2,3,4,5};
          111  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          112  + long long _ = 0LL;
          113  +END
          114  +CASE(3)
          115  + int knob1_[] = {6,6,6,4,1};
          116  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          117  + int knob2_[] = {1,2,4,5,3};
          118  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          119  + long long _ = 0LL;
          120  +END
          121  +CASE(4)
          122  + int knob1_[] = {1,1,2,2,11,11,8,8,3,3,4,4,5};
          123  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          124  + int knob2_[] = {2,3,11,8,12,13,9,10,4,5,7,6,14};
          125  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          126  + long long _ = 16LL;
          127  +END
          128  +CASE(5)
          129  + int knob1_[] = {1,2,3,4,5,6,7,8,9};
          130  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          131  + int knob2_[] = {2,3,4,5,6,7,8,9,10};
          132  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          133  + long long _ = 0LL;
          134  +END
          135  +/*
          136  +CASE(6)
          137  + int knob1_[] = ;
          138  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          139  + int knob2_[] = ;
          140  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          141  + long long _ = LL;
          142  +END
          143  +CASE(7)
          144  + int knob1_[] = ;
          145  +   vector <int> knob1(knob1_, knob1_+sizeof(knob1_)/sizeof(*knob1_));
          146  + int knob2_[] = ;
          147  +   vector <int> knob2(knob2_, knob2_+sizeof(knob2_)/sizeof(*knob2_));
          148  + long long _ = LL;
          149  +END
          150  +*/
          151  +}
          152  +// END CUT HERE

Added SRM/559-U/1C-U.cpp version [7d4184f5c5d549e9]

            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 complex<double> CMP;
           20  +
           21  +struct Circle {
           22  + CMP o;
           23  + double r;
           24  +};
           25  +
           26  +bool line_circle(CMP la, CMP lb, CMP c, double r, CMP* p1, CMP* p2)
           27  +{
           28  + CMP v = (lb-la) / abs(lb-la);
           29  + CMP o = (c-la) / v;
           30  + if( abs(o.imag()) > r )
           31  +  return false;
           32  + double dx = sqrt(r*r - o.imag()*o.imag());
           33  + *p1 = la + (o.real()-dx)*v;
           34  + *p2 = la + (o.real()+dx)*v;
           35  + return true;
           36  +}
           37  +
           38  +class CircusTents { public:
           39  + double findMaximumDistance(vector <int> x, vector <int> y, vector <int> r)
           40  + {
           41  +  double f = r[0];
           42  +
           43  +  vector<Circle> cs;
           44  +  for(int i=1; i<x.size(); ++i) {
           45  +   Circle you = {CMP(x[1]-x[0], y[1]-y[0])/f, double(r[1])/f};
           46  +   cs.push_back(you);
           47  +  }
           48  +
           49  +  return solve(cs) * f;
           50  + }
           51  +
           52  + double solve(const vector<Circle>& cs)
           53  + {
           54  +  vector<double> args;
           55  +
           56  +  for(int i=0; i<cs.size(); ++i)
           57  +  for(int k=i+1; k<cs.size(); ++k) {
           58  +   CMP p = cs[i].o;
           59  +   CMP q = cs[k].o;
           60  +
           61  +   double len = abs(q-p);
           62  +   double mid = (len - cs[i].r - cs[k].r)/2+cs[i].r;
           63  +   CMP r = (q-p)/len*mid;
           64  +   CMP d = (q-p)/len*CMP(0,1);
           65  +   /// r + td is the splitting line.
           66  +
           67  +   CMP x1, x2;
           68  +   if( line_circle(r, r+d, CMP(0,0), 1.0, &x1, &x2) ) {
           69  +    args.push_back(arg(x1));
           70  +    args.push_back(arg(x2));
           71  +   }
           72  +  }
           73  +
           74  +  if(args.empty()) {
           75  +   args.push_back(0.0);
           76  +   args.push_back(1.0);
           77  +  }
           78  +  sort(args.begin(), args.end());
           79  +
           80  +  double best = 0.0;
           81  +  for(int i=0; i<args.size(); ++i) {
           82  +   double aL = args[i];
           83  +   double aR = (i+1==args.size() ? args[0]+M_PI/2 : args[i+1]);
           84  +
           85  +   double aC = (aL+aR) / 2;
           86  +   CMP p = polar(1.0, aC);
           87  +
           88  +   int close = -1; double close_d = 999999999;
           89  +   for(int k=0; k<cs.size(); ++k) {
           90  +    double d = abs(p - cs[k].o) - cs[k].r;
           91  +    if(d<close_d) {close=k, close_d=d;}
           92  +   }
           93  +
           94  +   CMP pL = polar(1.0, aL);
           95  +   CMP pR = polar(1.0, aR);
           96  +   CMP v = cs[close].o;
           97  +   pL /= v/abs(v);
           98  +   pR /= v/abs(v);
           99  +   double aaL = arg(pL);
          100  +   double aaR = arg(pR);
          101  +   double theA;
          102  +   if(aaL > aaR) {
          103  +    theA = M_PI;
          104  +   } else {
          105  +    theA = (abs(aaL)>abs(aaR) ? aaL : aaR);
          106  +   }
          107  +
          108  +   // distance from polar(1.0, theA) to Circ((abs(v),0), cs[close].r)
          109  +   // ... avoiding the two circle!
          110  +   double ddd = 0;
          111  +cerr<<polar(1.0, theA)<<endl;
          112  +   best = min(best, ddd);
          113  +  }
          114  +  return best;
          115  + }
          116  +};
          117  +
          118  +// BEGIN CUT HERE
          119  +#include <ctime>
          120  +double start_time; string timer()
          121  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          122  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          123  + { os << "{ ";
          124  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          125  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          126  +void verify_case(const double& Expected, const double& Received) {
          127  + bool ok = (abs(Expected - Received) < 1e-9);
          128  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          129  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          130  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          131  +#define END  verify_case(_, CircusTents().findMaximumDistance(x, y, r));}
          132  +int main(){
          133  +
          134  +CASE(0)
          135  + int x_[] = {0,3};
          136  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          137  + int y_[] = {0,0};
          138  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          139  + int r_[] = {1,1};
          140  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          141  + double _ = 3.7390603609952078;
          142  +END
          143  +CASE(1)
          144  + int x_[] = {0,3,-3,3,-3};
          145  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          146  + int y_[] = {0,3,3,-3,-3};
          147  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          148  + int r_[] = {1,1,1,1,1};
          149  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          150  + double _ = 2.6055512754639887;
          151  +END
          152  +CASE(2)
          153  + int x_[] = {3,7,7,7,3};
          154  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          155  + int y_[] = {4,6,1,-3,0};
          156  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          157  + int r_[] = {2,2,2,1,1};
          158  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          159  + double _ = 4.3264459099620725;
          160  +END
          161  +CASE(3)
          162  + int x_[] = {10,-1};
          163  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          164  + int y_[] = {0,0};
          165  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          166  + int r_[] = {8,2};
          167  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          168  + double _ = 24.63092458664212;
          169  +END
          170  +CASE(4)
          171  + int x_[] = {0,4,-4};
          172  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          173  + int y_[] = {0,4,-4};
          174  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          175  + int r_[] = {1,1,1};
          176  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          177  + double _ = 4.745474963675133;
          178  +END
          179  +/*
          180  +CASE(5)
          181  + int x_[] = ;
          182  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          183  + int y_[] = ;
          184  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          185  + int r_[] = ;
          186  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          187  + double _ = ;
          188  +END
          189  +CASE(6)
          190  + int x_[] = ;
          191  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          192  + int y_[] = ;
          193  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          194  + int r_[] = ;
          195  +   vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
          196  + double _ = ;
          197  +END
          198  +*/
          199  +}
          200  +// END CUT HERE