# Black-White Balls

## 题目描述

$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$.

## 算法分析

$$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}}$$

## 代码

#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;
}


418 I'm a teapot