Yuki 301 サイコロで確率問題 (1)

Problem Description:
You have a dice with 6 faces, mapping to integer in 1..6.
You roll the dice, and sum up them along the process.
However, you will reset the sum to 0, when the sum has exceeded N.
Find the expected number of rolls you have to make.

Constraints:
1 ≤ T ≤ 10000
1 ≤ N ≤ 1e18
Precision: 12 digits after decimal dot.

Solution:
When N is large, one can observe that it converges to N + 1 + 2 / 3.
When N is small (< 200), apply DP and binary search:
Binary search the answer as e:
dp[i]: expected number of rounds to roll sum n.
dp[i] = sum(dp[j] for j in (i - 6)..(i - 1)) / 6 + 1
If e is low, then e < dp[n], otherwise e > dp[n].

Code:

#include <bits/stdc++.h>

double attempt(double e, long long n) {
  std::vector<double> dp(n + 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= 6; ++j) {
      if (i > j) dp[i] += dp[i - j];
      if (j > i) dp[i] += e;
    }
    dp[i] = dp[i] / 6 + 1;
  }
  return dp[n];
}

double naive_solve(long long n) {
  double lb = 0, ub = 1e12;
  for (int i = 0; i < 100; ++i) {
    double mb = (lb + ub) / 2.;
    (attempt(mb, n) >= mb ? lb : ub) = mb;
  }
  return (lb + ub) / 2.;
}

signed main() {
  std::ios::sync_with_stdio(false);
  int T;
  std::cin >> T;
  while (T--) {
    int64_t N;
    std::cin >> N;
    if (N < 200) std::cout << std::fixed << std::setprecision(13) << naive_solve(N) << std::endl;
    else std::cout << std::fixed << std::setprecision(13) << ((N + 1) + 2. / 3) << std::endl;
  }
  return 0;
}