Ginie Learns to Code
All submissions for this problem are available.
Aladdin is trying to teach coding to his Genie.
After teaching him the concepts, he gives him the following pseudo code :-
int a[1..N]; int max = -1; for i = 1..N: if(a[i] > max) max = a[i];
In order to assess his level of understanding, he asks his Genie 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.
For each test case, output a single decimal.
Your answer should be within 10-6 of the correct answer.
- 1<= t <= 100
- 1<= n <=100,000
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.