网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
第二试-神奇口袋
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | bag.in | 输出文件 | bag.out |
【任务描述】
Pòlya 获得了一个奇妙的口袋,上面写着人类难以理解的符号。Pòlya 看得入了迷,冥思苦想,发现了一个神奇的模型(被后人称为Pòlya 模型)。为了生动地讲授这个神奇的模型,他带着学生们做了一个虚拟游戏:
游戏开始时,袋中装入a1 个颜色为1 的球,a2 个颜色为2 的球,…,at个颜色为t 的球,其中ai∈Z+ (1≤i ≤t) 。
游戏开始后,每次严格进行如下的操作:
从袋中随机的抽出一个小球(袋中所有小球被抽中的概率相等),Pòlya 独自观察这个小球的颜色后将其放回,然后再把d 个与其颜色相同的小球放到口袋中。
设ci 表示第i 次抽出的小球的颜色(1≤ ci ≤t) ,一个游戏过程将会产生一个颜色序列(c1,c2,…,cn,…)。
Pòlya 把游戏开始时t 种颜色的小球每一种的个数a1,a2,…,at 告诉了所有学生。然后他问学生:一次游戏过程产生的颜色序列满足下列条件的概率有多大?
cx1=y1,cx2=y2,L,cxi=yi,,L,cxn=yn
其中0
【输入格式】
第一行有三个正整数t,n,d;第二行有t 个正整数a1,a2,…,at,表示游戏开始时口袋里t 种颜色的球,每种球的个数。
以下n 行,每行有两个正整数xi,yi,表示第xi 次抽出颜色为的yi 球。
【输出格式】
要求用分数形式输出(显然此概率为有理数)。输出文件包含一行,格式为:
分子/分母。同时要求输出最简形式(分子分母互质)。特别的,概率为0 应输出0/1,概率为1 应输出1/1。
【输入样例】
样例1 的输入
2 3 1 1 1 1 1 2 2 3 1
样例1 的输出
1/12
样例2 的输入
3 1 2 1 1 1 5 1
样例2 的输出
1/3
【样例1 说明】
初始时,两种颜色球数分别为(1, 1),取出色号为1 的球的概率为1/2;第二次取球之前,两种颜色球数分别为(2, 1),取出色号为2 的球的概率为1/3;第三次取球之前,两种颜色球数分别为(2, 2),取出色号为1 的球的概率为1/2,所以三次取球的总概率为1/12。
【评分方法】
本题没有部分分,你的程序的输出只有和我们的答案完全一致才能获得满分,否则不得分。
【数据范围】
1≤t,n≤1000, 1≤ak ,d≤10, 1≤x1