新生舞会
测试数据来自 system/2016
描述
学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。(学姐我要和你跳舞!)
有n个男生和n个女生参加舞会,一个男生和一个女生一起跳舞,互为舞伴。(学姐你的舞伴是我!)
Cathy收集了这些同学之间的关系,比如两个人之前是否认识,计算出\(a_{i,j}\),表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。
Cathy还需要考虑两个人一起跳舞是否方便,比如身高体重差别会不会太大,计算得出\(b_{i,j}\),表示第i个男生和第j个女生一起跳舞的时候的不协调程度。
当然还需要考虑很多其它问题。
Cathy想用一个程序通过\(a_{i,j}\)和\(b_{i,j}\)求出一种方案,再手动对方案进行微调。
Cathy找到你,希望你帮她写那个程序。
一个方案中有n对舞伴,假设每对舞伴的喜悦程度分别是\(a_1^{'},a_2^{'},\cdots,a_n^{'}\),假设每对舞伴的不协调程度分别是\(b_1^{'},b_2^{'},\cdots,b_n^{'}\),令
\(C={{a_1^{'}+a_2^{'}+\cdots+a_n^{'}} \over {b_1^{'}+b_2^{'}+\cdots+b_n^{'}}}\)
Cathy希望C值最大。
格式
输入格式
第一行一个整数n。
接下来n行,每行n个正整数,第i行第j个数表示\(a_{i,j}\)。
接下来n行,每行n个正整数,第i行第j个数表示\(b_{i,j}\)。
输出格式
一行一个数,表示C的最大值,四舍五入保留6位小数。选手输出的小数需与标准输出相等。
样例1
样例输入1
3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9
样例输出1
5.357143
限制
对于10%的数据,\(1\le n\le 5\)
对于40%的数据,\(1\le n\le 18\)
另外存在20%的数据,\(b_{i,j}=1\)
对100%的数据,\(1\le n\le 100\),\(1\le a_{i,j}\le 10^4\),\(1\le b_{i,j}\le 10^4\)
来源
SDOI 2017 Round1 Day2
信息
- ID
- 1948
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者