Problem G
Password Hacking
You have done a lot of hacking using such lists, and you have a good idea of how likely each password in the list is the correct one (you are very surprised by the number of people using “123456” as their passwords). You have a new account to hack, and you have decided to try each of the passwords in the list one at a time, until the correct one is found. You are absolutely sure that the account you want to hack uses a password in the given list.
What is the expected number of attempts to find the correct passwords, assuming that you try these passwords in the optimal order?
Input
The first line of input contains a positive integer $N$, the number of passwords in the list. Each of the next $N$ lines gives the password, followed by a space, followed by the probability that the password is the correct one. Each password consists only of alphanumeric characters and is $1$ to $12$ characters long. Each probability is a real number with $4$ decimal places. You may assume that there are at most $500$ passwords in the list, and that the sum of all probabilities equals $1$. No two passwords in the list are the same.
Output
Output on a single line the expected number of attempts to find the correct passwords using the optimal order. Answers within $10^{-4}$ of the correct answer will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 123456 0.6666 qwerty 0.3334 |
1.3334 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 qwerty 0.5432 123456 0.3334 password 0.1234 |
1.5802 |
