Differences From Artifact [0722a98dbeb899c2]:
- File
SRM/526.5-U/1B-U.cpp
- 2011-12-28 14:46:22 - part of checkin [226a376552] on branch trunk - 526.5 (user: kinaba) [annotate]
- File
SRM/526.5-U/1B.cpp
- 2011-12-28 08:40:59 - part of checkin [99eae4eb4a] on branch trunk - 526.5 (user: kinaba) [annotate]
To Artifact [6a80b80254e8b111]:
- File
SRM/526.5-U/1B.cpp
- 2011-12-28 15:25:19 - part of checkin [fa5fb91aff] on branch trunk - 1B (user: kinaba) [annotate]
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