2941. Girl Friend
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 400 Accepted Runs: 138
May Buddha let us meet
in my most beautiful hours
I have prayed for it
for five hundred years.
--Murong Xi
RoBa, a dull and shy boy, still has no girl friend after four years' campus life. What a pity!
His friends are very worried about him, and plan to manage a series of dates with different girls
for him.
Now the girl candidates are determined, and the possibility of RoBa falling in love with each
girl, and the fitness for each pair of them are calculated. You know RoBa is very loyal (or say,
foolish), once he fall in love with some girl, he will have no interest to others at all, even
if their fitness maybe not very well. As RoBa's best friend, you hope that he have a perfect
love. So you have to arrange a plan that, make RoBa miss some dates on purpose. Please note the
order of the girls cannot be changed. And if after all the dates, RoBa still has no girl friend,
you can consider the fitness is 0. You task is to make a plan so that the expected fitness is maximum.
For example, there are two girls, the first one with 100% possibility and the fitness is 10.
The other is with 60% possibility and the fitness is 100. The best plan should be, miss the
date with the first girl, then date with the second girl. So the expected fitness is 60% * 100
+ 40% * 0 = 60. You should not make RoBa meet the first girl, because he will fall in love with
her definitely, then he will not date with the second girl, but the fitness is only 10.
Input
There are multiple test cases. The first line of each test case is an integer N (N
≤ 100,000), indicating the number of girls. (Hundreds of thousand girls... oh my God!) Then
N lines followed, each contains two integers Pi and Vi.
Pi (0 ≤ Pi ≤100) indicating the possibility (in
percents) of RoBa and this girl falling in love if they meet. Vi (0 ≤
Vi ≤ 100000) indicating the girl's fitness for RoBa.
The input is terminated with N = 0.
Output
Output one line for each test case, indicating the maximum expected fitness. Two digits after
decimal point are preserved by rounding.
Sample Input
2
100 10
60 100
0
Sample Output
60.00
Problem Setter: RoBa
Source: TJU Team Selection Contest 2008
Submit List
Runs Forum Statistics
Tianjin University Online Judge v1.2.4
