Submission #323932

---

Source Code Expand

#include <bits/stdc++.h>//{{{{{{
using namespace std;
//TYPEDEFS //{{{
typedef long double ldouble;
typedef long long lint;
typedef unsigned long long ulint;
typedef vector<int> vint;
typedef vector<lint> vlint;
typedef vector<double> vdouble;
//}}}
//MACROS //{{{
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniquenize(v) (v).erase(unique(all(v)), (v).end())
#define perm(c) sort(all(c)); for(bool b = true; b; b = next_permutation(all(c)))
//}}}
//INPUTS //{{{
#define int(x) int x; scanf("%d",&x);
#define lint(x) long long x; scanf("%lld",&x);
#define vint(v,n) vector<int> v(n); rep(i,n) scanf("%d", &v[i]);
#define vlint(v,n) vector<lint> v(n); rep(i,n) scanf("%lld", &v[i]);
#define double(x) double x; scanf("%lf",&x);
#define vdouble(v,n) vector<double> v(n); rep(i,n) scanf("%lf", &v[i]);
#define string(x) string x; cin >> x;
//}}}
//OUTPUT //{{{
template<class T> ostream& operator<<(ostream &os, const vector<T> &v){os << "["; rep(i, v.size()) os << (i? "," : "") << v[i]; os << "]"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t){ return os << "(" << t.first << "," << t.second << ")";}
//}}}
//UTILITY//{{{
template<class T> bool chmax(T &a, const T &b){return a<b && (a = b, 1);}
template<class T> bool chmin(T &a, const T &b){return a>b && (a = b, 1);}
//}}} }}}}}}

double d[114];

inline double fact(int x){
    long double res = 1;
    for(int i = 1; i <= x; i++) res *= i;
    return res;
}

double f(int a, int b, int c){
    return fact(a+b+c)/fact(a)/fact(b)/fact(c);
}

double all_same(int n){
    return f(n, 0, 0);
}

double aiko3(int n){
    assert(n%3 == 0);
    return f(n/3, n/3, n/3)/3;
}

double calc(int m, int n){
    double res = 0;
    //(now, winning, losing)
    //(m, 0, n-m)
    if(m <= n-m) res += f(m, 0, n-m);
    //(m, n-m, 0)
    if(m < n-m) res += f(m, n-m, 0);

    //(m, i, n-i-m)
    for(int i = m+1; i+m <= n && m <= n-i-m; i++){
        res += f(m, i, n-i-m);
    }
    return res;
}


int main(){
    d[1] = 0;
    //d[2] = 1.5;
    //d[3] = 1.5;
    for(int i = 2; i <= 100; i++){
        vector<double> w(200);
        double tmp = 1;
        double pp = 1;
        for(int j = 1; j <= i; j++){
            w[j] = calc(j, i);
            tmp += w[j] * d[j] / pow(3, i-1);
            pp -= w[j]/pow(3, i-1);
        }
        //w[i] = all_same(i);
        //if(i%3 == 0) w[i] = aiko3(i);
        d[i] = tmp / (1-pp);
    }

    int n; cin >> n; printf("%.9f\n", d[n]);
}

Submission Info

Judge Result