{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"2\u003csup\u003e\u003ci\u003en\u003c/i\u003e\u003c/sup\u003e 支球队进行淘汰赛,编号为 1, 2, …, 2\u003csup\u003e\u003ci\u003en\u003c/i\u003e\u003c/sup\u003e。每一轮都会淘汰若干球队。每一轮开始前,所有未被淘汰的球队按照编号升序排列,不妨设为 $a_1$$\u003c$$a_2$$\u003c…a_{2^i}$。接下来 $a_1$ 与 $a_2$ 竞争, $a_3$ 与 $a_4$ 竞争,以此类推。显然在 $n$ 轮后,最终只剩下一个球队,获得冠军。\n\n给定一个矩阵 $P$,其中 $P_{i,j}$ 表示球队 $i$ 能击败球队 $j$ 的概率。找出成为冠军概率最大的球队。"}},{"title":"Input","value":{"format":"MD","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input test file will contain multiple test cases. Each test case will begin with a single line containing \u003ci\u003en\u003c/i\u003e (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 7). The next 2\u003csup\u003e\u003ci\u003en\u003c/i\u003e\u003c/sup\u003e lines each contain 2\u003csup\u003e\u003ci\u003en\u003c/i\u003e\u003c/sup\u003e values; here, the \u003ci\u003ej\u003c/i\u003eth value on the \u003ci\u003ei\u003c/i\u003eth line represents \u003ci\u003ep\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e. The matrix \u003ci\u003eP\u003c/i\u003e will satisfy the constraints that \u003ci\u003ep\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e \u003d 1.0 − \u003ci\u003ep\u003csub\u003eji\u003c/sub\u003e\u003c/i\u003e for all \u003ci\u003ei\u003c/i\u003e ≠ \u003ci\u003ej\u003c/i\u003e, and \u003ci\u003ep\u003csub\u003eii\u003c/sub\u003e\u003c/i\u003e \u003d 0.0 for all \u003ci\u003ei\u003c/i\u003e. The end-of-file is denoted by a single line containing the number −1. Note that each of the matrix entries in this problem is given as a floating-point value. To avoid precision problems, make sure that you use either the \u003ccode\u003edouble\u003c/code\u003e data type instead of \u003ccode\u003efloat\u003c/code\u003e.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cp\u003eThe output file should contain a single line for each test case indicating the number of the team most likely to win. To prevent floating-point precision issues, it is guaranteed that the difference in win probability for the top two teams will be at least 0.01.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n0.0 0.1 0.2 0.3\n0.9 0.0 0.4 0.5\n0.8 0.6 0.0 0.6\n0.7 0.5 0.4 0.0\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eIn the test case above, teams 1 and 2 and teams 3 and 4 play against each other in the first round; the winners of each match then play to determine the winner of the tournament. The probability that team 2 wins the tournament in this case is:\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003ctable border\u003d\"0\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd valign\u003d\"top\"\u003eP(2 wins)\u0026nbsp;\u003c/td\u003e\u003ctd\u003e\u003d \u003ci\u003eP\u003c/i\u003e(2 beats 1)\u003ci\u003eP\u003c/i\u003e(3 beats 4)\u003ci\u003eP\u003c/i\u003e(2 beats 3) + \u003ci\u003eP\u003c/i\u003e(2 beats 1)\u003ci\u003eP\u003c/i\u003e(4 beats 3)\u003ci\u003eP\u003c/i\u003e(2 beats 4)\u003cbr\u003e\u003d \u003ci\u003ep\u003c/i\u003e\u003csub\u003e21\u003c/sub\u003e\u003ci\u003ep\u003c/i\u003e\u003csub\u003e34\u003c/sub\u003e\u003ci\u003ep\u003c/i\u003e\u003csub\u003e23\u003c/sub\u003e + \u003ci\u003ep\u003c/i\u003e\u003csub\u003e21\u003c/sub\u003e\u003ci\u003ep\u003c/i\u003e\u003csub\u003e43\u003c/sub\u003e\u003ci\u003ep\u003c/i\u003e\u003csub\u003e24\u003c/sub\u003e\u003cbr\u003e\u003d 0.9 · 0.6 · 0.4 + 0.9 · 0.4 · 0.5 \u003d 0.396.\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/div\u003e\u003cp\u003eThe next most likely team to win is team 3, with a 0.372 probability of winning the tournament.\u003c/p\u003e\u003c/span\u003e"}}]}