Submission #1027087

---

Source Code Expand

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define dump(x) 
#endif

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

int main(){
    iostream_init();
    int N;
    cin >> N;
    vector<double> f(N + 1);
    f[0] = 0;
    f[1] = 0;
    vector<double> fact(N + 1, 1);
    for(int i = 2; i <= N; i++) {
        fact[i] = fact[i-1] * i;
    }
    for(int i = 2; i <= N; i++) {
        double base = 1;
        REP(_, i) base /= 3;

        double fail = 0;
        f[i] = 1;
        REP(r, i+1) REP(g, i+1) if(r + g <= i) {
            int b = i - g - r;
            double p = fact[i] / fact[r] / fact[g] / fact[b] * base;
            int R = r == 0 ? INT_MAX : r;
            int G = g == 0 ? INT_MAX : g;
            int B = b == 0 ? INT_MAX : b;
            int next = min({R, G, B});
            if(next == i || (next == R && next == G && next == B)) {
                fail += p;
            } else {
                f[i] += p * f[next];
            }
        }
        f[i] = f[i] / (1 - fail);
    }
    cout << f[N] << endl;
    return 0;
}

Submission Info

Judge Result