結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
![]() |
提出日時 | 2016-03-19 22:15:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,351 bytes |
コンパイル時間 | 694 ms |
コンパイル使用メモリ | 84,388 KB |
実行使用メモリ | 11,720 KB |
最終ジャッジ日時 | 2024-10-01 09:17:13 |
合計ジャッジ時間 | 1,617 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
/* -*- coding: utf-8 -*- * * 108.cc: No.108 トリプルカードコンプ - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 100; /* typedef */ /* global variables */ int n; int n1 = 0, n2 = 0, n3 = 0; double dp[MAX_N + 1][MAX_N + 1][MAX_N + 1]; /* subroutines */ double rec(int i3, int i2, int i1) { if (dp[i3][i2][i1] >= 0.0) return dp[i3][i2][i1]; double sum = 0.0; if (i3 > 0) sum += rec(i3 - 1, i2 + 1, i1) * i3; if (i2 > 0) sum += rec(i3, i2 - 1, i1 + 1) * i2; if (i1 > 0) sum += rec(i3, i2, i1 - 1) * i1; return (dp[i3][i2][i1] = (sum + n) / (i3 + i2 + i1)); } /* main */ int main() { cin >> n; for (int i = 0; i < n; i++) { int ai; cin >> ai; switch (ai) { case 0: n3++; break; case 1: n2++; break; case 2: n1++; break; } } for (int i3 = 0; i3 <= n; i3++) for (int i2 = 0; i2 <= n; i2++) for (int i1 = 0; i1 <= n; i1++) dp[i3][i2][i1] = -1.0; dp[0][0][0] = 0.0; double ans = rec(n3, n2, n1); printf("%.10lf\n", ans); return 0; }