fa5fb91aff 2011-12-28 kinaba: #include <iostream> fa5fb91aff 2011-12-28 kinaba: #include <sstream> fa5fb91aff 2011-12-28 kinaba: #include <iomanip> fa5fb91aff 2011-12-28 kinaba: #include <vector> fa5fb91aff 2011-12-28 kinaba: #include <string> fa5fb91aff 2011-12-28 kinaba: #include <map> fa5fb91aff 2011-12-28 kinaba: #include <set> fa5fb91aff 2011-12-28 kinaba: #include <algorithm> fa5fb91aff 2011-12-28 kinaba: #include <numeric> fa5fb91aff 2011-12-28 kinaba: #include <iterator> fa5fb91aff 2011-12-28 kinaba: #include <functional> fa5fb91aff 2011-12-28 kinaba: #include <complex> fa5fb91aff 2011-12-28 kinaba: #include <queue> fa5fb91aff 2011-12-28 kinaba: #include <stack> fa5fb91aff 2011-12-28 kinaba: #include <cmath> fa5fb91aff 2011-12-28 kinaba: #include <cassert> fa5fb91aff 2011-12-28 kinaba: #include <cstring> fa5fb91aff 2011-12-28 kinaba: #ifdef __GNUC__ fa5fb91aff 2011-12-28 kinaba: #include <ext/hash_map> fa5fb91aff 2011-12-28 kinaba: #define unordered_map __gnu_cxx::hash_map fa5fb91aff 2011-12-28 kinaba: #else fa5fb91aff 2011-12-28 kinaba: #include <unordered_map> fa5fb91aff 2011-12-28 kinaba: #endif fa5fb91aff 2011-12-28 kinaba: using namespace std; fa5fb91aff 2011-12-28 kinaba: typedef long long LL; fa5fb91aff 2011-12-28 kinaba: typedef complex<double> CMP; fa5fb91aff 2011-12-28 kinaba: fa5fb91aff 2011-12-28 kinaba: class MagicBlizzard { public: fa5fb91aff 2011-12-28 kinaba: double expectation(vector <int> range, vector <int> amount) fa5fb91aff 2011-12-28 kinaba: { fa5fb91aff 2011-12-28 kinaba: vector< pair<int,int> > ar; fa5fb91aff 2011-12-28 kinaba: for(int i=0; i<range.size(); ++i) fa5fb91aff 2011-12-28 kinaba: ar.push_back(make_pair(range[i], amount[i])); fa5fb91aff 2011-12-28 kinaba: fa5fb91aff 2011-12-28 kinaba: sort(ar.begin(), ar.end()); fa5fb91aff 2011-12-28 kinaba: double total = 0.0; fa5fb91aff 2011-12-28 kinaba: int cnt = 0; fa5fb91aff 2011-12-28 kinaba: for(int i=0; i<ar.size(); ++i) fa5fb91aff 2011-12-28 kinaba: for(int _=0; _<ar[i].second; ++_) fa5fb91aff 2011-12-28 kinaba: total += 2.0 * (cnt++) / (ar[i].first*2+1) / (ar[i].first*2+1) + 1; fa5fb91aff 2011-12-28 kinaba: return total; fa5fb91aff 2011-12-28 kinaba: } fa5fb91aff 2011-12-28 kinaba: }; fa5fb91aff 2011-12-28 kinaba: fa5fb91aff 2011-12-28 kinaba: // BEGIN CUT HERE fa5fb91aff 2011-12-28 kinaba: #include <ctime> fa5fb91aff 2011-12-28 kinaba: double start_time; string timer() fa5fb91aff 2011-12-28 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } fa5fb91aff 2011-12-28 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) fa5fb91aff 2011-12-28 kinaba: { os << "{ "; fa5fb91aff 2011-12-28 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) fa5fb91aff 2011-12-28 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } fa5fb91aff 2011-12-28 kinaba: void verify_case(const double& Expected, const double& Received) { fa5fb91aff 2011-12-28 kinaba: bool ok = (abs(Expected - Received) < 1e-9); fa5fb91aff 2011-12-28 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; fa5fb91aff 2011-12-28 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } fa5fb91aff 2011-12-28 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); fa5fb91aff 2011-12-28 kinaba: #define END verify_case(_, MagicBlizzard().expectation(range, amount));} fa5fb91aff 2011-12-28 kinaba: int main(){ fa5fb91aff 2011-12-28 kinaba: fa5fb91aff 2011-12-28 kinaba: CASE(0) fa5fb91aff 2011-12-28 kinaba: int range_[] = {1,0}; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = {1,1}; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = 2.2222222222222223; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: CASE(1) fa5fb91aff 2011-12-28 kinaba: int range_[] = {1,0}; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = {2,1}; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = 3.666666666666667; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: CASE(2) fa5fb91aff 2011-12-28 kinaba: int range_[] = {5,2,6,5}; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = {1,2,2,3}; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = 8.46525111252384; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: CASE(3) fa5fb91aff 2011-12-28 kinaba: int range_[] = {7,11,2,13,3,19,5,17}; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = {16,8,4,15,12,9,10,6}; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = 98.55659436211914; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: CASE(4) fa5fb91aff 2011-12-28 kinaba: int range_[] = {0,0,0,0,0,0,0,0,0,0}; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = 1.0E10; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: /* fa5fb91aff 2011-12-28 kinaba: CASE(5) fa5fb91aff 2011-12-28 kinaba: int range_[] = ; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = ; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = ; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: CASE(6) fa5fb91aff 2011-12-28 kinaba: int range_[] = ; fa5fb91aff 2011-12-28 kinaba: vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_)); fa5fb91aff 2011-12-28 kinaba: int amount_[] = ; fa5fb91aff 2011-12-28 kinaba: vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_)); fa5fb91aff 2011-12-28 kinaba: double _ = ; fa5fb91aff 2011-12-28 kinaba: END fa5fb91aff 2011-12-28 kinaba: */ fa5fb91aff 2011-12-28 kinaba: } fa5fb91aff 2011-12-28 kinaba: // END CUT HERE