 /**//*
区间[L,R]中每个数出现的概率为1/(R-L+1)
现给出n个区间,[Li,Ri],每个区间抽取出一个数
求这n个数中,至少有K%个数的前缀为1的概率

可以处理出每个区间[Li, Ri]抽取的数前缀为1的概率p[i]
dp[i,j]表示前面i个区间有j个数前缀为1的概率
则转移就是dp[i,j] = dp[i-1,j-1]*p[i] + dp[i-1,j]*(1-p[i])
答案就是∑dp[n,j], j/n >= K%
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

 long long cal(long long x) {//[1,x]
long long cnt = 0 , now = 1;
 while(x/now > 1) {
cnt += now;
now *= 10;
}
 if(x / now == 1) {//x = 1***
cnt += x - now + 1;
}
return cnt;
}

 double cal(long long left, long long right) {
return (cal(right) - cal(left-1)) / (right - left + 1.0);
}

double p[1000], dp[1000][1000];

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif

 for (int n; ~scanf("%d", &n); ) {
long long left, right;
 for (int i = 0; i <n ; i++) {
scanf("%I64d%I64d", &left, &right);
p[i] = cal(left, right);
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1.0;
 for (int i = 1; i <= n; i++) {
 for(int j = 0; j <= i; j++) {
dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j]*(1-p[i-1]);
}
}
int per;
scanf("%d", &per);
double ans = 0;
 for( int j = 0 ; j <= n; j++ ) {
 if(100*j >= n*per) {
ans += dp[n][j];
}
}
printf("%.10f\n", ans);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|