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
ishaan:
2014-01-11 13:33:46
Is this trick some pre-defined formula for solving this question?
|
|
Tarun Garg:
2013-12-28 11:24:56
Think like a lazy man....:D |
|
Bhavik:
2013-12-26 17:58:12
good question :) |
|
Nick:
2013-12-25 06:46:14
Yes, there's a pattern behind this. You can try.. Btw, thanks @[ _BaDsHah_ ]
|
|
Akhilesh Anandh:
2013-11-09 21:59:19
Really good problem.. finally discovered the trick :D |
|
Alien:
2013-07-02 11:33:55
agreed hasil Last edit: 2013-07-02 11:37:04 |
|
Hasil Sharma:
2013-07-02 11:23:37
KingAditya , can't agree more you only need to know the trick nothing else |
|
DOT:
2013-06-21 10:48:43
Some more test cases, please. |
|
Alien:
2013-06-21 10:28:09
EASY PROB,if you know the trick |
|
Chandan Mittal:
2013-06-01 18:25:22
what will be the o/p for
|
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 |