LOOPEXP - Loop Expectation

Consider the following pseudo-code

int a[1..N]; 

int max = -1;

for i = 1..N:

if(a[i] > max) 

max = a[i];


Your task is to calculate the expected number of times the 'if' block of the above pseudo-code executes. The array 'a' is a random permutation of numbers from 1..N chosen uniformly at random. 


First line contains t, the number of test cases. t lines follow, each containing N, the number of elements in the array.

1<= t <= 100

1<= n <=100,000


For each test case, output a single decimal. Your answer should be within 10^-6 of the correct answer.




Explaination :
for N=2, you can have the following two permutations: [1,2]  and [2,1] . 
for the first case the if block gets executed 2 times and for the second one the if block gets executed 1 time. So the expected 
value is (3)/2 = 1.5

hide comments
nadstratosfer: 2017-09-28 04:49:55

Found the pattern quickly, spent 1.5h trying to reduce the formula to something computable. Failed, tried what I thought was bruteforce, expected TLE - got AC! Not a good time though so decided to precompute, expected WA due to floats - got AC and best time in Python! Rare case of positive WTF.

sfialok98: 2017-06-26 16:38:07

Nice problem..
Solved using DP and Big Numbers....

sonudoo: 2017-02-08 13:40:35

Enjoyed deriving the formulae :)

aditya1997: 2016-08-26 08:51:25

use double instead of float.
ps: u can print as many digits after . but the answer must be in range of 10^-6 of the official answers

square1001: 2016-08-16 04:49:55

Easy. Find the logic.

Archit Jain: 2014-08-20 17:01:18

enjoyed solving it

Anubhav Balodhi : 2014-08-13 20:45:49

Once you work on paper, the problem is simpler...

SanchitK: 2014-03-24 15:30:14

someone please tell the answer for n=6

785227: 2014-03-20 13:42:46

I found the pattern.. But what does 10^-6 of the correct answer mean ?? I think i am getting WA because of this

Phoenix007: 2014-02-01 11:18:25

Very nice problem.. :)

Added by:Aman Gupta
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64