Submission #7599480

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
double C(int n, int r) {
    double ans = 1;
    for (int i = 0; i < r; i++) {
        ans *= (n - i) / (i + 1.0);
    }
    return ans;
}
int main() {
    int N; cin >> N;
    vector<double> dp(N + 1);
    for (int cnt = 2; cnt <= N; cnt++) {
        double ans = 0, draw = 0;
        for (int a = 0; a <= cnt; a++) {
            for (int b = a; a + b <= cnt; b++) {
                int c = cnt - a - b;
                if (!(b <= c)) continue;
                double prob = C(cnt, a) * C(cnt - a, b) / pow(3, cnt);
                if (a == b && b == c) prob *= 1;
                else if (a == b || b == c) prob *= 3;
                else prob *= 6;
                if (a == 0 && b == 0) {
                    draw += prob;
                } else if (a == b && b == c) {
                    draw += prob;
                } else if (a == 0) {
                    ans += prob * dp[b];
                } else {
                    ans += prob * dp[a];
                }
            }
        }
        dp[cnt] = (1 + ans) / (1 - draw);
    }
    cout << fixed << setprecision(9) << dp[N] << '\n';
    return 0;
}

Submission Info

Judge Result