Submission #16654663


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  double nCr[110][110];
  nCr[0][0] = 1;
  for (int n = 1; n < 110; n++)
    for (int r = 0; r <= n; r++)
      nCr[n][r] = (r == 0 || r == n) ? 1 : nCr[n - 1][r] + nCr[n - 1][r - 1];
  double memo[110];
  fill(memo, memo + 110, -1);
  function<double(int)> rec = [&](int n) {
    if (n == 1) return 0.;
    if (memo[n] >= 0) return memo[n];
    double ret = 1;
    double pw3 = pow(1. / 3, n);
    for (int i = 1; i * 3 <= n; i++) {
      double p = nCr[n][i] * pw3 * 3;
      for (int j = i + 1; 2 * j <= n - i; j++)
        p += nCr[n][i] * nCr[n - i][j] * pw3 * 6;
      if (n - 2 * i > 0) p += nCr[n][i] * nCr[n - i][i] * pw3 * 3;
      ret += p * rec(i);
    }
    double p = pw3 * 3;
    debug(p);
    if (n % 3 == 0) p += pw3 * nCr[n][n / 3] * nCr[n - (n / 3)][n / 3];
    debug(n);
    debug(p);
    ret /= 1 - p;
    return memo[n] = ret;
  };
  int N;
  cin >> N;
  cout << fixed << setprecision(12) << rec(N) << '\n';
  return 0;
}

Submission Info

Submission Time
Task C - ゲーマーじゃんけん
User hashiryo
Language C++ (GCC 9.2.1)
Score 0
Code Size 1645 Byte
Status
Exec Time 7 ms
Memory 4232 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
× 2
× 97
Set Name Test Cases
All input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt
Case Name Status Exec Time Memory
input-002.txt 7 ms 3868 KB
input-003.txt 3 ms 4024 KB
input-004.txt 2 ms 4028 KB
input-005.txt 2 ms 4084 KB
input-006.txt 2 ms 4192 KB
input-007.txt 2 ms 4192 KB
input-008.txt 2 ms 4084 KB
input-009.txt 2 ms 4232 KB
input-010.txt 2 ms 4192 KB
input-011.txt 2 ms 4152 KB
input-012.txt 2 ms 4100 KB
input-013.txt 5 ms 4148 KB
input-014.txt 2 ms 4184 KB
input-015.txt 2 ms 4088 KB
input-016.txt 3 ms 4084 KB
input-017.txt 2 ms 4192 KB
input-018.txt 2 ms 4188 KB
input-019.txt 2 ms 4136 KB
input-020.txt 2 ms 4148 KB
input-021.txt 2 ms 4232 KB
input-022.txt 7 ms 4088 KB
input-023.txt 2 ms 4144 KB
input-024.txt 2 ms 4184 KB
input-025.txt 2 ms 4216 KB
input-026.txt 2 ms 4136 KB
input-027.txt 1 ms 4092 KB
input-028.txt 2 ms 4192 KB
input-029.txt 2 ms 4148 KB
input-030.txt 2 ms 4096 KB
input-031.txt 2 ms 4136 KB
input-032.txt 2 ms 4216 KB
input-033.txt 2 ms 4144 KB
input-034.txt 2 ms 4088 KB
input-035.txt 2 ms 4192 KB
input-036.txt 3 ms 4084 KB
input-037.txt 2 ms 4088 KB
input-038.txt 2 ms 4216 KB
input-039.txt 2 ms 4144 KB
input-040.txt 2 ms 4092 KB
input-041.txt 2 ms 4028 KB
input-042.txt 2 ms 4084 KB
input-043.txt 2 ms 4188 KB
input-044.txt 2 ms 4100 KB
input-045.txt 2 ms 4204 KB
input-046.txt 2 ms 4192 KB
input-047.txt 2 ms 4092 KB
input-048.txt 2 ms 4148 KB
input-049.txt 2 ms 4188 KB
input-050.txt 2 ms 4088 KB
input-051.txt 2 ms 4188 KB
input-052.txt 2 ms 4140 KB
input-053.txt 2 ms 4024 KB
input-054.txt 2 ms 4144 KB
input-055.txt 3 ms 4156 KB
input-056.txt 2 ms 4188 KB
input-057.txt 4 ms 4188 KB
input-058.txt 2 ms 4088 KB
input-059.txt 2 ms 4144 KB
input-060.txt 2 ms 4140 KB
input-061.txt 2 ms 4184 KB
input-062.txt 2 ms 4188 KB
input-063.txt 2 ms 4092 KB
input-064.txt 2 ms 4088 KB
input-065.txt 2 ms 4144 KB
input-066.txt 2 ms 4100 KB
input-067.txt 2 ms 4088 KB
input-068.txt 2 ms 4216 KB
input-069.txt 2 ms 4100 KB
input-070.txt 3 ms 4084 KB
input-071.txt 2 ms 4188 KB
input-072.txt 2 ms 4188 KB
input-073.txt 2 ms 4184 KB
input-074.txt 2 ms 4084 KB
input-075.txt 2 ms 4100 KB
input-076.txt 3 ms 4088 KB
input-077.txt 2 ms 4088 KB
input-078.txt 2 ms 4084 KB
input-079.txt 2 ms 4088 KB
input-080.txt 2 ms 4024 KB
input-081.txt 2 ms 4084 KB
input-082.txt 2 ms 4232 KB
input-083.txt 2 ms 4136 KB
input-084.txt 2 ms 4088 KB
input-085.txt 2 ms 4204 KB
input-086.txt 2 ms 4192 KB
input-087.txt 2 ms 4204 KB
input-088.txt 3 ms 4088 KB
input-089.txt 2 ms 4188 KB
input-090.txt 2 ms 4148 KB
input-091.txt 2 ms 4136 KB
input-092.txt 2 ms 4096 KB
input-093.txt 2 ms 4088 KB
input-094.txt 2 ms 4188 KB
input-095.txt 5 ms 4084 KB
input-096.txt 2 ms 4188 KB
input-097.txt 4 ms 4188 KB
input-098.txt 2 ms 4120 KB
input-099.txt 2 ms 4084 KB
input-100.txt 3 ms 4096 KB