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

Added SRM/536-U/1A.cpp version [a01ad9bff4f4fef1]

            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 MergersDivOne { public:
           29  + double findMaximum(vector <int> revenues)
           30  + {
           31  +  vector<double> r(revenues.begin(), revenues.end());
           32  +  sort(r.begin(), r.end());
           33  +  return best(r, r.size());
           34  + }
           35  +
           36  +
           37  + map<int, double> memo;
           38  + double best(const vector<double>& r, int N)
           39  + {
           40  +  if( N == 1 )
           41  +   return r[0];
           42  +  if( memo.count(N) )
           43  +   return memo[N];
           44  +
           45  +  double score = -1e+100;
           46  +  for(int k=1; k<N; ++k) {
           47  +   double a = accumulate(r.begin()+k, r.begin()+N, best(r, k)) / (N-k+1);
           48  +   score = max(score, a);
           49  +  }
           50  +  return memo[N] = score;
           51  + }
           52  +};
           53  +
           54  +// BEGIN CUT HERE
           55  +#include <ctime>
           56  +double start_time; string timer()
           57  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           58  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           59  + { os << "{ ";
           60  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           61  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           62  +void verify_case(const double& Expected, const double& Received) {
           63  + bool ok = (abs(Expected - Received) < 1e-9);
           64  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           65  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           66  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           67  +#define END  verify_case(_, MergersDivOne().findMaximum(revenues));}
           68  +int main(){
           69  +
           70  +CASE(0)
           71  + int revenues_[] = {5, -7, 3};
           72  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
           73  + double _ = 1.5;
           74  +END
           75  +CASE(1)
           76  + int revenues_[] = {10, -17};
           77  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
           78  + double _ = -3.5;
           79  +END
           80  +CASE(2)
           81  + int revenues_[] = {12, 12, 12, 12, 12};
           82  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
           83  + double _ = 12.0;
           84  +END
           85  +CASE(3)
           86  + int revenues_[] = {0, 0, 0, 0, 0, 100};
           87  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
           88  + double _ = 50.0;
           89  +END
           90  +CASE(4)
           91  + int revenues_[] = {10, -10, 100, -100, 1000, -1000};
           92  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
           93  + double _ = 491.25;
           94  +END
           95  +CASE(5)
           96  +int revenues_[] = {0,0,100,100};
           97  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
           98  + double _ = -1;
           99  +END
          100  +/*
          101  +CASE(6)
          102  + int revenues_[] = ;
          103  +   vector <int> revenues(revenues_, revenues_+sizeof(revenues_)/sizeof(*revenues_));
          104  + double _ = ;
          105  +END
          106  +*/
          107  +}
          108  +// END CUT HERE

Added SRM/536-U/1B-U.cpp version [0853e7c70823346d]

            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 RollingDiceDivOne { public:
           29  + long long mostLikely(vector <int> dice)
           30  + {
           31  +  sort(dice.begin(), dice.end());
           32  +  if( dice.size() == 1 )
           33  +   return 1;
           34  +
           35  +
           36  +  LL m2sum = 0;
           37  +  for(int i=0; i<dice.size(); ++i)
           38  +   m2sum += dice[i]+1;
           39  +  LL v = m2sum / 2;
           40  +  return v;
           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 long long& Expected, const long long& Received) {
           53  + bool ok = (Expected == Received);
           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(_, RollingDiceDivOne().mostLikely(dice));}
           58  +int main(){
           59  +
           60  +CASE(0)
           61  + int dice_[] = {6, 6, 8};
           62  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           63  + long long _ = 11LL;
           64  +END
           65  +CASE(1)
           66  + int dice_[] = {10};
           67  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           68  + long long _ = 1LL;
           69  +END
           70  +CASE(2)
           71  + int dice_[] = {2, 3, 4, 5};
           72  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           73  + long long _ = 9LL;
           74  +END
           75  +CASE(3)
           76  + int dice_[] = {1, 10, 1};
           77  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           78  + long long _ = 3LL;
           79  +END
           80  +CASE(4)
           81  + int dice_[] = {382828264, 942663792, 291832707, 887961277, 546603677, 545185615, 146267547, 6938117, 167567032, 84232402,
           82  +700781193, 452172304, 816532384, 951089120, 448136091, 280899512, 256093435, 39595226, 631504901, 154772240};
           83  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           84  + long long _ = 4366828428LL;
           85  +END
           86  +CASE(5)
           87  + int dice_[] = {686070183,764446558,958676845,711114086,307405925,18345836,534933273,884410953,402311475,699530578,734067293,586174895,653276411,461102667,361634525,515961596,53576037,909418211,678589501,398850606,279452824,544186770,203263120,85451598,330889574,93199510,730144410,620028986,247001511,285471536,706978584,976668932,10197700,550812603,440712526,127306784,280595874,519698127,482194343,519518638,680491824,236933627,69469348,993453692,817501995,678439028,166742435,200336684,724838900,525355524};
           88  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           89  + long long _ = -1LL;
           90  +END
           91  +CASE(6)
           92  + int dice_[] = {1};
           93  +   vector <int> dice(dice_, dice_+sizeof(dice_)/sizeof(*dice_));
           94  + long long _ = 1LL;
           95  +END
           96  +
           97  +}
           98  +// END CUT HERE