HDUOJ 6803 Blow up the Enemy

HDUOJ 6803 Blow up the Enemy"/>

HDUOJ 6803 Blow up the Enemy

HDUOJ 6803 Blow up the Enemy

题目链接

Problem Description

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 ith weapon has Damage Ai and Delay Di. When a player shoots with this weapon, his enemy’s HP is reduced by Ai, then he must wait for Di 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.

Input

The first line of the input gives the number of test cases, T(1≤T≤100). T test cases follow.

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

Then n lines follow, the ith of which contains two integers Ai,Di(1≤Ai≤100,1≤Di≤10000), representing the Damage and the Delay of each weapon.

The sum of n in all test cases doesn’t exceed 2000.

Output

For each test case, print a line with a real number p(0≤p≤1), representing the optimal probability.

Your answers should have absolute or relative errors of at most 10−6.

Sample Input

2
1
100 100
4
50 50
40 20
30 10
20 100

Sample Output

0.5
0.875

思维题，注意攻击回合必须是整数，我们可以预处理出所有武器所需的最早击杀时间：
( ⌈ 100 a i ⌉ − 1 ) ∗ d i (\lceil \frac{100}{a_i}\rceil -1)*d_i (⌈ai​100​⌉−1)∗di​
为什么减 1 1 1 呢，因为时间为 0 0 0 的时候就互相攻击了一次，因为数据小直接暴力找最优武器就行，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int damage,delay,t[N];
int main(){int n,T;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&damage,&delay);t[i]=(ceil(double(100)/double(damage))-1)*delay;}double ans=0;for(int i=0;i<n;i++){double sum=0;for(int j=0;j<n;j++){if(t[j]==t[i]) sum+=1.0/double(n*2);else if(t[j]>t[i]) sum+=1.0/double(n);}ans=max(ans,sum);}printf("%.6f\n",ans);}return 0;
}