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

Added SRM/548-U/1A.cpp version [4bd4984796b0669c]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class KingdomAndTrees { public:
           23  + int minLevel(vector <int> heights)
           24  + {
           25  +  // (L,R]
           26  +  int L = -1;
           27  +  int R = 1000000000;
           28  +  while(R-L>1)
           29  +  {
           30  +   int C = (L+R)/2;
           31  +   (possible(C,heights) ? R : L) = C;
           32  +  }
           33  +  return R;
           34  + }
           35  +
           36  + bool possible(int C, const vector<int>& h)
           37  + {
           38  +  int last = max(1, h[0]-C);
           39  +  for(int i=1; i<h.size(); ++i)
           40  +  {
           41  +   if( !(last < h[i]+C) )
           42  +    return false;
           43  +   last = max(last+1, h[i]-C);
           44  +  }
           45  +  return true;
           46  + }
           47  +};
           48  +
           49  +// BEGIN CUT HERE
           50  +#include <ctime>
           51  +double start_time; string timer()
           52  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           53  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           54  + { os << "{ ";
           55  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           56  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           57  +void verify_case(const int& Expected, const int& Received) {
           58  + bool ok = (Expected == Received);
           59  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           60  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           61  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           62  +#define END  verify_case(_, KingdomAndTrees().minLevel(heights));}
           63  +int main(){
           64  +
           65  +CASE(0)
           66  + int heights_[] = {9, 5, 11};
           67  +   vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
           68  + int _ = 3;
           69  +END
           70  +CASE(1)
           71  + int heights_[] = {5, 8};
           72  +   vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
           73  + int _ = 0;
           74  +END
           75  +CASE(2)
           76  + int heights_[] = {1, 1, 1, 1, 1};
           77  +   vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
           78  + int _ = 4;
           79  +END
           80  +CASE(3)
           81  + int heights_[] = {548, 47, 58, 250, 2012};
           82  +   vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
           83  + int _ = 251;
           84  +END
           85  +CASE(4)
           86  + int heights_[] = {337994619,837714986,7014426,516695490,268514071,590654553,940024470,79308071,891444369,231310251,172567010,283491054,951215936,92716118,911004789,896372476,617116292,874491895,120052194,635772188,938392572,466867891,418351197,278475278,635224368,38779964,762367612,370214557,20108108,314281202,644947239,868648377,617056931,542328796,280916141,281585869,895175595,529854516,862330692,733665485,173060292,579136324,401396401,303236137,161627936,410922706,172892990,840336279,848958999,849348801};
           87  +   vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
           88  + int _ = -1;
           89  +END
           90  +CASE(5)
           91  + int heights_[] = {1000000000,1};
           92  +   vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
           93  + int _ = 500000000;
           94  +END
           95  +
           96  +}
           97  +// END CUT HERE

Added SRM/548-U/1B.cpp version [3c1fd7f25faac951]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +template<typename T>
           23  +struct DP3
           24  +{
           25  + int N1, N2, N3;
           26  + vector<T> data;
           27  + DP3(int N1, int N2, int N3, const T& t = T())
           28  +  : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           29  + T& operator()(int i1, int i2, int i3)
           30  +  { return data[ ((i1*N2)+i2)*N3+i3 ]; }
           31  + void swap(DP3& rhs)
           32  +  { data.swap(rhs.data); }
           33  +};
           34  +
           35  +struct cmp {
           36  + int N;
           37  + cmp(int N):N(N){}
           38  + bool operator()(int a, int b) const
           39  + {
           40  +  if( abs(2*a - N*N) != abs(2*b - N*N) )
           41  +   return abs(2*a - N*N) < abs(2*b - N*N);
           42  +  return a < b;
           43  + }
           44  +};
           45  +class KingdomAndDice { public:
           46  + double newFairness(vector <int> firstDie, vector <int> secondDie, int X)
           47  + {
           48  +  int N = firstDie.size();
           49  +  sort(secondDie.begin(), secondDie.end());
           50  +
           51  +  vector<int> choice;
           52  +  {
           53  +   choice.push_back(N);
           54  +   for(int i=0; i+1<N; ++i)
           55  +    choice.push_back(secondDie[i+1]-secondDie[i]-1);
           56  +   choice.push_back(X-secondDie.back());
           57  +  }
           58  +  int base = 0;
           59  +  {
           60  +   for(int k=0; k<N; ++k)
           61  +    if( firstDie[k]!=0 && firstDie[k]<secondDie[0] ) {
           62  +     choice[0] --;
           63  +     base += 0;
           64  +    }
           65  +   for(int i=0; i+1<N; ++i)
           66  +    for(int k=0; k<N; ++k)
           67  +     if( firstDie[k]!=0 && secondDie[i]<firstDie[k] && firstDie[k]<secondDie[i+1] ) {
           68  +      choice[i+1] --;
           69  +      base += i+1;
           70  +     }
           71  +   for(int k=0; k<N; ++k)
           72  +    if( firstDie[k]!=0 && secondDie[N-1]<firstDie[k] ) {
           73  +     choice[N] --;
           74  +     base += N;
           75  +    }
           76  +  }
           77  +  return solve(N, base, choice, count(firstDie.begin(), firstDie.end(), 0));
           78  + }
           79  +
           80  + double solve(int N, int base, const vector<int>& choice, int K)
           81  + {
           82  +  DP3<int> dp(N+1, K+1, N*N+1);
           83  +  for(int i=0; i<=N; ++i)
           84  +  for(int p=0; p<=K; ++p)
           85  +  for(int sum=0; sum<=N*N; ++sum)
           86  +  {
           87  +   if(i==0)
           88  +   {
           89  +    dp(i,p,sum) = (sum==base && p<=choice[i]);
           90  +   }
           91  +   else
           92  +   {
           93  +    bool b = false;
           94  +    for(int z=0; z<=p && z<=choice[i]; ++z)
           95  +     if(sum>=i*z)
           96  +      b = b | dp(i-1,p-z,sum-i*z);
           97  +    dp(i,p,sum) = b;
           98  +   }
           99  +  }
          100  +
          101  +  vector<int> cand;
          102  +  for(int sum=0; sum<=N*N; ++sum)
          103  +   if( dp(N,K,sum) )
          104  +    cand.push_back( sum );
          105  +  return *min_element(cand.begin(), cand.end(), cmp(N)) / double(N*N);
          106  + }
          107  +};
          108  +
          109  +// BEGIN CUT HERE
          110  +#include <ctime>
          111  +double start_time; string timer()
          112  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          113  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          114  + { os << "{ ";
          115  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          116  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          117  +void verify_case(const double& Expected, const double& Received) {
          118  + bool ok = (abs(Expected - Received) < 1e-9);
          119  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          120  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          121  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          122  +#define END  verify_case(_, KingdomAndDice().newFairness(firstDie, secondDie, X));}
          123  +int main(){
          124  +
          125  +CASE(0)
          126  + int firstDie_[] = {0, 2, 7, 0};
          127  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          128  + int secondDie_[] = {6, 3, 8, 10};
          129  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          130  + int X = 12;
          131  + double _ = 0.4375;
          132  +END
          133  +CASE(1)
          134  + int firstDie_[] = {0, 2, 7, 0};
          135  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          136  + int secondDie_[] = {6, 3, 8, 10};
          137  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          138  + int X = 10;
          139  + double _ = 0.375;
          140  +END
          141  +CASE(2)
          142  + int firstDie_[] = {0, 0};
          143  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          144  + int secondDie_[] = {5, 8};
          145  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          146  + int X = 47;
          147  + double _ = 0.5;
          148  +END
          149  +CASE(3)
          150  + int firstDie_[] = {19, 50, 4};
          151  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          152  + int secondDie_[] = {26, 100, 37};
          153  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          154  + int X = 1000;
          155  + double _ = 0.2222222222222222;
          156  +END
          157  +CASE(4)
          158  + int firstDie_[] = {6371, 0, 6256, 1852, 0, 0, 6317, 3004, 5218, 9012};
          159  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          160  + int secondDie_[] = {1557, 6318, 1560, 4519, 2012, 6316, 6315, 1559, 8215, 1561};
          161  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          162  + int X = 10000;
          163  + double _ = 0.49;
          164  +END
          165  +CASE(5)
          166  + int firstDie_[] = {278130165,933636493,607327308,19369203,439158229,445295066,370731340,551180273,163280323,359800317,834663837,108871632,362106962,921853660,145507840,284869553,246938492,379648759,956330140,525562675,251028940,270135098,862786589,513909283,412651940,499422899,724171306,922270222,938213346,61418124,248820926,891527589,812074952,155495258,23280465,761818758,328244247,975585791,108105856,414583437,424242761,168720992,585728188,0,0,0,0,0,0,0};
          167  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          168  + int secondDie_[] = {475017760,773630717,985005264,963668637,320647204,665487259,585555327,272107932,203172682,57845645,311126817,496577583,834654861,77335024,405827438,231342594,943378345,971851607,455697802,119475931,551079372,838525393,192593102,990828850,382044077,590561977,229071016,962163538,621629435,727621063,109926457,152882146,9199017,615779540,160320904,216276208,675743894,414050471,126645085,238141513,151262148,280509327,923103663,125699296,790073355,738597671,864455279,384833125,510401421,219630179};
          169  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          170  + int X = 1000000000;
          171  + double _ = 0.5;
          172  +END
          173  +CASE(6)
          174  + int firstDie_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
          175  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          176  + int secondDie_[] = {475017760,773630717,985005264,963668637,320647204,665487259,585555327,272107932,203172682,57845645,311126817,496577583,834654861,77335024,405827438,231342594,943378345,971851607,455697802,119475931,551079372,838525393,192593102,990828850,382044077,590561977,229071016,962163538,621629435,727621063,109926457,152882146,9199017,615779540,160320904,216276208,675743894,414050471,126645085,238141513,151262148,280509327,923103663,125699296,790073355,738597671,864455279,384833125,510401421,219630179};
          177  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          178  + int X = 1000000000;
          179  + double _ = 0.5;
          180  +END
          181  +CASE(6)
          182  + int firstDie_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
          183  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          184  + int secondDie_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
          185  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          186  + int X = 100;
          187  + double _ = 0.5;
          188  +END
          189  +CASE(7)
          190  +int firstDie_[] = {0,0};
          191  +   vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_));
          192  +   int secondDie_[] = {1,2};
          193  +   vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_));
          194  + int X = 4;
          195  + double _ = 1;
          196  +END
          197  +
          198  +}
          199  +// END CUT HERE