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.
Input
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
Output
For each test case, output a single decimal. Your answer should be within 10-6 of the correct answer.
Example
Input: 1 2 Output: 1.5
Explanation
For N = 2, you can have the following two permutations: [1, 2] and [2, 1].
In the first case the if block gets executed 2 times, and in the second case the if block gets executed 1 time. So the expected value is (2 + 1) / 2 = 1.5
hide comments
Gaurang Gupta:
2013-05-30 13:50:54
Am i supposed to print exactly one digit after . or six? Please help.
|
|
Ouditchya Sinha:
2013-05-23 14:04:07
Nice Problem. :) |
|
Arika Saputro:
2013-05-21 06:17:06
i think you must change the example testcase
|
|
Francky:
2013-04-20 19:50:12
Please tell me an example of error in my solution, thanks in advance. I'm weak with floats, but this problem seems easy to me...
|
Added by: | Aman Gupta |
Date: | 2013-04-20 |
Time limit: | 1s-3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own |