Overview
| SHA1 Hash: | 1475bf9d413e0227188a06d16482d989c2a605c9 |
|---|---|
| Date: | 2012-10-31 13:54:55 |
| User: | kinaba |
| Comment: | 559 |
| 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/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) > 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 > 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() > 63 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 64 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 65 #define END verify_case(_, HyperKnight().countCells(a, b, numRows, numColum > 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) > 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 > 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() > 88 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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> > 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])/ > 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+ > 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 > 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) > 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 > 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() > 129 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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