//むしゃくしゃしているときに書いた。今はリファクタリングしている。 #include using namespace std; bool flag[1024][1024]; double memo[1024][1024]; double f(int unopen, int known) { if (unopen == known){ //未知のカードを一枚引けば必ず既知のカードとマッチする flag[unopen][known] = true; return 0; } if (flag[unopen][known]){ return memo[unopen][known]; } const double u = unopen; const double k = known; double r = 0; if (known > 0){ //既知のカードを一枚目に引き当てたとき //引き当てたカードと既知のカードを一枚ずつ取り去る r += (k / u) * f(unopen - 1, known - 1); } //同じ未知のカードを連続で引き当てたとき //未知のカードを二枚取り去る r += ((u - k) / u) * (1.0 / (u - 1)) * f(unopen - 2, known); if (known > 0){ //未知のカードを引いた後、既知のカードを引いたとき //次のターン既知のカードのペアを取り除く + ペナルティ追加 r += ((u - k) / u) * (k / (u - 1)) * (f(unopen - 2, known) + 1); } //異なる未知のカードを二枚引いたとき //既知のカードが二枚増える + ペナルティ追加 if (unopen - known > 2){ r += ((u - k) / u) * ((u - k - 2) / (u - 1)) * (f(unopen - 2, known + 2) + 1); } flag[unopen][known] = true; memo[unopen][known] = r; return r; } int main() { memset(flag, 0, sizeof(flag)); memset(memo, 0, sizeof(memo)); for (int i = 0; i < 1024; ++i){ flag[0][i] = true; } int N; while (cin >> N && N){ printf("%.10lf\n", f(N, 0)); } }