Preparing NOJ
热风哈罗哈(三牌楼)店正在搞活动:他们将提供一个大披萨给第一个告诉他们以下信息的人:一次购买任一种披萨,哪种单位面积的价格最低。问题初步想一想,好像是这么解决:“对于每个披萨计算平均价格,那么最小值就是答案了。”
输入文件包含几个测试用例。每个测试用例包括:
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 两两不同。
对于每个测试用例:
打印一行,为通过一次购买任何一种披萨所能得到的单位面积最低价钱. 四舍五入到小数点后4位。
注意到你能组合任意数目的打折优惠券:对于价格为10的披萨和两个折扣为50和20的优惠券,你将只需支付10 * 0.8 * 0.5 = 4单位的钱。
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
2.6667
1.5000
0.5333
本题由旧版NOJ导入,来源:“IBM南邮杯”团队赛2009