2 shunfurh 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
caozhy   Ds   Rxr 2017.09.15 23:46
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
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(字符串、贪心)
题意:给你一个字符串,定义复杂度为字符的种类。问你最少删除几个字符,能使种类最多为两种? 题目还行,注意一点,aabbbcccc这种情况,不要光判断种类数。 代码如下,用了一点简单的hash。 #include using namespace std; int main() { char s[1000]; int has[1000];//那个字母出现几次 int p[
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)
题意: &amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;\ \ \ \ \ 给出一个NNN个点MMM条边的无向图,现在要给一些边染黑色或者白色,现在从这些边中选出一些边生成若干棵生成树,要求这些生成树至少包含一条白色的边和一条黑色的边,而且这些生成树的最小值是XXX,问有多少种染色方法。 思路: &amp;nbsp;&amp;nbsp;...
ADS-WK11-Review of Programming Contest Rules-回溯剪枝
【题目】 The ACM ICPC's rule of scoring is as the following: A problem is solved when it is accepted by the judges. Teams are ranked according to the most problems solved. For the purposes of awar
PTA Review of Programming Contest Rules
按照ACM/ICPC的比赛计分规则(解题数+20分钟罚时规则),给定比赛时间、总题数。 假设某个人是这样做题的: 1. 用一定时间通读所有的题,计算出解出每个题目所需的时间,以及如果错了,调试一次所需的时间。 2. 他一旦开始做某题,不做出来就不换题(一不做二不休)。 3. 对于每道题,他第一次提交的时间决定了他需要调试的次数。