HackerRank Probability – Kevin and Expected Value

Challenge: Kevin and Expected Value

Subdomeniu: Probability (probability)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464751438

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/kevin-and-expected-value/problem

Cerinta

Kevinsogo is a professor of mathematics, One day he gave an assignment to his students which was hard for them. The students want you to help them in solving the problem.<br>

Given the value of $N$,  
$$ x = \text{rand}() \bmod N $$  
$$ Y = \sqrt{x + { \sqrt{x + { \sqrt {x + \sqrt {x+ \cdots }}}} }}$$

Note that $\text{rand}()$ returns an integer between $0$ and $10^{100}$ (inclusive) uniformly at random.

Find out the expected value of $Y$.

**Input Format**  
The first line contains an integer $T$ i.e. the number of test cases.<br>
The next $T$ lines will each contain an integer $N$.<br>

**Output Format**  
Print the output corresponding to each test case in a separate line. The answer will be considered correct if its absolute error doesn't exceed $10^{-3}$ or $0.001$.  

**Constraints**  
*Task 1: 30 points*  
$ 1\le T \le 10000$  
$ 1\le N \le 5 \times 10^6$  

*Task 2: 10 additional points*  
$ 1\le T \le 1000$  
$ 1\le N \le 10^{16}$  


**Sample Input**

    3
    1
    5
    10


**Sample Output**

	0.0
    1.69647248786
    2.43798952788

Cod sursa

#!/bin/python3

import math
import sys


def euler_maclaurin_sum_sqrt(a: int, b: int) -> float:
    """Approximate sum_{k=a..b} sqrt(4k+1) with Euler-Maclaurin."""
    if a > b:
        return 0.0

    fa = math.sqrt(4.0 * a + 1.0)
    fb = math.sqrt(4.0 * b + 1.0)

    integral = ((4.0 * b + 1.0) ** 1.5 - (4.0 * a + 1.0) ** 1.5) / 6.0
    d1 = (2.0 / fb - 2.0 / fa) / 12.0
    d3 = (24.0 / (4.0 * b + 1.0) ** 2.5 - 24.0 / (4.0 * a + 1.0) ** 2.5) / 720.0

    return integral + 0.5 * (fa + fb) + d1 - d3


def solve_one_case(n: int, anchor_m: int, anchor_sum_f: float) -> float:
    if n <= 1:
        return 0.0

    m = n - 1
    if m <= anchor_m:
        # This branch is filled by exact precomputation in caller.
        return -1.0

    # f(x) = (1 + sqrt(4x+1)) / 2, for x >= 1.
    cnt = m - anchor_m
    sum_sqrt = euler_maclaurin_sum_sqrt(anchor_m + 1, m)
    total = anchor_sum_f + 0.5 * cnt + 0.5 * sum_sqrt
    return total / n


def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    t = int(data[0])
    ns = [int(x) for x in data[1:1 + t]]

    max_n = max(ns) if ns else 1
    max_m = max(0, max_n - 1)

    # Exact prefix up to anchor, then Euler-Maclaurin beyond.
    anchor_m = min(max_m, 2_000_000)

    # exact_prefix[i] for queried i only (memory-friendly)
    small_targets = sorted({n for n in ns if 1 < n <= anchor_m + 1})
    exact_ans = {}

    curr_x = 1
    sum_f = 0.0
    for n in small_targets:
        target_m = n - 1
        while curr_x <= target_m:
            sum_f += 0.5 * (1.0 + math.sqrt(4.0 * curr_x + 1.0))
            curr_x += 1
        exact_ans[n] = sum_f / n

    # Ensure sum_f corresponds to full anchor_m for large-N branch.
    while curr_x <= anchor_m:
        sum_f += 0.5 * (1.0 + math.sqrt(4.0 * curr_x + 1.0))
        curr_x += 1

    out = []
    for n in ns:
        if n <= 1:
            out.append("0.0")
        elif n <= anchor_m + 1:
            out.append(f"{exact_ans[n]:.10f}")
        else:
            val = solve_one_case(n, anchor_m, sum_f)
            out.append(f"{val:.10f}")

    sys.stdout.write("\n".join(out))


if __name__ == '__main__':
    main()