Shopping Rush

시간 제한1초메모리 제한1024 MB

요약

두 선물 선택이 서로 독립일 때, N개의 선물을 서로 다른 층에 배치해 두 선택 사이 이동 시간의 기댓값이 최소가 되도록 하고 기약분수로 출력한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

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.

출력

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

예제1

예제 1

입력

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