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