TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

作為最強的勇者兼鍛造師,阿姆斯特最近決定強化他的阿姆斯特朗炮。
現在有 $n$ 個強化槽和 $n$ 個強化石,
對於每個強化槽,阿姆斯特都能計算出使用每種強化石的成功率,也就是形如 $p\%$ 的百分比值($=p/100$)
每個強化石都只能給一個強化槽用,最終強化的成功率是所有強化槽成功率乘在一起。
阿姆斯特希望最終強化的成功率越高越好,他請他最好的夥伴,也就是你,幫忙計算最終強化的成功率的理論最大值。

Input Format

第一行有一個正整數 $n$,代表強化槽的個數
接下來有 $n$ 行,每行有 $n$ 個非負整數,第 $i$ 行的第 $j$ 個數 $p_{ij}$,代表的是第 $i$ 個強化槽選第 $j$ 種強化石的成功率。

  • $1\le n\le20$
  • $0\le p_{ij} \le 100$

Output Format

請輸出可能達到的最終強化的成功率的百分比值(四捨五入至小數第二位)

Sample Input 1

2
38 65
82 30

Sample Output 1

53.30

Hints

Problem Source

TIOJ 1554

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~21 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2