The manager of the multi-storey department store in my town 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.
Since my wife takes my kid shopping, he begged me to help the manager arrange the gifts across floors such that the expected time spent by a typical shopper such as my wife 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. Do not count the time taken to reach floor x and leave from floor y -- only count the time taken to go from x to y.
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.
1 <= T <= 300
1 <= N <= 22
0 <= A,B,C <= 10
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.
4 3 0 1 0 60 10 30 1 1 1 0 100 1 1 1 3 100 4 3 7 2 25 25 25 25
3/5 0/1 3/1 73/4
Migrated from old NTUJ.
Regional Amritapuri 2010
| No. | Testdata Range | Score |
|---|