Preparing NOJ

哈罗哈的大披萨 【淡蓝】

1000ms 65536K

Description:

热风哈罗哈(三牌楼)店正在搞活动:他们将提供一个大披萨给第一个告诉他们以下信息的人:一次购买任一种披萨,哪种单位面积的价格最低。问题初步想一想,好像是这么解决:“对于每个披萨计算平均价格,那么最小值就是答案了。”

但是,这个问题不是这么简单,因为在热风哈罗哈店里:对某些披萨,是送打折优惠券的,凭这些优惠券可以得到另一个便宜些甚至差点的披萨,这些优惠券可合并使用。披萨必须一个接一个的买,不可能使用优惠券对一个已买的披萨打折。你能第一个解决这个问题,得到大披萨吗?

Input:

输入文件包含几个测试用例。每个测试用例包括:

l       1行:一个数m,为热风哈罗哈提供披萨数目。当m=0时输入终止。一般1 m 15

l       随后的m 行描述每个披萨。每一行描述披萨i (1 i m) ,开始3个整数pi, ai ni 表示披萨的价格、面积、和购买它时得到的打折优惠券数目,1 pi 10000, 1 ai 10000 , 0 ni < m

l       随后是ni 对整数xi,j yi,j 表示你得到打折的披萨序号xi,j (1 xi,j m, xi,j i) 以及买披萨xi,j得到的折扣yi,j,以百分比表示(1 yi,j 50)。可以假设对于每个i xi,j 两两不同。

Output:

对于每个测试用例     

打印一行,为通过一次购买任何一种披萨所能得到的单位面积最低价钱. 四舍五入到小数点后4位。

注意到你能组合任意数目的打折优惠券:对于价格为10的披萨和两个折扣为5020的优惠券,你将只需支付10 * 0.8 * 0.5 = 4单位的钱。

Sample Input:

1
80 30 0
2
200 100 1 2 50
200 100 0
5
100 100 2 3 50 2 50
100 100 1 4 50
100 100 1 2 40
600 600 1 5 10
1000 10 1 1 50
0

Sample Output:

2.6667
1.5000
0.5333

Note:

本题由旧版NOJ导入,来源:“IBM南邮杯”团队赛2009

Info

NOJ

Provider NOJ

Code NOJ1116

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet