Overview
| SHA1 Hash: | 226a3765521cb6298455c69ff02e880f1469bfdd |
|---|---|
| Date: | 2011-12-28 14:46:22 |
| 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
Name change from from SRM/526.5-U/1B.cpp to SRM/526.5-U/1B-U.cpp.
Deleted 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 <
Added SRM/526.5-U/2A.cpp version [85387e3cdd5302ba]
> 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 MagicStonesStore { public: > 29 string ableToDivide(int n) > 30 { > 31 return n==1 ? "NO" : "YES"; > 32 } > 33 }; > 34 > 35 // BEGIN CUT HERE > 36 #include <ctime> > 37 double start_time; string timer() > 38 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 39 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 40 { os << "{ "; > 41 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 42 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 43 void verify_case(const string& Expected, const string& Received) { > 44 bool ok = (Expected == Received); > 45 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 46 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 47 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 48 #define END verify_case(_, MagicStonesStore().ableToDivide(n));} > 49 int main(){ > 50 > 51 CASE(0) > 52 int n = 1; > 53 string _ = "NO"; > 54 END > 55 CASE(1) > 56 int n = 2; > 57 string _ = "YES"; > 58 END > 59 CASE(2) > 60 int n = 3; > 61 string _ = "YES"; > 62 END > 63 CASE(3) > 64 int n = 5; > 65 string _ = "YES"; > 66 END > 67 CASE(4) > 68 int n = ; > 69 string _ = ; > 70 END > 71 CASE(5) > 72 int n = ; > 73 string _ = ; > 74 END > 75 > 76 } > 77 // END CUT HERE
Added SRM/526.5-U/2C.cpp version [71780af0d20da0b9]
> 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 MagicNaming { public: > 29 int maxReindeers(string magicName) > 30 { > 31 return rec(magicName, 0, ""); > 32 } > 33 > 34 map<pair<int,string>, int> memo; > 35 int rec(const string& s, int i, const string& last) > 36 { > 37 if( i == s.size() ) > 38 return 0; > 39 pair<int,string> key(i, last); > 40 if( memo.count(key) ) > 41 return memo[key]; > 42 > 43 // a+b <= b+a, b+c <= c+b > 44 int score = -1; > 45 for(int e=i+1; e<=s.size(); ++e) { > 46 string t = s.substr(i, e-i); > 47 if( last+t <= t+last ) { > 48 int ss = rec(s, e, t); > 49 if( ss != -1 ) > 50 score = max(score, 1 + ss); > 51 } > 52 } > 53 return memo[key] = score; > 54 } > 55 }; > 56 > 57 // BEGIN CUT HERE > 58 #include <ctime> > 59 double start_time; string timer() > 60 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 61 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 62 { os << "{ "; > 63 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 64 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 65 void verify_case(const int& Expected, const int& Received) { > 66 bool ok = (Expected == Received); > 67 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 68 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 69 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 70 #define END verify_case(_, MagicNaming().maxReindeers(magicName));} > 71 int main(){ > 72 > 73 CASE(0) > 74 string magicName = "aba"; > 75 int _ = 2; > 76 END > 77 CASE(1) > 78 string magicName = "babbaba"; > 79 int _ = 2; > 80 END > 81 CASE(2) > 82 string magicName = "philosophersstone"; > 83 int _ = 5; > 84 END > 85 CASE(3) > 86 string magicName = "knuthmorrispratt"; > 87 int _ = 7; > 88 END > 89 CASE(4) > 90 string magicName = "acrushpetrtourist"; > 91 int _ = 7; > 92 END > 93 CASE(5) > 94 string magicName = "zzzzz"; > 95 int _ = 5; > 96 END > 97 /* > 98 CASE(6) > 99 string magicName = ; > 100 int _ = ; > 101 END > 102 CASE(7) > 103 string magicName = ; > 104 int _ = ; > 105 END > 106 */ > 107 } > 108 // END CUT HERE