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

Added SRM/547-U/1A.cpp version [4250c24f458f28d7]

            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 Pillars { public:
           23  + double getExpectedLength(int w, int x, int y)
           24  + {
           25  +  if(x>y) swap(x,y);
           26  +
           27  +  double e = 0;
           28  +  int num = 1;
           29  +  for(int y_minus_x=1-x; y_minus_x<=y-1; ++y_minus_x) {
           30  +   e += hypot(y_minus_x, w) * num;
           31  +   if(y_minus_x<0)
           32  +    ++num;
           33  +   else if(y_minus_x >= y-x)
           34  +    --num;
           35  +  }
           36  +  return e/y/x;
           37  + }
           38  +};
           39  +
           40  +// BEGIN CUT HERE
           41  +#include <ctime>
           42  +double start_time; string timer()
           43  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           44  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           45  + { os << "{ ";
           46  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           47  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           48  +void verify_case(const double& Expected, const double& Received) {
           49  + bool ok = (abs(Expected - Received) < 1e-9);
           50  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           51  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           52  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           53  +#define END  verify_case(_, Pillars().getExpectedLength(w, x, y));}
           54  +int main(){
           55  +CASE(0)
           56  + int w = 1;
           57  + int x = 1;
           58  + int y = 1;
           59  + double _ = 1.0;
           60  +END
           61  +CASE(1)
           62  + int w = 1;
           63  + int x = 5;
           64  + int y = 1;
           65  + double _ = 2.387132965131785;
           66  +END
           67  +CASE(1)
           68  + int w = 1;
           69  + int x = 1;
           70  + int y = 5;
           71  + double _ = 2.387132965131785;
           72  +END
           73  +CASE(2)
           74  + int w = 2;
           75  + int x = 3;
           76  + int y = 15;
           77  + double _ = 6.737191281760445;
           78  +END
           79  +CASE(2)
           80  + int w = 2;
           81  + int x = 15;
           82  + int y = 3;
           83  + double _ = 6.737191281760445;
           84  +END
           85  +CASE(3)
           86  + int w = 10;
           87  + int x = 15;
           88  + int y = 23;
           89  + double _ = 12.988608956320535;
           90  +END
           91  +CASE(3)
           92  + int w = 10;
           93  + int x = 23;
           94  + int y = 15;
           95  + double _ = 12.988608956320535;
           96  +END
           97  +CASE(4)
           98  + int w = 1000;
           99  + int x = 100000;
          100  + int y = 100000;
          101  + double _ = -1;
          102  +END
          103  +CASE(5)
          104  + int w = 1;
          105  + int x = 1;
          106  + int y = 1;
          107  + double _ = 1;
          108  +END
          109  +
          110  +}
          111  +// END CUT HERE

Added SRM/547-U/1B.cpp version [9d97bb46a523cc67]

            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 RectangularSum { public:
           23  + long long minimalArea(int height_, int width_, long long S)
           24  + {
           25  +  LL H = height_;
           26  +  LL W = width_;
           27  +  static const LL INF = 0x7fffffffffffffffLL;
           28  +  LL best = INF;
           29  +
           30  +  vector<LL> divs;
           31  +  for(LL x=1; x*x<=2*S; ++x)
           32  +   if(2*S%x==0) {
           33  +    divs.push_back(x);
           34  +    divs.push_back(2*S/x);
           35  +   }
           36  +
           37  +  // sum = L1 + (L1 + wX) + (L1 + 2wX) + ... + (L1 + (Y-1)wX)
           38  +  //     = L1*Y + wX(Y-1)Y/2
           39  +  //     = (L1+wX(Y-1)/2) * Y
           40  +  // L1 = p + (p+1) + ... + (p+X-1)
           41  +  //    = p*X + X(X-1)/2
           42  +  //
           43  +  // sum = (p + (X-1)/2 + w(Y-1)/2) * X * Y
           44  +  // 2sum = (2p + X-1 + w(Y-1)) * X * Y
           45  +
           46  +  for(int i=0; i<divs.size(); ++i) {
           47  +   LL Y = divs[i];
           48  +   if(Y<=H)
           49  +   {
           50  +    LL R = (2*S)/Y;
           51  +    for(int j=0; j<divs.size(); ++j) {
           52  +     LL X = divs[j];
           53  +     if(X<=W && R%X == 0)
           54  +     {
           55  +      LL T = R/X;
           56  +      LL twoP = T - (X-1) - W*(Y-1);
           57  +      if( (twoP&1) == 1 )
           58  +       continue;
           59  +      LL P = twoP/2;
           60  +      if( P<0 || H*W<=P )
           61  +       continue;
           62  +      LL x = P%W;
           63  +      LL y = P/W;
           64  +      if( x+X<=W && y+Y<=H ) {
           65  +
           66  +       best = min(best, X*Y);
           67  +      }
           68  +     }
           69  +    }
           70  +   }
           71  +  }
           72  +  return best == INF ? -1 : best;
           73  + }
           74  +};
           75  +
           76  +// BEGIN CUT HERE
           77  +#include <ctime>
           78  +double start_time; string timer()
           79  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           80  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           81  + { os << "{ ";
           82  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           83  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           84  +void verify_case(const long long& Expected, const long long& Received) {
           85  + bool ok = (Expected == Received);
           86  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           87  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           88  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           89  +#define END  verify_case(_, RectangularSum().minimalArea(height, width, S));}
           90  +int main(){
           91  +
           92  +CASE(0)
           93  + int height = 2;
           94  + int width = 3;
           95  + long long S = 8LL;
           96  + long long _ = 4LL;
           97  +END
           98  +CASE(1)
           99  + int height = 3;
          100  + int width = 3;
          101  + long long S = 10LL;
          102  + long long _ = -1LL;
          103  +END
          104  +CASE(2)
          105  + int height = 3;
          106  + int width = 3;
          107  + long long S = 36LL;
          108  + long long _ = 9LL;
          109  +END
          110  +CASE(3)
          111  + int height = 25;
          112  + int width = 25;
          113  + long long S = 16000LL;
          114  + long long _ = 32LL;
          115  +END
          116  +CASE(4)
          117  + int height = 1000000;
          118  + int width = 1000000;
          119  + long long S = 1000000000000LL;
          120  + long long _ = 2LL;
          121  +END
          122  +CASE(5)
          123  + int height = 1000000;
          124  + int width = 1000000;
          125  + long long S = 123456789LL;
          126  + long long _ = -999LL;
          127  +END
          128  +CASE(6)
          129  + int height = 2;
          130  + int width = 3;
          131  + long long S = 6LL;
          132  + long long _ = 4LL;
          133  +END
          134  +
          135  +}
          136  +// END CUT HERE