Check-in [fa5fb91aff]
Not logged in
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
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].first+1)*(2*ra[i-1].first+1)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 93 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,10000}; 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 24 using namespace std; 25 25 typedef long long LL; 26 26 typedef complex<double> CMP; 27 27 28 28 class MagicBlizzard { public: 29 29 double expectation(vector <int> range, vector <int> amount) 30 30 { 31 - map<LL,int> ram; 31 + vector< pair<int,int> > ar; 32 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); 33 + ar.push_back(make_pair(range[i], amount[i])); 36 34 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].first+1)*(2*ra[i-1].first+1)); 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; 35 + sort(ar.begin(), ar.end()); 36 + double total = 0.0; 37 + int cnt = 0; 38 + for(int i=0; i<ar.size(); ++i) 39 + for(int _=0; _<ar[i].second; ++_) 40 + total += 2.0 * (cnt++) / (ar[i].first*2+1) / (ar[i].first*2+1) + 1; 41 + return total; 79 42 } 80 43 }; 81 44 82 45 // BEGIN CUT HERE 83 46 #include <ctime> 84 47 double start_time; string timer() 85 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ................................................................................ 126 89 CASE(4) 127 90 int range_[] = {0,0,0,0,0,0,0,0,0,0}; 128 91 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 129 92 int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}; 130 93 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); 131 94 double _ = 1.0E10; 132 95 END 96 +/* 133 97 CASE(5) 134 - int range_[] = {1}; 98 + int range_[] = ; 135 99 vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); 136 - int amount_[] = {100}; 100 + int amount_[] = ; 137 101 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); 138 - double _ = 10000; 102 + double _ = ; 139 103 END 140 104 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 - }; 105 + int range_[] = ; 148 106 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 - }; 107 + int amount_[] = ; 156 108 vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); 157 - double _ = -1; 109 + double _ = ; 158 110 END 159 - 111 +*/ 160 112 } 161 113 // END CUT HERE