## 题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.

Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.

You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

## 题意概述

袋子里有$n$个球，每个球可能是黑色或白色。已知黑球个数在$0, 1, \ldots, n$之间等概率分布。现在从中取出$l$个球，其中有$l_1$个黑球和$l_2$个白球（$l_1+l_2=l$）。要求找到一个最短的区间$[a, b]$，使得黑球个数在$[a, b]$中的概率至少为${p \over 100}$。若有多个这样的区间，输出$a$最小的。

数据范围：$1 \le n \le 50, \; 0 \le l_1 \le n, \; 0 \le l_2 \le n-l_1, \; 0 \le p \le 100$。

## 算法分析

令事件$A$为取出的$l$个球中有$l_1$个黑球，事件$B_i$为袋子里有$i$个黑球。根据贝叶斯定理

$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$

而我们知道

$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$

因此可以计算出$P(B_i|A)$，接下来只要枚举区间即可。

## 代码

#include <algorithm> #include <cstdio> #include <cstring> static int const N = 55; double a[N]; double get_c(int n, int m) { if (n < m) return 0; double ret = 1; for (int i = 0; i < m; ++i) ret *= 1. * (n - i) / (m - i); return ret; } int main() { int n, l1, l2, p; scanf("%d%d%d%d", &n, &l1, &l2, &p); double b = 0; for (int i = 0; i <= n; ++i) b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2); for (int i = 1; i <= n + 1; ++i) for (int j = 0; j + i - 1 <= n; ++j) { double sum = 0; for (int k = j; k <= j + i - 1; ++k) sum += a[k]; if (sum / b * 100 + 1e-12 >= p) return printf("%d %d\n", j, j + i - 1), 0; } return 0; }