Need More Diamonds

All submissions for this problem are available.
Alice and Bob have decided to play the following game. Initially there are N diamonds placed in a straight line. Diamonds numbered from 1 to N in consecutive order. Each diamond has a specific value. The value of ith diamond is V_{i} for i from 1 to N. Players make moves alternatively. In each move player proceeds as follows. If there is only one diamond left the player takes it otherwise he/she tosses the unbiased coin and if it lands on heads he/she takes the first diamond among the diamonds that are currently present in a line, otherwise he/she takes the
last diamond. What is the expected total value Alice will get, if she plays first? Note that the unbiased coin lands on heads with probability 0.5 (and hence lands on tail with the same probability). Also note that the total value is the sum of values of all diamonds that Alice will get.
Input
The first line of the input contains an integer T, the number of test cases. T test cases follow. Each test case consists of exactly 2 lines. The first line of each test case contains a single integer
N, the number of diamonds. The second line contains N space separated integers
V_{1}, V_{2}, ..., V_{N}, the values of diamonds in the order they lie in a line.
Output
Output for each test case should contain a single real number in a separate line, the expected total value Alice will get for this particular test. Your answer will be considered as correct if it has an absolute error less than 10^{2}.
Constraints
1 ≤ T ≤ 500
1 ≤ N ≤ 2000
0 ≤ V_{i} ≤ 999
Example
Input 4 1 100 2 42 0 3 1 4 9 4 5 5 5 5 Output 100.000 21.000 9.500 10.000
Explanation
Case 1: In the first move Alice has to take 100, and this is the only move. Hence, the expected value Alice will get is 100.
Case 2: It is quite clear that Alice will make only 1 move. As she can get 42 or 0 with
equal probability, the expected value she will get is equal to 0.5 ∙ 42 + 0.5 ∙ 0 = 21.
Case 3: Let's consider all possible scenarios how game can proceed:
1st move  2nd move  3rd move  Alice total value 
Alice gets 1  Bob gets 4  Alice gets 9  10 
Alice gets 1  Bob gets 9  Alice gets 4  5 
Alice gets 9  Bob gets 1  Alice gets 4  13 
Alice gets 9  Bob gets 4  Alice gets 1  10 
Clearly each of these scenarios will happen with probability 0.5 ∙ 0.5 = 0.25. Hence the expected value Alice will get is equal to 0.25 ∙ 10 + 0.25 ∙ 5 + 0.25 ∙ 13 + 0.25 ∙ 10 = 9.5.
Case 4: Out of the 4 diamonds, Alice will get some 2 of them. As all of the diamonds have the same value 5, the expected value she will get is equal to 5 + 5 = 10.
Author:  kaushik_iska 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/DIAMOND 
Tags  dynamicprogramming, easy, kaushik_iska, oct12 
Date Added:  17092012 
Time Limit:  0.429076 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions