Submission #326531

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

const double kEps = 1e-9;

typedef unsigned long long ull;
typedef pair<int,int> P;

double nCr[102][102];

double E[102];

P combination_type(int rock, int scissor, int paper) {
  vector<int> v;
  if (rock)
    v.push_back(rock);
  if (scissor)
    v.push_back(scissor);
  if (paper)
    v.push_back(paper);
  sort(v.begin(), v.end());
  int mn = v[0];
  int mn_cnt = count(v.begin(), v.end(), mn);
  int sum = rock + scissor + paper;
  P ret;

  if (v.size() == 1) {
    ret.first = 3;
    ret.second = 0;
  }
  else if (mn_cnt == 1) {
    ret.first = 1;
    ret.second = sum - mn;
  }
  else if (mn_cnt == 2) {
    ret.first = 2;
    ret.second = sum - mn;
  }
  else {
    ret.first = 3;
    ret.second = 0;
  }

  return ret;
}

double solve(int n) {
  const double kDenom = pow(3, n);
  vector<double> pn(102, 0);

  for (int r = 0; r <= n; r++) {
    for (int s = 0; (s + r) <= n; s++) {
      for (int p = 0; (s + r + p) <= n; p++) {
        if (s + r + p < n) continue;
        P tmp = combination_type(r, s, p);
        // printf("r,s,p=%d,%d,%d value=%llu f,s=%d,%d\n",
        //   r, s, p, nCr[n][r] * nCr[n-r][s], tmp.first, tmp.second);
        if (tmp.first == 1 || tmp.first == 2) {
          pn[n - tmp.second] += nCr[n][r] * nCr[n-r][s] / kDenom;
        }
        else {
          pn[n] += nCr[n][r] * nCr[n-r][s] / kDenom;
        }
      }
    }
  }

  for (int i = 0; i <= n; i++) {
     //printf("pn[%d] = %.3f\n", i, pn[i]);
     //pn[i] /= kDenom;
  }

  // expression
  double ret = pn[n];
  for (int i = 1; i <= n - 1; i++) {
    //printf("compute sum at index=%d\n", i);
    ret += pn[i] * (E[i] + 1);
  }
  ret /= (1 - pn[n]);

  return ret;
}

int main() {
  // nCr
  memset(nCr, 0, sizeof nCr);
  nCr[0][0] = 1;
  for (int i = 1; i <= 100; i++) {
    nCr[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j];
    }
  }

  // do
  memset(E, 0, sizeof E);
  E[1] = 0;
  for (int i = 2; i <= 100; i++) {
    E[i] = solve(i);
    //printf("E[%d] = %.3f\n", i, E[i]);
  }

  int in;
  while (scanf("%d", &in) != -1) {
    printf("%.7f\n", E[in]);
  }
  return 0;
}

Submission Info

Judge Result