Overview
| SHA1 Hash: | fa5fb91affdc936535440b8a3c719dc23f2e9728 |
|---|---|
| Date: | 2011-12-28 15:25:19 |
| User: | kinaba |
| Comment: | 1B |
| 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
Deleted SRM/526.5-U/1B-U.cpp version [0722a98dbeb899c2]
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 #ifdef __GNUC__ < 19 #include <ext/hash_map> < 20 #define unordered_map __gnu_cxx::hash_map < 21 #else < 22 #include <unordered_map> < 23 #endif < 24 using namespace std; < 25 typedef long long LL; < 26 typedef complex<double> CMP; < 27 < 28 class MagicBlizzard { public: < 29 double expectation(vector <int> range, vector <int> amount) < 30 { < 31 map<LL,int> ram; < 32 for(int i=0; i<range.size(); ++i) < 33 ram[range[i]] += amount[i]; < 34 vector< pair<LL,int> > ra(ram.begin(), ram.end()); < 35 int all = accumulate(amount.begin(), amount.end(), 0); < 36 < 37 double e = 0; < 38 for(int i=0; i<ra.size(); ++i) < 39 { < 40 LL r = ra[i].first; < 41 int a = ra[i].second; < 42 LL r_area = (2*r+1)*(2*r+1) - (i==0 ? 0 : (2*ra[i-1].fir < 43 for(int sf=0; sf<=all; ++sf) < 44 e += rec(ra, i, sf, all) * r_area * sf * sf; < 45 all -= a; < 46 } < 47 return e; < 48 } < 49 < 50 map<pair<int,int>, double> memo; < 51 double rec(vector< pair<LL,int> >& ra, int i, int snow_fall, int all) < 52 { < 53 if( i == ra.size() ) < 54 return snow_fall == 0 ? 1.0 : 0.0; < 55 if( all < snow_fall ) < 56 return 0.0; < 57 < 58 pair<int,int> key(i, snow_fall); < 59 if( memo.count(key) ) < 60 return memo[key]; < 61 < 62 LL r = ra[i].first; < 63 int a = ra[i].second; < 64 double p1 = double(1)/((2*r+1)*(2*r+1)); < 65 double p0 = 1 - p1; < 66 // (p0 #0 + p1 #1)^a < 67 double csum = 0; < 68 double Cak = 1; < 69 for(int k=0; k<=min(a, snow_fall); ++k) < 70 { < 71 // coord of ^k < 72 // C(a,k) p1^k p0^(a-k) < 73 double c = Cak * pow(p1,k) * pow(p0,a-k); < 74 csum += c * rec(ra, i+1, snow_fall-k, all-a); < 75 < 76 Cak = Cak * (a-k) / (k+1); < 77 } < 78 return memo[key] = csum; < 79 } < 80 }; < 81 < 82 // BEGIN CUT HERE < 83 #include <ctime> < 84 double start_time; string timer() < 85 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 86 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 87 { os << "{ "; < 88 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 89 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 90 void verify_case(const double& Expected, const double& Received) { < 91 bool ok = (abs(Expected - Received) < 1e-9); < 92 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 93 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 94 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 95 #define END verify_case(_, MagicBlizzard().expectation(range, amount));} < 96 int main(){ < 97 < 98 CASE(0) < 99 int range_[] = {1,0}; < 100 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 101 int amount_[] = {1,1}; < 102 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 103 double _ = 2.2222222222222223; < 104 END < 105 CASE(1) < 106 int range_[] = {1,0}; < 107 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 108 int amount_[] = {2,1}; < 109 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 110 double _ = 3.666666666666667; < 111 END < 112 CASE(2) < 113 int range_[] = {5,2,6,5}; < 114 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 115 int amount_[] = {1,2,2,3}; < 116 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 117 double _ = 8.46525111252384; < 118 END < 119 CASE(3) < 120 int range_[] = {7,11,2,13,3,19,5,17}; < 121 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 122 int amount_[] = {16,8,4,15,12,9,10,6}; < 123 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 124 double _ = 98.55659436211914; < 125 END < 126 CASE(4) < 127 int range_[] = {0,0,0,0,0,0,0,0,0,0}; < 128 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 129 int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,1 < 130 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 131 double _ = 1.0E10; < 132 END < 133 CASE(5) < 134 int range_[] = {1}; < 135 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 136 int amount_[] = {100}; < 137 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 138 double _ = 10000; < 139 END < 140 CASE(6) < 141 int range_[] = { < 142 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 143 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 144 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 145 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 146 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 147 }; < 148 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); < 149 int amount_[] = { < 150 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 151 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 152 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 153 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 154 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 155 }; < 156 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) < 157 double _ = -1; < 158 END < 159 < 160 } < 161 // END CUT HERE <
Modified SRM/526.5-U/1B.cpp from [0722a98dbeb899c2] to [6a80b80254e8b111].
24 using namespace std; 24 using namespace std; 25 typedef long long LL; 25 typedef long long LL; 26 typedef complex<double> CMP; 26 typedef complex<double> CMP; 27 27 28 class MagicBlizzard { public: 28 class MagicBlizzard { public: 29 double expectation(vector <int> range, vector <int> amount) 29 double expectation(vector <int> range, vector <int> amount) 30 { 30 { 31 map<LL,int> ram; | 31 vector< pair<int,int> > ar; 32 for(int i=0; i<range.size(); ++i) 32 for(int i=0; i<range.size(); ++i) 33 ram[range[i]] += amount[i]; | 33 ar.push_back(make_pair(range[i], amount[i])); 34 vector< pair<LL,int> > ra(ram.begin(), ram.end()); < 35 int all = accumulate(amount.begin(), amount.end(), 0); < 36 34 > 35 sort(ar.begin(), ar.end()); 37 double e = 0; | 36 double total = 0.0; > 37 int cnt = 0; 38 for(int i=0; i<ra.size(); ++i) | 38 for(int i=0; i<ar.size(); ++i) 39 { < 40 LL r = ra[i].first; < 41 int a = ra[i].second; | 39 for(int _=0; _<ar[i].second; ++_) 42 LL r_area = (2*r+1)*(2*r+1) - (i==0 ? 0 : (2*ra[i-1].fir | 40 total += 2.0 * (cnt++) / (ar[i].first*2+1) / (ar 43 for(int sf=0; sf<=all; ++sf) < 44 e += rec(ra, i, sf, all) * r_area * sf * sf; < 45 all -= a; < 46 } < 47 return e; | 41 return total; 48 } < 49 < 50 map<pair<int,int>, double> memo; < 51 double rec(vector< pair<LL,int> >& ra, int i, int snow_fall, int all) < 52 { < 53 if( i == ra.size() ) < 54 return snow_fall == 0 ? 1.0 : 0.0; < 55 if( all < snow_fall ) < 56 return 0.0; < 57 < 58 pair<int,int> key(i, snow_fall); < 59 if( memo.count(key) ) < 60 return memo[key]; < 61 < 62 LL r = ra[i].first; < 63 int a = ra[i].second; < 64 double p1 = double(1)/((2*r+1)*(2*r+1)); < 65 double p0 = 1 - p1; < 66 // (p0 #0 + p1 #1)^a < 67 double csum = 0; < 68 double Cak = 1; < 69 for(int k=0; k<=min(a, snow_fall); ++k) < 70 { < 71 // coord of ^k < 72 // C(a,k) p1^k p0^(a-k) < 73 double c = Cak * pow(p1,k) * pow(p0,a-k); < 74 csum += c * rec(ra, i+1, snow_fall-k, all-a); < 75 < 76 Cak = Cak * (a-k) / (k+1); < 77 } < 78 return memo[key] = csum; < 79 } 42 } 80 }; 43 }; 81 44 82 // BEGIN CUT HERE 45 // BEGIN CUT HERE 83 #include <ctime> 46 #include <ctime> 84 double start_time; string timer() 47 double start_time; string timer() 85 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) ................................................................................................................................................................................ 126 CASE(4) 89 CASE(4) 127 int range_[] = {0,0,0,0,0,0,0,0,0,0}; 90 int range_[] = {0,0,0,0,0,0,0,0,0,0}; 128 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 91 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 129 int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,1 92 int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,1 130 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) 93 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) 131 double _ = 1.0E10; 94 double _ = 1.0E10; 132 END 95 END > 96 /* 133 CASE(5) 97 CASE(5) 134 int range_[] = {1}; | 98 int range_[] = ; 135 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 99 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 136 int amount_[] = {100}; | 100 int amount_[] = ; 137 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) 101 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) 138 double _ = 10000; | 102 double _ = ; 139 END 103 END 140 CASE(6) 104 CASE(6) 141 int range_[] = { | 105 int range_[] = ; 142 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 143 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 144 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 145 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 146 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 147 }; < 148 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 106 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 149 int amount_[] = { | 107 int amount_[] = ; 150 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 151 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 152 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 153 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 154 10000,10000,10000,10000,10000,10000,10000,10000,10000,10000, < 155 }; < 156 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) 108 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)) 157 double _ = -1; | 109 double _ = ; 158 END 110 END 159 < > 111 */ 160 } 112 } 161 // END CUT HERE 113 // END CUT HERE