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.
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 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.
1 <= T <= 100
1 <= N <= 20
0 <= A,B,C <= 10
3 0 1 0
60 10 30
1 1 1 0
1 1 1 3
4 3 7 2
25 25 25 25