HackerRank Probability – Random Number Generator

Challenge: Random Number Generator

Subdomeniu: Probability (probability)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464761505

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/random-number-generator-1/problem

Cerinta

Sabya is writing code to output a random number between $1$ and $N$ inclusive. The code can output different integers in the interval with different probabilities so that the sum of the probabilities is equal to $1$.
<br>

For evaluation, the code is run twice. If the output in both cases are different, his score is equal to the *sum* of the outputs. Otherwise, his score is equal to $0$.
<br>

Sabya is very intelligent, and he writes code that maximizes his expected score. Find the expected score. Output the ratio of the expected score to the maximum possible score. The maximum possible score is $2\times N - 1$.
<br>

Input Format

The first line contains $T$: the number of test cases.  
The next $T$ lines each contain a single integer, $N$.

Output Format

Output $T$ lines: the ratio $\frac{\text{expected score}}{\text{maximum score}}$ in each case.    
The answer is considered correct if the absolute error is less than $10^{-8}$.  

**Constraints**  
$1 \leqslant T \leqslant 10^5$  
$1 \leqslant N \leqslant 10^6$

Cod sursa

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    vector<int> ns(T);
    int maxN = 0;
    for (int i = 0; i < T; ++i) {
        cin >> ns[i];
        maxN = max(maxN, ns[i]);
    }

    vector<long double> H(maxN + 1, 0.0L);
    for (int i = 1; i <= maxN; ++i) H[i] = H[i - 1] + 1.0L / (long double)i;

    auto eval_pt = [&](int N, int m) {
        int t = N - m + 1;
        long double hseg = H[N] - H[t - 1];
        long double lambda = (2.0L - (long double)m) / hseg;
        return (1.0L + lambda / (long double)t) * 0.5L;
    };

    for (int N : ns) {
        if (N <= 1) {
            cout << "0.000000000\n";
            continue;
        }

        int lo = 2, hi = N;
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (eval_pt(N, mid) > 0.0L)
                lo = mid;
            else
                hi = mid - 1;
        }
        int m = lo;
        int t = N - m + 1;

        long double hseg = H[N] - H[t - 1];
        long double lambda = (2.0L - (long double)m) / hseg;

        long double S1 = ((long double)t + (long double)N) * (long double)m * 0.5L;
        long double E = (S1 - lambda * lambda * hseg) * 0.5L;
        long double ratio = E / (long double)(2 * N - 1);

        if (ratio < 0) ratio = 0;
        cout.setf(std::ios::fixed);
        cout << setprecision(12) << (double)ratio << '\n';
    }

    return 0;
}