1037. Cutting the Loot
You have a bag holding W units of weight and n items, and unlike the
bag in problem #236 you may take any fraction of an item for a proportional part
of its value.
Print the greatest value you can carry, to exactly two decimal places.
That single change makes the greedy rule correct. Sort by value per unit weight and take the best first, cutting the last item to fit exactly. Because the bag is always filled exactly, no gap is ever wasted, which is the obstruction that made greedy wrong when items could not be cut.
Knowing WHY the rule works here and not there is the point. It is the same pair of problems an interviewer uses to find out whether you can justify a greedy choice or only recognise one.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ W ≤ 1000000000` - `1 ≤ weight[i] ≤ 1000000` - `0 ≤ value[i] ≤ 1000000`
Input
The first line contains two integers n and W.
Each of the next n lines contains two integers: the weight and the value of one item.
Output
Print the greatest value obtainable, to exactly two decimal places.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.