/**//* 区间[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
搜索
最新评论
|
|