結果
問題 | No.108 トリプルカードコンプ |
ユーザー |
![]() |
提出日時 | 2019-09-23 16:19:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 2,091 bytes |
コンパイル時間 | 1,293 ms |
コンパイル使用メモリ | 160,396 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2024-09-19 04:26:55 |
合計ジャッジ時間 | 2,047 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define LLINF 1000000000000000ll #define sz(x) ((int)(x).size()) #define fi first #define sec second #define all(x) (x).begin(),(x).end() #define sq(x) ((x)*(x)) #define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++) #define EQ(a,b) (abs((a)-(b))<eps) #define dmp(x) cerr << __LINE__ << " " << #x << " " << x << endl; template<class T> void chmin(T& a,const T& b){if(a>b)a=b;} template<class T> void chmax(T& a,const T& b){if(a<b)a=b;} template<class T,class U> ostream& operator << (ostream& os,pair<T,U>& p){ os << p.fi << ',' << p.sec; return os; } template<class T,class U> istream& operator >> (istream& is,pair<T,U>& p){ is >> p.fi >> p.sec; return is; } template<class T> ostream& operator << (ostream &os,const vector<T> &vec){ for(int i=0;i<vec.size();i++){ os << vec[i]; if(i+1<vec.size())os << ' '; } return os; } template<class T> istream& operator >> (istream &is,vector<T>& vec){ for(int i=0;i<vec.size();i++)is >> vec[i]; return is; } void fastio(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); } int N; int a[105]; double dp[105][105][105]; double rec(int x,int y,int z){ if(dp[x][y][z]!=-1.0)return dp[x][y][z]; auto& t = dp[x][y][z]; t = 1.0; if(N>x+y+z)t += rec(x+1,y,z)*(double)(N-x-y-z)/(double)N; if(x>0)t += rec(x-1,y+1,z)*(double)x/(double)N; if(y>0)t += rec(x,y-1,z+1)*(double)y/(double)N; t /= (1.0-(double)z/(double)N); // cout << x << ' ' << y << ' ' << z << ' ' << t << endl; return t; } int cnt[4]; int main(){ fastio(); cin >> N; for(int i=0;i<N;i++){ cin >> a[i]; cnt[min(a[i],3)]++; } for(int i=0;i<=100;i++){ for(int j=0;j<=100;j++){ for(int k=0;k<=100;k++){ dp[i][j][k] = -1.0; } } } dp[0][0][N] = 0.0; cout << rec(cnt[1],cnt[2],cnt[3]) << endl; return 0; }