AMR10H - Shopping Rush

no tags 

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


hide comments

Added by:Varun Jalan
Time limit:0.916s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem, ICPC Asia regionals, Amritapuri 2010