Overview
| SHA1 Hash: | 854327905ba915025b676993a860d7e5c4660e25 |
|---|---|
| Date: | 2014-12-27 16:09:00 |
| User: | kinaba |
| Comment: | 642 |
| 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/642-U/1A.cpp version [9ba46fb7593c506a]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class WaitingForBus { public: > 23 double whenWillBusArrive(vector <int> time, vector <int> prob, int s) > 24 { > 25 const int WAIT_TIME_MAX = 100000; > 26 > 27 deque<double> p(WAIT_TIME_MAX+1, 0.0); > 28 p[0] = 1.0; > 29 for(int t=1; t<=s; ++t) { > 30 double p0 = p[0]; > 31 p.pop_front(); > 32 p.push_back(0.0); > 33 for(int i=0; i<time.size(); ++i) > 34 p[time[i]-1] += p0 * prob[i] / 100; > 35 } > 36 > 37 double ans = 0.0; > 38 for(int t=0; t<=WAIT_TIME_MAX; ++t) > 39 ans += t * p[t]; > 40 return ans; > 41 } > 42 }; > 43 > 44 // BEGIN CUT HERE > 45 #include <ctime> > 46 double start_time; string timer() > 47 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 48 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 49 { os << "{ "; > 50 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 51 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 52 void verify_case(const double& Expected, const double& Received) { > 53 bool ok = (abs(Expected - Received) < 1e-9); > 54 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 55 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 56 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 57 #define END verify_case(_, WaitingForBus().whenWillBusArrive(time, prob, s) > 58 int main(){ > 59 > 60 CASE(0) > 61 int time_[] = {5,100}; > 62 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 63 int prob_[] = {90,10}; > 64 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 65 int s = 5; > 66 double _ = 9.5; > 67 END > 68 CASE(1) > 69 int time_[] = {5}; > 70 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 71 int prob_[] = {100}; > 72 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 73 int s = 101; > 74 double _ = 4.0; > 75 END > 76 CASE(2) > 77 int time_[] = {5,10}; > 78 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 79 int prob_[] = {50,50}; > 80 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 81 int s = 88888; > 82 double _ = 3.666666666666667; > 83 END > 84 CASE(3) > 85 int time_[] = {1,2,3,4}; > 86 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 87 int prob_[] = {10,20,30,40}; > 88 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 89 int s = 1000; > 90 double _ = 1.166666666666667; > 91 END > 92 CASE(4) > 93 int time_[] = {10,100,1000,10000,100000}; > 94 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 95 int prob_[] = {90,4,3,2,1}; > 96 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 97 int s = 100000; > 98 double _ = 21148.147303578935; > 99 END > 100 /* > 101 CASE(5) > 102 int time_[] = ; > 103 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 104 int prob_[] = ; > 105 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 106 int s = ; > 107 double _ = ; > 108 END > 109 CASE(6) > 110 int time_[] = ; > 111 vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); > 112 int prob_[] = ; > 113 vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); > 114 int s = ; > 115 double _ = ; > 116 END > 117 */ > 118 } > 119 // END CUT HERE
Added SRM/642-U/1C-U.cpp version [a5d1138e452eadf3]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 template<typename T> > 23 struct DP2 > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2(int N1, int N2, const T& t = T()) > 28 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 29 T& operator()(int i1, int i2) > 30 { return data[ (i1*N2)+i2 ]; } > 31 void swap(DP2& rhs) > 32 { data.swap(rhs.data); } > 33 }; > 34 > 35 template<typename T> > 36 struct DP3 > 37 { > 38 int N1, N2, N3; > 39 vector<T> data; > 40 DP3(int N1, int N2, int N3, const T& t = T()) > 41 : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size() > 42 T& operator()(int i1, int i2, int i3) > 43 { return data[ ((i1*N2)+i2)*N3+i3 ]; } > 44 void swap(DP3& rhs) > 45 { data.swap(rhs.data); } > 46 }; > 47 > 48 class WheelofFortune { public: > 49 double maxExpectedValue(int N, vector <int> s) > 50 { > 51 const int SCORE_MAX = s.size(); > 52 > 53 // wlog Alice always declares "0". > 54 > 55 // ps(i+1, a) := probability that "0" is covered |a| times after > 56 // es(i+1, a) := expected score distrobution > 57 DP2<double> ps(s.size()+1, SCORE_MAX+1, 0.0); > 58 DP3<double> es(s.size()+1, SCORE_MAX+1, N, 0.0); > 59 ps(0, 0) = 1.0; > 60 > 61 vector<vector<double>> memo1(N+1, vector<double>(N, -1)); > 62 vector<vector<double>> memo2(N+1, vector<double>(N, -1)); > 63 > 64 for(int i=0; i<s.size(); ++i) > 65 for(int a=0; a<=SCORE_MAX; ++a) { > 66 const double q = double(s[i])/N; > 67 > 68 ps(i+1, a) = (1-q) * ps(i, a) + q * (a?ps(i, a-1):0.0); > 69 for(int cell=0; cell<N; ++cell) { > 70 double zero_t = zero_cover_times(N, s[i], cell, > 71 double non_zero_t = non_zero_cover_times(N, s[i] > 72 > 73 es(i+1, a, cell) = > 74 (a?ps(i, a-1):0.0) * q * (es(i, a-1, c > 75 + ps(i, a) * (1-q) * (es(i, a, cell) + d > 76 } > 77 } > 78 > 79 double ans = 0.0; > 80 for(int a=0; a<=SCORE_MAX; ++a) if(ps(s.size(), a)) { > 81 // Under the condition that "0" is covered exactly |a| t > 82 // what is the optimal choice for Bob? > 83 > 84 // Bob takes the max expected score cell (but 0). > 85 double bob_best = 0.0; > 86 for(int cell=1; cell<N; ++cell) > 87 bob_best = max(bob_best, es(s.size(), a, cell)); > 88 > 89 // accumulate > 90 ans += ps(s.size(), a) * (a+bob_best); > 91 } > 92 return ans; > 93 } > 94 > 95 double zero_cover_times(int N, int s, int cell, vector<vector<double>>& > 96 { > 97 if(memo[s][cell] >= 0) > 98 return memo[s][cell]; > 99 > 100 int cnt = 0, tot = 0; > 101 for(int b=0; b<N; ++b) { > 102 if(covers(N, b, s, 0)) > 103 ++tot; > 104 if(covers(N, b, s, 0) && covers(N, b, s, cell)) > 105 ++cnt; > 106 } > 107 return memo[s][cell] = double(cnt)/tot; > 108 } > 109 > 110 double non_zero_cover_times(int N, int s, int cell, vector<vector<double > 111 { > 112 if(memo[s][cell] >= 0) > 113 return memo[s][cell]; > 114 > 115 int cnt = 0, tot=0; > 116 for(int b=0; b<N; ++b) { > 117 if(!covers(N, b, s, 0)) > 118 ++tot; > 119 if(!covers(N, b, s, 0) && covers(N, b, s, cell)) > 120 ++cnt; > 121 } > 122 return memo[s][cell] = double(cnt)/tot; > 123 } > 124 > 125 bool covers(int N, int b, int s, int c) > 126 { > 127 if(b<=c && c<=b+s-1) > 128 return true; > 129 if(0<=c && c<=b+s-1-N) > 130 return true; > 131 return false; > 132 } > 133 }; > 134 > 135 // BEGIN CUT HERE > 136 #include <ctime> > 137 double start_time; string timer() > 138 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 139 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 140 { os << "{ "; > 141 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 142 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 143 void verify_case(const double& Expected, const double& Received) { > 144 bool ok = (abs(Expected - Received) < 1e-9); > 145 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 146 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 147 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 148 #define END verify_case(_, WheelofFortune().maxExpectedValue(N, s));} > 149 int main(){ > 150 > 151 CASE(0) > 152 int N = 4; > 153 int s_[] = {2}; > 154 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 155 double _ = 1.25; > 156 END > 157 CASE(1) > 158 int N = 6; > 159 int s_[] = {1,1,1,1,1,1}; > 160 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 161 double _ = 2.0000000000000004; > 162 END > 163 CASE(2) > 164 int N = 20; > 165 int s_[] = {1,20,1,20,1}; > 166 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 167 double _ = 4.299999999999999; > 168 END > 169 CASE(3) > 170 int N = 10; > 171 int s_[] = {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7, > 172 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 173 double _ = 31.973469385798197; > 174 END > 175 CASE(4) > 176 int N = 15; > 177 int s_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; > 178 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 179 double _ = 16.691531334568044; > 180 END > 181 /* > 182 CASE(5) > 183 int N = ; > 184 int s_[] = ; > 185 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 186 double _ = ; > 187 END > 188 CASE(6) > 189 int N = ; > 190 int s_[] = ; > 191 vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_)); > 192 double _ = ; > 193 END > 194 */ > 195 } > 196 // END CUT HERE