Yogurt Expiration Date
Time limit2sMemory limit128 MB
Pick k yogurts with maximum total amount, break ties by minimizing the chance at least one is defective, and print that incident probability as a percentage.
- Level
Medium5 of 10
- Topics
- Greedy, Sorting, Probability, Math
- Solved
- No attempts yet
Problem
Several yogurts all expire on the same day. Hyunsoo will choose exactly k of them to drink.
The i-th yogurt has amount U_i and an integer probability P_i% of being defective. If he drinks at least one defective yogurt, the incident occurs.
The chosen k yogurts must first maximize the total amount. If multiple choices have that maximum total amount, choose one that minimizes the probability of the incident. Assume the defect events of different yogurts are independent.
Compute the probability of the incident as a percentage.
Input
The first line contains the number of yogurts n and the number of yogurts to drink k.
1 <= k <= n <= 1,000,000
Each of the next n lines contains the amount U_i of one yogurt and its defective probability P_i.
1 <= U_i <= 1,000,001
0 <= P_i <= 10
All input values are integers.
Output
Print the probability, as a percentage, that at least one selected yogurt is defective.
Round the value to three digits after the decimal point. If the rounded value is less than 0.001, print GG.