Overview
| SHA1 Hash: | fca716a31cce19a7f26cd10baff7c6380c35e973 |
|---|---|
| Date: | 2011-07-26 13:03:27 |
| User: | kinaba |
| Comment: | 513 |
| 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/513-U/1A.cpp version [d303488aa6248209]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const int MODVAL = 1000000009; > 23 > 24 class YetAnotherIncredibleMachine { public: > 25 int countWays(vector <int> platformMount, vector <int> platformLength, v > 26 { > 27 LL total = 1; > 28 for(int p=0; p<platformLength.size(); ++p) > 29 { > 30 vector< pair<int,int> > q; > 31 int len = platformLength[p]; > 32 int pos = platformMount[p]; > 33 q.push_back( make_pair(pos-len, pos) ); > 34 for(int i=0; i<balls.size(); ++i) > 35 avoid( balls[i], q, len ); > 36 > 37 int cnt = 0; > 38 for(int i=0; i<q.size(); ++i) > 39 cnt += q[i].second - q[i].first + 1; > 40 total = total * cnt % MODVAL; > 41 } > 42 return int(total); > 43 } > 44 > 45 void avoid(int x, vector< pair<int,int> >& q, int len) > 46 { > 47 vector< pair<int,int> > q2; > 48 for(int i=0; i<q.size(); ++i) > 49 if( q[i].second+len < x || x < q[i].first ) > 50 q2.push_back( q[i] ); > 51 else { > 52 int L = q[i].first; > 53 int R = q[i].second; > 54 if( L<=x-len-1 ) > 55 q2.push_back( make_pair(L, x-len-1) ); > 56 if( x+1<=R ) > 57 q2.push_back( make_pair(x+1, R) ); > 58 } > 59 q.swap(q2); > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const int& Expected, const int& Received) { > 72 bool ok = (Expected == Received); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, YetAnotherIncredibleMachine().countWays(platform > 77 int main(){ > 78 > 79 CASE(0) > 80 int platformMount_[] = {7}; > 81 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 82 int platformLength_[] = {10}; > 83 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 84 int balls_[] = {3,4}; > 85 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 86 int _ = 3; > 87 END > 88 CASE(1) > 89 int platformMount_[] = {1,4}; > 90 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 91 int platformLength_[] = {3,3}; > 92 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 93 int balls_[] = {2,7}; > 94 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 95 int _ = 1; > 96 END > 97 CASE(2) > 98 int platformMount_[] = {4,4,4}; > 99 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 100 int platformLength_[] = {10,9,8}; > 101 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 102 int balls_[] = {1,100}; > 103 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 104 int _ = 27; > 105 END > 106 CASE(3) > 107 int platformMount_[] = {0}; > 108 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 109 int platformLength_[] = {1}; > 110 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 111 int balls_[] = {0}; > 112 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 113 int _ = 0; > 114 END > 115 CASE(4) > 116 int platformMount_[] = {100, -4215, 251}; > 117 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 118 int platformLength_[] = {400, 10000, 2121}; > 119 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 120 int balls_[] = {5000, 2270, 8512, 6122}; > 121 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 122 int _ = 250379170; > 123 END > 124 /* > 125 CASE(5) > 126 int platformMount_[] = ; > 127 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 128 int platformLength_[] = ; > 129 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 130 int balls_[] = ; > 131 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 132 int _ = ; > 133 END > 134 CASE(6) > 135 int platformMount_[] = ; > 136 vector <int> platformMount(platformMount_, platformMount_+sizeof(platf > 137 int platformLength_[] = ; > 138 vector <int> platformLength(platformLength_, platformLength_+sizeof(pl > 139 int balls_[] = ; > 140 vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_)); > 141 int _ = ; > 142 END > 143 */ > 144 } > 145 // END CUT HERE
Added SRM/513-U/1B.cpp version [d2075b0ec6259c1a]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 template<typename T> > 23 struct DP2 > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2(int N1, int N2, const T& t = T()) > 28 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 29 T& operator()(int i1, int i2) > 30 { return data[ (i1*N2)+i2 ]; } > 31 void swap(DP2& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 class PerfectMemory { public: > 36 double getExpectation(int N, int M) > 37 { > 38 const int C = N*M; > 39 DP2<double> dp(C+1, C+1); > 40 for(int u=0; u<=C; ++u) > 41 for(int k=0; k<=C; ++k) if( (u+k)%2==0 && k+u<=C ) > 42 { > 43 if( k > u ) > 44 { > 45 dp(k,u) = 1 + dp(k-2,u); > 46 } > 47 else if( k == u ) > 48 { > 49 if( k==0 && u==0 ) > 50 dp(k,u) = 0; > 51 else > 52 dp(k,u) = 1 + dp(k-1, u-1); > 53 } > 54 else // k < u > 55 { > 56 dp(k,u) = 1; > 57 > 58 double pFirstIsKnown = double(k) / u; > 59 double pSecondIsIt = double(1) / (u-1); > 60 if(k) > 61 dp(k,u) += pFirstIsKnown * dp(k- > 62 double pSecondIsThat = double(k) / (u-1) > 63 dp(k,u) += (1-pFirstIsKnown) * pSecondIs > 64 dp(k,u) += (1-pFirstIsKnown) * (1-pSecon > 65 dp(k,u) += (1-pFirstIsKnown) * pSecondIs > 66 } > 67 // cerr << k << " " << u << " " << dp(k,u) << endl; > 68 } > 69 return dp(0,C); > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const double& Expected, const double& Received) { > 82 bool ok = (abs(Expected - Received) < 1e-9); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, PerfectMemory().getExpectation(N, M));} > 87 int main(){ > 88 > 89 CASE(0) > 90 int N = 1; > 91 int M = 2; > 92 double _ = 1.0; > 93 END > 94 CASE(1) > 95 int N = 2; > 96 int M = 2; > 97 double _ = 2.6666666666666665; > 98 END > 99 CASE(2) > 100 int N = 2; > 101 int M = 3; > 102 double _ = 4.333333333333334; > 103 END > 104 CASE(3) > 105 int N = 4; > 106 int M = 4; > 107 double _ = 12.392984792984793; > 108 END > 109 /* > 110 CASE(4) > 111 int N = 50; > 112 int M = 50; > 113 double _ = -1; > 114 END > 115 CASE(5) > 116 int N = 2; > 117 int M = 1; > 118 double _ = 1.0; > 119 END > 120 */ > 121 } > 122 // END CUT HERE