当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

4958:Poor Rukaw

题目描述
Last time, Hanamichi lost the basketball battle between him and Rukaw. So these days he had a burning desire to wreak revenge. So he invented a new game and asked Rukaw to play with him. What’s more, the loser should confess his ignorance and on the other hand the winner can go on a trip with Haruko.

Hanamichi knows the game well (as he invented it), and he always chooses the best strategy, however Rukaw is not so willing to play this game. He just wants it to be finished as soon as possible so that he can go to play basketball. So he decides not to think about the best strategy and play casually.

The game’s rules are here. At first, there are N numbers on the table. And the game consists of N rounds. Each round has a score which is the number of the numbers still left on the table. And Each round there will be one number to be removed from the table. In each round, two players take turns to play with these numbers.To be fair, Rukaw plays first in the first round. If there’s more than 1 numbers on the table, players can choose any two numbers they like and change them to a number abs(x-y). This round ends when there’s only one number left on the table, and if this number is an odd number, Rukaw wins, otherwise Hanamichi wins. The score of this round will be add to the winner. After that, all numbers will be recovered to the state when this round starts. And the loser of this round has the right to remove one number and he also has the right to play first in the next round. Then they use the remaining numbers to start next round. After N rounds, all numbers removed and this game ends. The person who has more scores wins the whole game.

As you know, Rukaw has already decided to play casually, that is to say, in his turn, he chooses numbers randomly, each numbers left on the table has the same possibility to be chosen. When a round ends, if Rukaw is the loser, he also randomly chooses a number to remove. And Hanamichi will always choose numbers or remove numbers to maxmium his final total score. Here comes the question:
Given the N numbers on the table at the beginning, can you calculate the expectation of the final score of Hanamichi. (We don’t care about who wins the whole game at all.)
输入解释
This problem contains multiple tests.
In the first line there’s one number T (1 ≤ T ≤ 200) which tells the total number of test cases. For each test case, there a integer N (1 ≤ N ≤ 1000) in the first line, and there are N intergers Ai , i = 1, 2, … , N (1 ≤ Ai ≤ 100000), in the second line which are the numbers at the beginning.
输出解释
This problem is intended to use special judge. But so far, BestCoder doesn’t support special judge. So you should output your answer in the following way. If the expectation you get is X, output \([3\times X+0.5]\) in a line. Here, [A] means the largest integer which is no more than A.
输入样例
2
2
2 4
2
1 2
输出样例
9
3
提示
In the first example, Hanamichi will always win two rounds and the score of two rounds will be 2 and 1. 
So the answer is 3. (And you should output 9.) 
In the second example, Rukaw wins the first round. And after that Hanamichi has the right to choose a number from 1 and 2 to remove.
(Because this round started with this two numbers.)
And We know that he will choose 1 to maximum his final total score.
So when the second round starts, there’s only one number 2 left on the table and Hanamichi plays first.
He immediately wins this round and got 1 point. Then the game ends. So the answer is 1.(And you should output 3.)
来自杭电HDUOJ的附加信息
Recommend heyang

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #5

源链接: HDU-4958

最后修改于 2020-10-25T23:18:25+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 32768/32768K(Java/Others)