#P2016. 表演艺术(artist)
表演艺术(artist)
【问题描述】
凡和邻家男孩玩完了纸牌,兴致很高,于是准备了一场表演艺术对抗赛。他特意请来了很多表演艺术家,分成绿黑两队,进行名为PK,实则捞金的表演。
凡为了捞金,开设了一个赌局,在比赛开始之前招揽人们来押注谁能胜出,在所有人进行投注之后,凡需要告诉大家绿方和黑方的单位返还金额都是多少。
举个例子,如果绿方的单位返还金额为5,那么我每押1块钱绿方胜,如果成真就能拿回5块钱,但是如果结果绿方输了,我就拿不回来任何钱
凡决定将单位返还金额设得更具有吸引力,所以他要求“绿方胜的单位返还金额+黑方胜的单位返还金额=T”,并且为了赚更多的钱,凡可以在中间某两个投注的人之间更改单位返还金额,但是要求双方的总和仍然为T,并且只能更改一次
不幸的是,凡突然发现自己请来的表演艺术家竟然和众多投注人是一伙的,也就是说,在凡定下单位返还金额之后,那些艺术家会操纵比赛结果,从而让凡拿出更多的钱来
这下凡有些慌了,于是他来询问你应该怎么制定单位返还金额
【输入格式】
第一行一个整数N,代表投注的人的个数
接下来N行,每行两个实数ai,bi代表第i个人投注黑方胜和绿方胜的资金
最后一行一个实数T,含义如题目中所示
【输出格式】
一个实数,代表你最少返还的金额(保留两位小数)
【样例输入1】
3
0 10
10 0
10 0
10
【样例输出1】
0.00
【样例解释1】
一种最优方案是:
第一次投注及之前,单位返还金额为10和0
第二次投注及之后,单位返还金额为0和10
这样无论哪方胜利,你都不会返还任何金钱
【样例输入2】
2
5 5
5 5
1
【样例输出2】
5.00
【样例解释2】
一种最优方案是:
第一次投注及之前,单位返还金额为0.5和0.5
第二次投注及之后,单位返还金额为0.5和0.5
这样无论哪方胜利,你的返还金额都为5
【数据范围与约定】
测试点编号 | N |
---|---|
1 | = 2 |
2 | ≤ 10 |
3 | |
4 | ≤ 1000 |
5 | |
6 | ≤ 100000 |
7 | |
8 | ≤ 500000 |
9 | |
10 |
对于所有数据,0<=ai,bi,T<=100,且至多精确到两位小数
相关
在下列比赛中: