Overview
| SHA1 Hash: | 99eae4eb4a0600e81fe136a14dc280932de4b8e6 |
|---|---|
| Date: | 2011-12-28 08:40:59 |
| User: | kinaba |
| Comment: | 526.5 |
| 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
Added SRM/526.5-U/1A.cpp version [577cfc25d3b1c3b9]
> 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 MagicCandy { public: > 29 int whichOne(int n) > 30 { > 31 int r = n; > 32 while( n > 1 ) { > 33 int sn = int(sqrt(n)); > 34 r -= (sn*sn == n); > 35 n -= sn; > 36 } > 37 return r; > 38 } > 39 }; > 40 > 41 // BEGIN CUT HERE > 42 #include <ctime> > 43 double start_time; string timer() > 44 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 45 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 46 { os << "{ "; > 47 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 48 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 49 void verify_case(const int& Expected, const int& Received) { > 50 bool ok = (Expected == Received); > 51 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 52 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 53 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 54 #define END verify_case(_, MagicCandy().whichOne(n));} > 55 int main(){ > 56 CASE(0) > 57 int n = 5; > 58 int _ = 5; > 59 END > 60 CASE(1) > 61 int n = 9; > 62 int _ = 7; > 63 END > 64 CASE(2) > 65 int n = 20; > 66 int _ = 17; > 67 END > 68 CASE(3) > 69 int n = 5265; > 70 int _ = 5257; > 71 END > 72 CASE(4) > 73 int n = 20111223; > 74 int _ = 20110741; > 75 END > 76 /* > 77 CASE(5) > 78 int n = 1; > 79 int _ = 1; > 80 END > 81 CASE(6) > 82 int n = ; > 83 int _ = ; > 84 END > 85 CASE(7) > 86 int n = ; > 87 int _ = ; > 88 END > 89 */ > 90 } > 91 // END CUT HERE
Added SRM/526.5-U/1B.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