Overview
| SHA1 Hash: | d921147eeff54b6a24436f8dda575e1a26a0b94e |
|---|---|
| Date: | 2012-07-01 02:10:21 |
| User: | kinaba |
| Comment: | 547 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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) > 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 > 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() > 51 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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) > 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 > 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() > 87 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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