
ZOJ Problem Set  3502
Lazyman is going to join the programming contest! There are n problems in the contest. Because Lazyman is so lazy, he just tried each problem once and only once. However each problem in the contest may be not independent, it may have some relationship with other problems. So here is a propbility P n*n matrix. The jth element of the ith row is denoted by P_{ij}. Suppose he have tried m problems, a_{1},a_{2},...a_{m} (No matter the problems are solved or not.) (1 ≤ a_{1},a_{2},...a_{m} ≤ n) If he tries the rth problems next, (r!=a_{1},a_{2},...a_{m}) the propbility that he can solve it is the maximum value of the m + 1 values, P_{rr}, P_{a1r}%, P_{a2r}%, ... P_{amr}%. Help him to decide the order he tries the problems to make the expected number of the solved problems maximum. InputThere are multiple test cases. The first line of input is an integer T (0 < T ≤ 100), indicating the number of test cases. Then T test cases follow. The first line of each test case is a positive integer n (0 < n ≤ 10). Then comes n lines. The jth element of the ith line is an integer P_{ij}. (0 ≤ P_{ij} ≤100 1 ≤ i,j ≤ n) OutputFor each test case, output 2 lines. The first line is the maxmum expected number of problems, accurated to the nearest 0.01. The second the order he should try each problems to achieve this expected number of problems. If there are several sequeces achieve the same maximum expected number, choose the lexicographically smallest one. Use capital letters to denote each problems please. (Start from A) Sample Input2 1 0 2 2 3 5 7 Sample Output0.00 A 0.12 BA HintFor the 2nd sample, if the order is AB: The probility of the result that he solves problem A is 0.02*(10.07)=0.0186 The probility of the result that he solves problem B is (10.02)*0.07=0.0686 The probility of the result that he solves problem A and B is 0.02*0.07=0.0014 So the expected number of the problem sovled is 1*0.0186+1*0.0686+2*0.0014=0.09 For the 2nd sample, if the order is BA: The probility of the result that he solves problem A is (10.07)*0.05=0.0465 The probility of the result that he solves problem B is 0.07*(10.05)=0.0665 The probility of the result that he solves problem A and B is 0.07*0.05=0.0035 So the expected number of the problem sovled is 1*0.0465+1*0.0665+2*0.0035=0.12 Author: CAO, Peng 