题号：NC15784
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
Now there are totally n seeds in a box. You'll pick one randomly, then you can either put it back then pick another one randomly until you're satisfied with what you take, or plant it to the campus of HUST and stop the process so that the beauty of HUST increase vi. However, the i-th seed must be planted after having been put back for pi times (pi = 0 means the seed can be picked up for the first time and then must be planted). Now HUSTers will take the choices that will maximize the expected beauty. Can you help calculate the expected maximum beauty?
Please keep the answer with 6 decimal places.
输入描述:
The first line is an integer n
, indicating the number of seeds.Then next n lines, each line contains two integer pi
and vi
indicating the times the i-th seed can be put back and the beauty the i-th seed can bring.
输出描述:
Output one real number indicating the expected beauty.
示例1
说明
If you pick 1 at the first round, you will choose to repick. And at the next round no matter what you get you'll have to plant it. The expected beauty is 1.5. If you pick 2 at the first round, you'll certainly plant it, and you get 2 beauty. So the answer is 1.5*0.5+2*0.5=1.75.