• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           55  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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)<(1<<28)); }
           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()*sizeof(T)<(1<<28)); }
           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 i-th try.
           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, memo1);
           71  +    double non_zero_t = non_zero_cover_times(N, s[i], cell, memo2);
           72  +
           73  +    es(i+1, a, cell) =
           74  +       (a?ps(i, a-1):0.0) * q * (es(i, a-1, cell) + double(zero_t))
           75  +     + ps(i, a) * (1-q) * (es(i, a, cell) + double(non_zero_t));
           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| times,
           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>>& memo)
           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>>& memo)
          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) << " msec)"; return os.str(); }
          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 os; }
          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() << endl;
          146  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          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,9,5};
          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