2b07d53d04 2012-07-07 kinaba: #include <iostream> 2b07d53d04 2012-07-07 kinaba: #include <sstream> 2b07d53d04 2012-07-07 kinaba: #include <iomanip> 2b07d53d04 2012-07-07 kinaba: #include <vector> 2b07d53d04 2012-07-07 kinaba: #include <string> 2b07d53d04 2012-07-07 kinaba: #include <map> 2b07d53d04 2012-07-07 kinaba: #include <set> 2b07d53d04 2012-07-07 kinaba: #include <algorithm> 2b07d53d04 2012-07-07 kinaba: #include <numeric> 2b07d53d04 2012-07-07 kinaba: #include <iterator> 2b07d53d04 2012-07-07 kinaba: #include <functional> 2b07d53d04 2012-07-07 kinaba: #include <complex> 2b07d53d04 2012-07-07 kinaba: #include <queue> 2b07d53d04 2012-07-07 kinaba: #include <stack> 2b07d53d04 2012-07-07 kinaba: #include <cmath> 2b07d53d04 2012-07-07 kinaba: #include <cassert> 2b07d53d04 2012-07-07 kinaba: using namespace std; 2b07d53d04 2012-07-07 kinaba: typedef long long LL; 2b07d53d04 2012-07-07 kinaba: typedef long double LD; 2b07d53d04 2012-07-07 kinaba: typedef complex<LD> CMP; 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: template<typename T> 2b07d53d04 2012-07-07 kinaba: struct DP3 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: int N1, N2, N3; 2b07d53d04 2012-07-07 kinaba: vector<T> data; 2b07d53d04 2012-07-07 kinaba: DP3(int N1, int N2, int N3, const T& t = T()) 2b07d53d04 2012-07-07 kinaba: : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); } 2b07d53d04 2012-07-07 kinaba: T& operator()(int i1, int i2, int i3) 2b07d53d04 2012-07-07 kinaba: { return data[ ((i1*N2)+i2)*N3+i3 ]; } 2b07d53d04 2012-07-07 kinaba: void swap(DP3& rhs) 2b07d53d04 2012-07-07 kinaba: { data.swap(rhs.data); } 2b07d53d04 2012-07-07 kinaba: }; 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: struct cmp { 2b07d53d04 2012-07-07 kinaba: int N; 2b07d53d04 2012-07-07 kinaba: cmp(int N):N(N){} 2b07d53d04 2012-07-07 kinaba: bool operator()(int a, int b) const 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: if( abs(2*a - N*N) != abs(2*b - N*N) ) 2b07d53d04 2012-07-07 kinaba: return abs(2*a - N*N) < abs(2*b - N*N); 2b07d53d04 2012-07-07 kinaba: return a < b; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: }; 2b07d53d04 2012-07-07 kinaba: class KingdomAndDice { public: 2b07d53d04 2012-07-07 kinaba: double newFairness(vector <int> firstDie, vector <int> secondDie, int X) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: int N = firstDie.size(); 2b07d53d04 2012-07-07 kinaba: sort(secondDie.begin(), secondDie.end()); 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: vector<int> choice; 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: choice.push_back(N); 2b07d53d04 2012-07-07 kinaba: for(int i=0; i+1<N; ++i) 2b07d53d04 2012-07-07 kinaba: choice.push_back(secondDie[i+1]-secondDie[i]-1); 2b07d53d04 2012-07-07 kinaba: choice.push_back(X-secondDie.back()); 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: int base = 0; 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: for(int k=0; k<N; ++k) 2b07d53d04 2012-07-07 kinaba: if( firstDie[k]!=0 && firstDie[k]<secondDie[0] ) { 2b07d53d04 2012-07-07 kinaba: choice[0] --; 2b07d53d04 2012-07-07 kinaba: base += 0; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: for(int i=0; i+1<N; ++i) 2b07d53d04 2012-07-07 kinaba: for(int k=0; k<N; ++k) 2b07d53d04 2012-07-07 kinaba: if( firstDie[k]!=0 && secondDie[i]<firstDie[k] && firstDie[k]<secondDie[i+1] ) { 2b07d53d04 2012-07-07 kinaba: choice[i+1] --; 2b07d53d04 2012-07-07 kinaba: base += i+1; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: for(int k=0; k<N; ++k) 2b07d53d04 2012-07-07 kinaba: if( firstDie[k]!=0 && secondDie[N-1]<firstDie[k] ) { 2b07d53d04 2012-07-07 kinaba: choice[N] --; 2b07d53d04 2012-07-07 kinaba: base += N; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: return solve(N, base, choice, count(firstDie.begin(), firstDie.end(), 0)); 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: double solve(int N, int base, const vector<int>& choice, int K) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: DP3<int> dp(N+1, K+1, N*N+1); 2b07d53d04 2012-07-07 kinaba: for(int i=0; i<=N; ++i) 2b07d53d04 2012-07-07 kinaba: for(int p=0; p<=K; ++p) 2b07d53d04 2012-07-07 kinaba: for(int sum=0; sum<=N*N; ++sum) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: if(i==0) 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: dp(i,p,sum) = (sum==base && p<=choice[i]); 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: else 2b07d53d04 2012-07-07 kinaba: { 2b07d53d04 2012-07-07 kinaba: bool b = false; 2b07d53d04 2012-07-07 kinaba: for(int z=0; z<=p && z<=choice[i]; ++z) 2b07d53d04 2012-07-07 kinaba: if(sum>=i*z) 2b07d53d04 2012-07-07 kinaba: b = b | dp(i-1,p-z,sum-i*z); 2b07d53d04 2012-07-07 kinaba: dp(i,p,sum) = b; 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: vector<int> cand; 2b07d53d04 2012-07-07 kinaba: for(int sum=0; sum<=N*N; ++sum) 2b07d53d04 2012-07-07 kinaba: if( dp(N,K,sum) ) 2b07d53d04 2012-07-07 kinaba: cand.push_back( sum ); 2b07d53d04 2012-07-07 kinaba: return *min_element(cand.begin(), cand.end(), cmp(N)) / double(N*N); 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: }; 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: // BEGIN CUT HERE 2b07d53d04 2012-07-07 kinaba: #include <ctime> 2b07d53d04 2012-07-07 kinaba: double start_time; string timer() 2b07d53d04 2012-07-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 2b07d53d04 2012-07-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 2b07d53d04 2012-07-07 kinaba: { os << "{ "; 2b07d53d04 2012-07-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 2b07d53d04 2012-07-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 2b07d53d04 2012-07-07 kinaba: void verify_case(const double& Expected, const double& Received) { 2b07d53d04 2012-07-07 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 2b07d53d04 2012-07-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 2b07d53d04 2012-07-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 2b07d53d04 2012-07-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 2b07d53d04 2012-07-07 kinaba: #define END verify_case(_, KingdomAndDice().newFairness(firstDie, secondDie, X));} 2b07d53d04 2012-07-07 kinaba: int main(){ 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: CASE(0) 2b07d53d04 2012-07-07 kinaba: int firstDie_[] = {0, 2, 7, 0}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: int secondDie_[] = {6, 3, 8, 10}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 12; 2b07d53d04 2012-07-07 kinaba: double _ = 0.4375; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(1) 2b07d53d04 2012-07-07 kinaba: int firstDie_[] = {0, 2, 7, 0}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: int secondDie_[] = {6, 3, 8, 10}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 10; 2b07d53d04 2012-07-07 kinaba: double _ = 0.375; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(2) 2b07d53d04 2012-07-07 kinaba: int firstDie_[] = {0, 0}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: int secondDie_[] = {5, 8}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 47; 2b07d53d04 2012-07-07 kinaba: double _ = 0.5; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(3) 2b07d53d04 2012-07-07 kinaba: int firstDie_[] = {19, 50, 4}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: int secondDie_[] = {26, 100, 37}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 1000; 2b07d53d04 2012-07-07 kinaba: double _ = 0.2222222222222222; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(4) 2b07d53d04 2012-07-07 kinaba: int firstDie_[] = {6371, 0, 6256, 1852, 0, 0, 6317, 3004, 5218, 9012}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: int secondDie_[] = {1557, 6318, 1560, 4519, 2012, 6316, 6315, 1559, 8215, 1561}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 10000; 2b07d53d04 2012-07-07 kinaba: double _ = 0.49; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(5) 2b07d53d04 2012-07-07 kinaba: 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}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: 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}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 1000000000; 2b07d53d04 2012-07-07 kinaba: double _ = 0.5; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(6) 2b07d53d04 2012-07-07 kinaba: 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}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: 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}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 1000000000; 2b07d53d04 2012-07-07 kinaba: double _ = 0.5; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(6) 2b07d53d04 2012-07-07 kinaba: 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}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: 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}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 100; 2b07d53d04 2012-07-07 kinaba: double _ = 0.5; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: CASE(7) 2b07d53d04 2012-07-07 kinaba: int firstDie_[] = {0,0}; 2b07d53d04 2012-07-07 kinaba: vector <int> firstDie(firstDie_, firstDie_+sizeof(firstDie_)/sizeof(*firstDie_)); 2b07d53d04 2012-07-07 kinaba: int secondDie_[] = {1,2}; 2b07d53d04 2012-07-07 kinaba: vector <int> secondDie(secondDie_, secondDie_+sizeof(secondDie_)/sizeof(*secondDie_)); 2b07d53d04 2012-07-07 kinaba: int X = 4; 2b07d53d04 2012-07-07 kinaba: double _ = 1; 2b07d53d04 2012-07-07 kinaba: END 2b07d53d04 2012-07-07 kinaba: 2b07d53d04 2012-07-07 kinaba: } 2b07d53d04 2012-07-07 kinaba: // END CUT HERE