SP8062 AMR10H - Shopping Rush

A shop-keeper is trying to figure out how to arrange gifts in his shop for Christmas. He runs a peculiar shop such that each customer buys exactly two gifts at the shop (he could buy two of the same gifts too). He knows the probability that a customer might want gift i, is P\_i. He needs to arrange the gifts across several floors. Each floor should have exactly one gift. It takes A\*(|x - y|)^2 + B\*(|x - y|) + C seconds to go from floor x to floor y. Can you help him arrange the gifts across floors such that, the expected time spent by a shopper is minimized? For the purpose of this problem assume that the first gift choice and the second gift choice are independent of each other. i.e., Choosing a first gift as i does not change his probability of choosing the second gift as j. It still remains P\_j. **INPUT** The first line contains the number of test cases T. 2\*T lines follow, 2 per test case. The first line contains 4 integers : N, A, B, C. The second line contains N integers in the range 1 to 100. The ith integer represents the percentage probability P\_i. All P\_i's will sum to 100. **OUTPUT** Output T lines one for each test case. Each line contains the minimum expected travelling time for the corresponding test case. Output the answer as a reduced fraction as below. **CONSTRAINTS** 1

N/A

N/A