首页 > 试题广场 >

招聘会小礼品

[编程题]招聘会小礼品
  • 热度指数:109 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
小摩召开了一场招聘会,招聘会现场一共有N个人,Mobike公司给大家准备了一些小礼品。但是我们并不知道每个人具体喜欢什么,
现在库房共有M种小礼品,每种小礼品有Ci件,共N件。而我们大致知道每个人选择某种小礼品的概率,
即能知道Pij(编号为i的人选择第j种小礼品的概率)。现在所有人按编号依次领小礼品(第1个人先领,第N个人最后领),
领小礼品时,参加者会按照预先统计的概率告诉准备者自己想要哪一种小礼品,
如果该种小礼品在他之前已经发放完了则他会领不到小礼品,请帮我们计算出能能领到小礼品的期望人数。

输入描述:
第一行包含两个整数N(1≤N≤300),M(1≤M≤100),用单个空格隔开。表示公有N个应聘者,M种小礼品。
第二行为M个整数,依次为Ci,第i种小礼品的个数。
接下来的N行,每行M个实数,依次为Pij,第i个人选择第j种小礼品的概率。


输出描述:
一行输出期望人数。结果保留1位小数。
示例1

输入

2 2
1 1
0.3 0.7
0.7 0.3

输出

1.6

说明

(样例解释:共有4种选择(1,1),(1,2),(2,1),(2,2),概率分别为0.21、0.09、0.49、0.21,(1,1),(2,2)这两种选择只有1个人能拿到小礼品,(1,2),(2,1)这两种选择有2个人能拿到小礼品,所以期望为1*(0.21+0.21) + 2*(0.09+0.49) = 1.58,保留一位小数为1.6。)
def prizeGetFunc(N,M,C,P):     """"     Parameters     ----------     N :   number of interviewees     M :   kinds of the gifts     C :   number of each gift     P :   preferential matrix     """     leftPrize = 0     # initiate the number of prizes left     for j in range(M):         if C[j] < 1:             prizeLeftPro = [0]         else:             prizeLeftPro = [0]*C[j]+[1]  # initialize the left prob of each prize (from 0 to C[j])             for i in range(N):                     prizeLeftPro[0] += prizeLeftPro[1] * P[i][j] # left 0, prizes of kind i are all given                     for k in range(C[j]):                         prizeLeftPro[k] = prizeLeftPro[k]*(1-P[i][j]) + prizeLeftPro[k+1]*P[i][j] # update the p_k                     prizeLeftPro[C[j]] = prizeLeftPro[C[j]]*(1-P[i][j])         for k in range(1,C[j]+1):             leftPrize += prizeLeftPro[k]*k # calculate the expected number of prizes left     getPrize = round(N-leftPrize,2)     return getPrize N,M = map(int,raw_input().split()) C = map(int,raw_input().split()) P = [map(float,raw_input().split()) for i in range(N)] getPrize = prizeGetFunc(N,M,C,P) print getPrize  

编辑于 2018-08-02 00:42:31 回复(0)