A company can make at most of available trades. Each available trade has the following properties:
- : A floating-point number denoting the trade’s probability of being profitable.
- : A floating-point number denoting the trade’s potential profit.
- : A floating-point number denoting the trade’s potential loss, which has a probability of .
Given the values of , , and , , and for each trade , find and print the maximum expected amount of money the company can make by performing at most of the trades.
The first line contains two space-separated integers denoting the respective values of (the number of trades available) and (the maximum number of trades allowed).
The second line contains space-separated floating-point numbers describing the respective values of , where each denotes the probability that the transaction will result in a profit.
The third line contains space-separated floating-point numbers describing the respective values of , where each denotes the possible profit of the transaction.
The fourth line contains space-separated floating-point numbers describing the respective values of , where each denotes the possible loss of the transaction.
- All , , and are floating-point numbers scaled to exactly one decimal place (i.e., format).
Print the maximum expected amount of money that can be made by performing at most of the available trades. Scale your answer to exactly decimal places (i.e., format).
Sample Input 0
4 2 0.5 0.5 0.5 0.5 4.0 1.0 2.0 3.0 4.0 0.5 1.0 1.0
Sample Output 0
There are transactions available and we can perform at most of them. We also know that the probability that each transaction results in a profit is . If the third and the fourth transactions are performed, the expected amount of money made from these transactions is: ; because this is greater than all the other possibilities we could calculate, we print as our answer (recall that we must scale our answer to two decimal places).
Sample Input 1
2 2 0.9 0.5 1.0 0.5 100.0 0.4
Sample Output 1
There are transactions available and we can perform at most of them. The probability that the first transaction is profitable is , while the probability that the second transaction is profitable is . We can maximize our potential profit by only performing the second transaction, which has an expected value of ; thus, we print as our answer.
Thanks to Maxxy for suggesting the approach here. The approach to solution is : Store probability of profits(p) in a List. Similarly store potential profits(x) and potential loss(y) in two other array lists. Now traverse the lists and store corresponding profits ( calculated as per the formula given in description). profitInEachTrade = P.get(i)*X.get(i)-(1-P.get(i))*Y.get(i); Add the profits in another array List. Sort this array List in reverse order. Now we need all the profits ( i.e, if the value of final array List is greater than zero) and we have to add trades at most k only. So we traverse the list and check if value is greater than zero and count is less than k, we add the values to get the final profit. Using Decimal format or other methods, you can print the value to two decimal places finally.