Code : Black Jack

#include <bits/stdc++.h>
using namespace std;

#define endl "\n";

void solve(int n, int L, int D) {
    auto p = (long double)1.0 / D;

    // ndp[i] is the probability that y is equal to i.
    vector<long double> ndp(n + 1, 0);
    ndp[0] = 1;
    for (int y = 0; y < L; y++) {
        for (int nxt = 1; nxt <= min(D, n - y); nxt++) {
            ndp[y + nxt] += p * ndp[y];
        }
        ndp[y] = 0;
    }
    for (int y = 1; y <= n; y++) {
        cout << ndp[y] << " ";
    }
    cout << endl;
    cout << endl;

    // win[i] is the winning probability when x = i.
    vector<long double> win(n + 1, 0);
    for (int x = 0; x <= n; x++) {
        // You would lose if max(L, i) <= y <= n.
        long double ndpsum = 0;
        for (int y = max(L, x); y <= n; y++) {
            ndpsum += ndp[y];
        }
        win[x] += (1 - ndpsum);
    }
    for (int x = 1; x <= n; x++) {
        cout << win[x] << " ";
    }
    cout << endl;
    cout << endl;

    long double ans = 0;

    // Strategy : No more rolls after x >= lim.
    for (int lim = 1; lim <= n; lim++) {
        // dp[i] is the probability that x = i in this strategy.
        vector<long double> dp(n + 1, 0);
        dp[0] = 1;
        for (int x = 0; x < lim; x++) {
            for (int nxt = 1; nxt <= min(D, n - x); nxt++) {
                dp[x + nxt] += p * dp[x];
            }
            dp[x] = 0;
        }
        for (int x = 1; x <= n; x++) {
            cout << dp[x] << " ";
        }
        cout << endl;

        // cur is the winning probability for this strategy.
        long double cur = 0;
        for (int x = 1; x <= n; x++) {
            cur += dp[x] * win[x];
        }
        cout << cur << endl;
        cout << endl;
        ans = max(ans, cur);
    }

    cout << ans << endl;
}

int main() {
    cout << fixed << setprecision(10);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, L, D;
        cin >> n >> L >> D;
        solve(n, L, D);
    }

    return 0;
}

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

#define endl "\n";

long double op(long double a, long double b) { return a + b; }

long double e() { return 0; }

class BlackBox {
  public:
    segtree<long double, op, e> *diff_array;
    BlackBox(int n) { diff_array = new segtree<long double, op, e>(n); }

    void range_inc(int l, int r, long double delta) {
        diff_array->set(l, diff_array->get(l) + delta);
        diff_array->set(r + 1, diff_array->get(r + 1) - delta);
    }

    long double point_query(int idx) {
        // Atcoder's segtree prod function has range [l, r).
        // Hence, we add + 1 to make inclusive range.
        return diff_array->prod(0, idx + 1);
    }
};

void solve(int n, int L, int D) {
    auto p = (long double)1.0 / D;

    // ndp[i] is the probability that y is equal to i.
    vector<long double> ndp(n + 1, 0);
    ndp[0] = 1;
    for (int y = 0; y < L; y++) {
        for (int nxt = 1; nxt <= min(D, n - y); nxt++) {
            ndp[y + nxt] += p * ndp[y];
        }
        ndp[y] = 0;
    }
    for (int y = 1; y <= n; y++) {
        cout << ndp[y] << " ";
    }
    cout << endl;
    cout << endl;

    // win[i] is the winning probability when x = i.
    vector<long double> win(n + 1, 0);
    for (int x = 0; x <= n; x++) {
        // You would lose if max(L, i) <= y <= n.
        long double ndpsum = 0;
        for (int y = max(L, x); y <= n; y++) {
            ndpsum += ndp[y];
        }
        win[x] += (1 - ndpsum);
    }
    for (int x = 1; x <= n; x++) {
        cout << win[x] << " ";
    }
    cout << endl;
    cout << endl;

    long double ans = 0;

    // Strategy : No more rolls after x >= lim.
    for (int lim = 1; lim <= n; lim++) {
        // dp[i] is the probability that x = i in this strategy.
        BlackBox dp(n + 5);
        dp.range_inc(0, 0, 1);
        for (int x = 0; x < lim; x++) {
            dp.range_inc(x + 1, x + min(D, n - x), p * dp.point_query(x));
            dp.range_inc(x, x, -dp.point_query(x));
        }
        for (int x = 1; x <= n; x++) {
            cout << dp.point_query(x) << " ";
        }
        cout << endl;

        // cur is the winning probability for this strategy.
        long double cur = 0;
        for (int x = 1; x <= n; x++) {
            cur += dp.point_query(x) * win[x];
        }
        cout << cur << endl;
        cout << endl;
        ans = max(ans, cur);
    }

    cout << ans << endl;
}

int main() {
    cout << fixed << setprecision(10);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n, L, D;
        cin >> n >> L >> D;
        solve(n, L, D);
    }

    return 0;
}