#include #include #include using namespace std; class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x mt; int mti = N + 1; void init_genrand(unsigned int s) { mt.push_back(s & 0xffffffffU); for(mti=1; mti> 30)) + mti); mt[mti] &= 0xffffffffU; } } void init_by_array(vector init_key) { int key_length = init_key.size(); init_genrand(19921223U); int i = 1, j = 0; int k = N > key_length ? N : key_length; for( ; k; k--) { mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U)) + init_key[j] + j; mt[i] &= 0xffffffffU; i++; j++; if(i >= N) { mt[0] = mt[N-1]; i = 1; } if(j >= key_length) { j = 0; } } for(k=N-1; k; k--) { mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U)) - i; mt[i] &= 0xffffffffU; i++; if(i >= N) { mt[0] = mt[N-1]; i = 1; } } mt[0] = 0x80000000U; } unsigned int genrand_int32(void) { unsigned int y; static unsigned int mag01[2] = {0x0U, MATRIX_A}; if(mti >= N) { if(mti == N + 1) { init_genrand(5489U); } int kk; for(kk=0; kk> 1) ^ mag01[y & 0x1U]; } for(; kk> 1) ^ mag01[y & 0x1U]; } y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK); mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680U; y ^= (y << 15) & 0xefc60000U; y ^= (y >> 18); return y; } int genrand_int31(void) { return (int)(genrand_int32() >> 1); } int choose(vector &v, int prob, int n) { int minp = 0; for(int i : range(1, n)) { if(v[i] < v[minp]) { minp = i; } } int p; if(genrand_int31() % 1000 < prob) { p = minp; } else { swap(v[minp], v[n-1]); p = genrand_int31() % (n-1); } swap(v[p], v[n-1]); return v[n-1]; } int main(void) { clock_t start = clock(); time_t seed = time(0); vector init; init.push_back(0x123); init.push_back(0x234); init.push_back(0x345); init.push_back(0x456); init.push_back(seed); init_by_array(init); int n; float da, db; scanf("%d%f%f", &n, &da, &db); int pa = da * 1000, pb = db * 1000; vector a, b; for(int i : range(n)) { int x; scanf("%d", &x); a.push_back(x); } for(int i : range(n)) { int x; scanf("%d", &x); b.push_back(x); } sort(a.begin(), a.end()); sort(b.begin(), b.end()); int game, win; int limit = 2.8 * CLOCKS_PER_SEC; for(game=0, win=0; clock()-start < limit; game++) { vector cpa = a, cpb = b; int suma = 0, sumb = 0; for(int i : range(n-1)) { int ca = choose(cpa, pa, n-i); int cb = choose(cpb, pb, n-i); if(ca > cb) { suma += ca+cb; } else { sumb += ca+cb; } } int ca = cpa[0], cb = cpb[0]; if(ca > cb) { suma += ca+cb; } else { sumb += ca+cb; } if(suma > sumb) { win++; } } printf("%f\n", float(win) / game); return 0; } // (ΦωΦ)<試行回数が増えてるはず!