OpenJudge

1082:游戏

总时间限制:
20000ms
单个测试点时间限制:
2000ms
内存限制:
262144kB
描述

AliceBob在玩一个游戏。

这个游戏的规则如下。开始,总共有N个数。这个游戏由N轮组成。每一轮的分数是剩下的数字的个数。在一轮中,两个玩家轮流操作。(为了公平,Bob在第一轮中先操作)如果还剩下多于一个数,那么玩家可以扔掉任意两个数AiAj(i!=j),然后放回数|Ai-Aj|。只剩一个数字的时候这轮结束。如果剩下的这个数是奇数,Bob胜,否则Alice胜。这轮的分数会被加给胜者。然后把这些数恢复成这轮之前的样子。输家可以任选一个数并把它扔出去(不再放回来)。然后用剩下的数开始下一轮。在N轮之后,所有数字都被扔了然后游戏结束。分数高的一方赢得整个游戏。

Bob决定随机玩这个游戏,即在他操作的时候,他随机选择数字,剩下的每个数字有相同的被选中的机率。当一轮结束的时候,如果Bob是输家,他会随机地扔掉一个数。但是Alice的每个操作都是最优的,即这个操作能使她最终能得到最高的总分。

问题是,已知桌上最初的N个数,请计算出Alice得分的期望值。(不要在意谁最终会赢)


输入
输入包含多组数据。
第一行有一个整数T代表数据组数。
对于每一组测试数据,第一行是一个整数N,第二行是N个正整数Ai代表这局游戏开始的时候的数字。
输出
一共T行,分别表示每组测试的答案。
这道题本来应该有SPJ,但是openjudge太坑了。所以你需要以以下方式输出你的答案。如果你的答案是X,输出[3 * x + 0.5]。([y]代表不超过y的最大整数)
样例输入
2
2
2 4
2
1 2
样例输出
9
3
提示
数据约束
对于100%的数据,1 ≤ T ≤ 200,1 ≤ N ≤ 1000,1 ≤ Ai ≤ 100000。
提示
在第一组数据中,Alice两轮都赢了,所以答案是3,所以应该输出9。
在第二轮中,Bob赢了第一轮,然后Alice就扔掉了1,然后她赢了。所以她的分数是1,所以应该输出3。
全局题号
7328
添加于
2014-08-24
提交次数
1
尝试人数
1
通过人数
1