RNDORDER - The Least Number

no tags 

You are given n symbols a1, a2,..., an. You are told that there is a total ordering of the symbols. That is, there is a permutation [P1, P2,..., Pn] of [1,2,...,n] such that aP1< aP2 <...< aPn. You are trying to figure out the order by doing comparisons. The process you follow for determining the order is as follows:

  • Compare [a1, a2]
  • Compare [a2, a3], [a1, a3]
  • Compare [a3, a4], [a2, a4], [a1, a4]
  • ...
  • ...
  • Compare [an-1,an], [an-2,an], ..., [a1, an]

Note that you compare in the order specified. That is you compare [a2, a3], then and only then do you compare [a1, a3].

Definition of Compare[ai, aj] (i < j)

  • If Compare [ai, aj] = 1, it means ai > aj. If Compare[ai, aj] = -1, it means ai < aj.
  • Compare is consistent. Suppose, that you queried [a2, a6] and it was already established [a2 < a6] (because for example a2 < a5 and a5 < a6 - since both of these comparisons happen earlier), then [a2, a6] returns -1.
  • If no relationship is known between ai and aj, Compare[ai, aj] = 1 with probability 1/2 and -1 with probability 1/2.

Your task is to output the probability that a1 is the smallest element of the final ordering so obtained.

Input

First line contains T, the number of test cases.

Each of the next T lines contains one number each, n(1 <= n <= 1000).

Output

Output T lines in total, one per test case: Probability that a1 is indeed the smallest element at the end of the comparisons. Your output will be judged correct if it differs by no more than 10-9 to the reference answer.

Example

Input:
3
1
2
3

Output:
1
0.500
0.3750000

Explanation

n = 1 is trivial.

For n = 2, only comparison is [a1, a2]. a1 is lower with probability 1/2.

For n = 3, a1 is not the least element if either (a1 > a2) or (a1 < a2 and a3 < a2 and a3 < a1).

So, probability that a1 is not the least element = 1/2 + 1/8 = 5/8. Probability that a1 is the least = 3/8 = 0.375.


hide comments
:D: 2012-04-22 10:49:19

Re: Zhouxing Shi

I'm not sure what you're asking about, but the logic behind this problem can be a little tricky, so it's probably that.

The best way to visualize this is, is to image you are playing a game with a "cheating" computer program. You want to guess the order of numbers by asking questions about relations (in the order specified in the description). But the program doesn't generate a sequence at startup. Instead it only keeps track of relations between number, that can be deduced from previously given answers. Is both query results are possible, it gives a random answers, otherwise it gives the one that will be consistent with data to this point.

So it's importaint that you don't look for a number of permutations meeting the constraint, because the chance of getting a certain permutations varies and is determined by queries sequence.

Zhouxing Shi: 2012-03-05 08:00:49

I wonder what it means.

Last edit: 2012-03-05 08:01:50

Added by:konqueror
Date:2010-07-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET