Submission #3015610

---

Source Code Expand

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

int nxt[1 << 16][3];
void nxtInit(){
    int tmp = (1<<18)-1;
    for(int i=1;i<(1<<16);i++){
        int b=1;
        for(;true;b<<=1)if(i&b)break;
        for(int j=0;j<3;j++, b<<=1){
            nxt[i][j] = (i&b ? i^b : i);
        }
    }
}

double dp[2][1 << 16];

int main(){

    nxtInit();

    int N;
    cin>>N;
    int startNode = 0;
    for(int i=0;i<N;i++){
        int x;
        cin>>x;
        startNode |= (1 << x);
    }
    dp[0][startNode] = 1.0;
    double ans = 0.0;

    for(int i=0;i<100;i++){
        for(int j=0;j<(1<<16);j++){
            dp[(i+1)%2][j]=0.0;
        }
        for(int j=1;j<(1<<16);j++){
            for(int k=0;k<3;k++){
                dp[(i+1)%2][nxt[j][k]]+=dp[i%2][j] / 3.0;
            }
        }
        ans += dp[i%2][0] * (double)i;
    }

    printf("%.9f\n", ans);

    return 0;
}

Submission Info

Judge Result