提示: 欢迎访问OurACM平台。
Problem 1885 新店

Accept: 21    Submit: 80
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

每到晚上9点后,福大3区门口就会有很多摆摊的,对于像chjing这样经常晚睡的人当然经常光顾。chjing的好友fanxing想在3区门口摆摊,开家新店。但是3区门口的地方不大,所以fanxing只能摆n个座位,由于3区门口摆摊是在一条路的旁边,路不是很宽阔,所以座位只能沿着路,成一条直线摆放,而且每个座位只能坐一个人。

经过几天的调查,fanxing得到了一些数据。就是每次到达摊位的要么1个人,要么就是结伴一起来的,对于结伴一起来的,fanxing会给他们优惠。而且结伴一起来的人数的个数不会超过m。对于那些结伴来的t个人,他们需要一段连续的t个座位,如果没有这样的座位存在,他们就会很扫兴的一起离开。

不同的结伴人数,概率不一样。每个人的收费也不一样。来的人会随机等概率的选择可以坐下的地方(当然,需要是连续的一段)而且坐下后会一起喝酒聊天,直到fanxing打烊收摊。由于FZU的GG和MM很多,所以座位一定会坐到来的人没地方坐为止。

你的任务就是求出一次摆摊,fanxing能赚到的钱的期望值。

Input

第一行,输入整数T,表示以后有T组数据。

每个用例第一行,输入2个数,分别是n和m。(0 < n,m <= 15) n表示fanxing摆放了n个座位,m表示一次结伴来的团体人数不会超过m个人;

下一行有m个实数,第i个实数代表一次结伴来i个人的概率,百分制的,保证i个实数的和是100。

然后下一行又有m个实数,第i个实数代表来i个人,每人收费的价格。数据保证来的人越多,每个人收的价格会越少。

Output

输出一个实数,保留3位小数,代表fanxing一次摆摊挣到的钱的期望值。输出格式见样例输出。每个测试样例后打印一行空行。

Sample Input

3 4 1 100 10 4 2 0 100 20 10 2 2 50 50 20 10

Sample Output

Case 1: 40.000 Case 2: 33.333 Case 3: 30.000

Hint

第一个样例 有4个座位,最多只来1个人,来1个人的概率是%100. 4个座位肯定都能坐满,挣到的钱是4*10=40 第二个样例 有4个座位,最多来的团体是2个人。而且来2个的概率是%100。 这2个人,有 **00 ,0**0,00** 3种坐法,以后再来2个人要么没地方做, 要么只有1种坐法。 而这3种坐法挣到的钱是2*10+2*10 ,2*10, 2*10+2*10 期望值就是这三种坐法挣到的钱100%*(100/3)=33.333; 第三个样例: ## 和**两种 #代表来1 个人,并入座。。 *代表来2个人并一起入座。。 Val(##)=50%*((val(#0)+val(0#))/2+20)=20 因为 Val(0#)=val(#0) 只会有1个人来的情况了,因为其他的肯定坐不进去, 所以再来一个人坐进去的概率是100%,答案是100%*20=20. 所以val(##)=20 而** 表示当两个人一起来的时候。。 期望值是50%*10*2=10 总的期望值是30

Source

chjing

Submit  Back  Status  Discuss