2528: 卡片游戏
题目描述
小 Y 在 NOI2014 的现场举办了一场盛大的联欢活动,其中有一个卡片游戏。游戏的规
则是这样的:有 n 张卡片,每张卡片上正面写着一个小于等于 100 的正整数 ai,反面都是一
样的花色。这 n 张卡片正面朝下叠成一堆,玩这个游戏的人从中可以抽出连续的 k(1≤k≤
n)张卡片。如果对于这 k 张卡片上的数字的平均值 a,满足 l<=a<=r,那他就可以获得小礼
物一件。
小 X 来玩这个游戏了,她事先通过某些途径知道了这 n 张卡片上写的数字(很不厚道),
现在她想知道她获得小礼物的期望值。但是,数学不好的小 X 对小数很头疼,所以请你编
程用分数的形式告诉她答案。
输入
第 1 行为三个整数 n,l,r。
第 2 行,包含 n 个整数 ai。
输出
仅一行,表示小 X 获得小礼物的期望值。
输出格式为“P/Q”(P 和 Q 互质)。
如果期望值是 0 或 1 就不用输出分数了。
样例输入 复制
4 2 3
3 1 2 4样例输出 复制
7/10提示
抽出的卡片 (保留 2 位小数) a 是否满足 l<=a<=r
3 3.00 √
1 1.00
2 2.00 √
4 4.00
3 1 2.00 √
1 2 1.50
2 4 3.00 √
3 1 2 2.00 √
1 2 4 2.33 √
3 1 2 4 2.50 √
由表可得,一共有 10 种情况,其中有 7 种情况小 X 可以获得小礼物。因此,小 X 获得
小礼物的期望值是 7/10。
【输入输出样例 2】
4 1 4
3 1 2 4
1
由上表得,小 X 总是可以获得小礼物。因此期望值是 1。
对于 30%的数据, 0<n≤10,000;
对于 70%的数据, 0<n≤100,000;
对于 100%的数据,0<n≤500,000,0<l<r≤100。