tdpcj.cpp

gistfile1.cpp

#include <cstdio>
#include <vector>
using namespace std;

double dp[1<<16];
bool vis[1<<16];

double f(int bit){
    if(bit == 0) return 0;
    if(vis[bit]) return dp[bit];
    double ret = 1e9;
    for (int i=0; i<16; i++) {
        int cnt = 3;
        double tmp = 0;
        for (int j=-1; j<=1; j++) {
            if(i + j == -1 || i + j >= 16) cnt--;
            else if((bit >> (i+j)) & 1){
                tmp += f(bit ^ (1<<(i+j)));
            }
            else cnt--;
        }
        if(cnt == 0) continue;
        ret = min(ret,(tmp + 3.0) / cnt);
    }
    vis[bit] = 1;
    return dp[bit] = ret;
}

int main(){
    int t, u, b = 0;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&u);
        b |= (1<<u);
    }
    printf("%lf",f(b));
}