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

建议使用的浏览器:

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

6803:Blow up the Enemy

Special Judge 特殊评判
题目描述
Zhang3 is playing a shooting game with Father. In the game there are two players trying to kill each other to win the game.

The game provides $n$ weapons, each has two properties: Damage and Delay. The $i^\mathrm{th}$ weapon has Damage $A_i$ and Delay $D_i$. When a player shoots with this weapon, his enemy's HP is reduced by $A_i$, then he must wait for $D_i$ ms before he can shoot again.

The game processes as follows:

1. Before the game starts, Zhang3 and Father choose a weapon respectively. Father always randomly chooses one of the $n$ weapons with equal probabilities. Each player can only use the chosen weapon during the game.
2. When the game starts, Zhang3 and Father have $100$ HP each. They make their first shot at the same time.
3. They keep shooting as quickly as possible. That means, a player shoots instantly whenever he can shoot, until the game ends.
4. When a player's HP is reduced to 0 or lower, he dies and the game ends. If the other player is still alive (i.e. has HP higher than 0), then the living player wins the game; otherwise (if the two players die at the same time), each player has $50\%$ probability to win the game.

Zhang3 wants to win the game. Please help her to choose a weapon so that the probability to win is maximized. Print the optimal probability.
输入解释
The first line of the input gives the number of test cases, $T \; (1 \le T \le 100)$. $T$ test cases follow.

For each test case, the first line contains an integer $n \; (1 \le n \le 1000)$, the number of weapons in the game.

Then $n$ lines follow, the $i^\mathrm{th}$ of which contains two integers $A_i, D_i \; (1 \le A_i \le 100, \; 1 \le D_i \le 10000)$, representing the Damage and the Delay of each weapon.

The sum of $n$ in all test cases doesn't exceed $2000$.
输出解释
For each test case, print a line with a real number $p \; (0 \le p \le 1)$, representing the optimal probability.

Your answers should have absolute or relative errors of at most $10^{-6}$.
输入样例
2
1
100 100
4
50 50
40 20
30 10
20 100
输出样例
0.5
0.875
来自杭电HDUOJ的附加信息
Recommend liuyiding

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

源链接: HDU-6803

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

共提交 0

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