shunfurh 于 2017.08.31 17:29 提问

Contest

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 Pij. Suppose he have tried m problems, a1,a2,...am (No matter the problems are solved or not.) (1 ≤ a1,a2,...am ≤ n) If he tries the rth problems next, (r!=a1,a2,...am) the propbility that he can solve it is the maximum value of the m + 1 values, Prr, Pa1r%, Pa2r%, ... Pamr%.

Help him to decide the order he tries the problems to make the expected number of the solved problems maximum.

Input

There 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 Pij. (0 ≤ Pij ≤100 1 ≤ i,j ≤ n)

Output

For 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 Input

2
1
0
2
2 3
5 7
Sample Output

0.00
A
0.12
BA
Hint

For the 2nd sample, if the order is AB:
The probility of the result that he solves problem A is 0.02*(1-0.07)=0.0186
The probility of the result that he solves problem B is (1-0.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 (1-0.07)*0.05=0.0465
The probility of the result that he solves problem B is 0.07*(1-0.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

1个回答

caozhy      2017.09.15 23:46

The Beauty contest game
Keynesian beauty contest A Keynesian beauty contest is a concept developed by John Maynard Keynes and introduced in Chapter 12 of his work, General Theory of Employment Interest and Money (19
[PTA] Review of Programming Contest Rules
#include #include #include int min;//记录最小时间 int max;//记录最多解题数 int time, num, t0; char c[12][22]; int visit[12]; int t[12];//做出该题时间 int d[12]; int path[12]; int count; int index[12]; int size; void
2015 Pacific Northwest Region Programming Contest—Division 2 Problem P — Complexity（字符串、贪心）

2013年成都acm题目
ACM International Collegiate Programming Contest Asia Chengdu Regional Contest
2017 JUST Programming Contest 2.0【solved：11 / 11】
gym 101343 A. On The Way to Lucky Plaza 思路：随手推个概率公式吧。trick点就是读入的时候*1000，需要调一调精度啊？。+0.5什么的。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; const int mod = 1e9 + 7; typedef lon
[BAPC2014]The 2014 Benelux Algorithm Programming Contest Problem Set
The 2014 Benelux Algorithm Programming Contest Problem Set. BAPC2014题目。
【AtCoder】（AtCoder Grand Contest 006）D - Median Pyramid Hard
【AtCoder】（AtCoder Grand Contest 006）D - Median Pyramid Hard 传送门：http://agc006.contest.atcoder.jp/tasks/agc006_d 刚开始不懂，去找大坏人，被告知是套路题。瞬间想到二分后转变为01的问题。 然后又想了很久……（发现还是不懂） 结果被路过的魏爷戳懂了……
AtCoder Regular Contest 093(E-Bichrome Spanning Tree)