結果
問題 | No.174 カードゲーム(Hard) |
ユーザー | omochana1 |
提出日時 | 2015-03-27 01:03:55 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,265 bytes |
コンパイル時間 | 669 ms |
コンパイル使用メモリ | 86,924 KB |
実行使用メモリ | 13,388 KB |
最終ジャッジ日時 | 2024-06-29 01:22:47 |
合計ジャッジ時間 | 4,254 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 12 |
ソースコード
#include <iostream>#include <cmath>#include <cstdio>#include <algorithm>#include <string>#include <vector>#include <queue>#include <string.h>#include <map>#include <fstream>#include <functional>#include <bitset>#include <stack>#include <set>#include <climits>#define MAX_N 100010#define LOG 21#define PI 3.141592653589#define EPS 1e-6#define MOD 1000000007#define YJSNPI 810#define INF (1 << 30)#define ADD(a, b) a = (a + (ll)b) % MOD#define MUL(a, b) a = (a * (ll)b) % MOD#define MAX(a, b) a = max(a, b)#define MIN(a, b) a = min(a, b)#define x first#define y second#define REP(i, a, b) for(int i = a; i < b; i++)#define RER(i, a, b) for(int i = a - 1; i >= b; i--)using namespace std;typedef long long ll;typedef pair<ll, int> pi;void debug() {cout << endl; }template<class FIRST, class... REST>void debug(FIRST arg, REST... rest) { cout << arg << " "; debug(rest...); }template<class T>void showary(T begin, T end) {while(begin != end) { cout << *begin << " "; begin++; } cout << endl; }double pa[50][50];double pb[50][50];double wina[50], winb[50];double dp1[1 << 20];double dp2[1 << 20];double dp[50][50][50];int va[50], vb[50];int N;double A, B;void solve(double *dp, double (*p)[50], double A) {dp[0] = 1.0;REP(bit, 0, (1 << N)) {int cnt = 0, minat = -1;REP(i, 0, N) {if(bit & (1 << i)) cnt++;else if(minat == -1) minat = i;}if(cnt == N - 1) p[cnt][minat] += dp[bit];else p[cnt][minat] += dp[bit] * A;dp[bit | (1 << minat)] += dp[bit] * A;REP(i, 0, N) {if((bit & (1 << i)) || minat == i) continue;if(N - cnt - 1 > 0) p[cnt][i] += dp[bit] * (1.0 - A) / (N - cnt - 1.0);if(N - cnt - 1 > 0) dp[bit | (1 << i)] += dp[bit] * (1.0 - A) / (N - cnt - 1.0);}}}int main() {cin >> N >> A >> B;REP(i, 0, N) cin >> va[i];REP(i, 0, N) cin >> vb[i];sort(va, va + N);sort(vb, vb + N);solve(dp1, pa, A);solve(dp2, pb, B);double res = 0;REP(i, 0, N) {REP(j, 0, N) {REP(k, 0, N) {if(va[j] > vb[k]) {res += pa[i][j] * pb[i][k] * (va[j] + vb[k]);}}}}/*REP(i, 0, N) showary(pa[i], pa[i] + N);REP(i, 0, N) showary(pb[i], pb[i] + N);showary(wina, wina + N);showary(winb, winb + N);*/printf("%.10f\n", res);}