#P2612. [ZJOI2012] 波浪
[ZJOI2012] 波浪
题目描述
阿米巴和小强是好朋友。
阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。
于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个 到 的排列 。定义波动强度等于相邻两项的差的绝对值的和,即:
$$L = | P_2 – P_1 | + | P_3 – P_2 | +\ldots + | P_N – P_{N-1} | $$给你一个 和 ,问:随机一个 的排列,它的波动强度不小于 的概率有多大?
答案请保留小数点后 位输出,四舍五入。
输入格式
第一行包含三个整数 和 ,分别表示排列的长度,波动强度,输出位数。
输出格式
第一行包含一个小数点后 位的实数。
3 3 3
0.667
提示
的排列有 个:;他们的波动强度分别为 。所以,波动强度不小于 的概率是 ,即 。
你也可以通过下面的代码来验证这个概率:
int a[3]={0,1,2},s=0,n=3;
for (int i=0;i<1000000;i++){
random_shuffle(a,a+n);
int t=0;
for (int j=0;j<n-1;j++) t+=abs(a[j+1]-a[j]);
if (t>=3) s++;
}
printf("%.3f\n",s/1000000.0);
【数据规模】
对于 的数据,。
对于另外 的数据, 。
对于另外 的数据,。
对于另外 的数据,。
对于 的数据,。