LibreOJ

2615 「SHOI 早期试题选」三国围棋对抗赛

内存限制：8 MB 时间限制：1000 ms

题目描述

中国邀请韩国，日本围棋队来参加三国围棋对抗赛，韩国，日本应邀各派了 $5$ 位超一流高手来参赛，中国围棋队希望能赢得这场比赛，但是这 $10$ 位高手实力不俗。不过中国队作为东道主，可以在对方选手安排好出场顺序后再决定队员的组成以及出场顺序，以得到最大的获胜概率。
比赛规则如下：先抽签决定第 $1$ 轮轮空的队，由不轮空的两支队的 $1$ 号队员进行比赛，失利的队员被淘汰，以后每次由前一轮获胜的队员与前一轮轮空的队剩下的队员中序号最小的队员进行比赛，直到只剩下一个国家的队员为止，这个国家就获得了比赛的胜利。

输入格式

第 $1$ 行为一个数 $n$ ，中国队的候选人数。
接下来是 $n$ 行，每行有 $10$ 个数。
第 $i+1$ 行的 $10$ 个数依次表示第 $i$ 位中国选手对韩国 $1 , \dots , 5$ 号，日本 $1 , \dots , 5$ 号的胜率，胜率 $k$（$0 \le k \le 1$）。
再接下来是 $5$ 行，每行有 $5$ 个数。
第 $i+n+1$ 行的第 $j$ 个数表示韩国 $i$ 号选手对日本 $j$ 号选手的胜率。

输出格式

仅一行，为中国队的最大的获胜概率，保留 $ 6 $ 位小数。

样例

数据范围与提示

对于 $100\%$ 的数据，$5 \le n \le 15$。

来源： SHOI2001

样例

样例输入 1

5
0.902 0.540 0.862 0.283 0.498 0.597 0.900 0.076 0.750 0.539
0.342 0.574 0.743 0.442 0.579 0.502 0.755 0.649 0.835 0.278
0.105 0.704 0.274 0.733 0.725 0.861 0.007 0.314 0.099 0.542
0.785 0.754 0.541 0.331 0.430 0.426 0.928 0.385 0.314 0.892
0.349 0.354 0.408 0.353 0.333 0.180 0.715 0.013 0.563 0.386
0.131 0.564 0.265 0.700 0.033
0.293 0.688 0.140 0.130 0.550
0.346 0.915 0.385 0.536 0.946
0.739 0.051 0.682 0.166 0.436
0.122 0.065 0.724 0.934 0.736

样例输出 1

0.529237