Soluție HackerRank pentru Kevin and Expected Value, subdomeniul Probability, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod…

  • Problemă: Kevin and Expected Value
  • Domeniu: Probability
  • Limbaj: Python 3

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

Cerință

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.

Given the value of N,
x = text{rand}() bmod N
Y = sqrt{x + { sqrt{x + { sqrt {x + sqrt {x+ ·s }}}} }}

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.

The next T lines will each contain an integer N.

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≤ T ≤ 10000
1≤ N ≤ 5 × 10^6

*Task 2: 10 additional points*
1≤ T ≤ 1000
1≤ N ≤ 10^16

Sample Input

3
1
5
10

Sample Output

0.0
1.69647248786
2.43798952788

Cod sursă

#!/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()
HackerRank Probability – Kevin and Expected Value