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

题意概述

袋子里有$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;
}

Panda’s Birthday Present

题目描述

On Panda’s Birthday party, he received a strange present from Jason. The present is a black box with $4$ dices in it which is used to play a game. The dice in the box is unusual. Instead of the digits, only red or blue is painted on each side of the dice. Before the first round of the game, the box can repaint every side of every dice red or blue with equal probability. Then for each round of the game, the box will roll the $4$ dices and tell the player the number of red side facing up, which is the point the player get. Now, Panda has play it for two rounds and he tell you the point he has got for each round. Can you tell him the expected point he can get for next round.

题意概述

一个盒子里有四个骰子,初始时它们每一面都被等概率染成红色或蓝色(你并不知道具体的染色方案)。每次你会摇动盒子,然后观察有几个骰子朝上的面是红色的。给定前两次观察到的值$p, q$,求第三次观察到的值的期望。

算法分析

为了方便起见,我们假设$0^0=1$。首先可以知道的结论:

  1. 对于一个骰子,它有$t$个面被染成红色的概率$P(x=t)={{6 \choose t} \over 2^6}={{6 \choose t} \over 64}$;
  2. 扔一个骰子$n$次,其中有$k$次朝上的面是红色的概率为$\sum_{i=0}^6 P(x=i) \cdot {i^k(6-i)^{n-k} \over 6^n}$。

考虑不管是一次操作中的多个骰子还是多次操作,它们其实是独立重复实验,与顺序无关。因此,只要$p+q$是确定的,那么第三次的期望也是确定的。令$1$表示红色面朝上、$0$表示蓝色面朝上,那么我们所要求的就是$P(??1|??)$,其中$??$表示前两次骰子朝上的面分别是什么。
根据贝叶斯定理,$P(H|E)={P(H)P(E|H) \over P(E)}$,所以$P(111|11)={P(111)P(11|111) \over P(11)}$。经计算可得
$$
\begin{align}
P(111|11)&={9 \over 14} \\
P(101|10)&={1 \over 2} \\
P(001|00)&={5 \over 14}
\end{align}
$$
再次考虑独立重复实验。因为它们可以任意交换顺序,所以可以直接将前两次朝上的面是红色的骰子两两并在一起算,朝上的面是蓝色的骰子两两并在一起算,若有剩下的一对红色蓝色则将它们并在一起。
具体来说,若$2 \mid p+q$,则期望为
$${p+q \over 2} \cdot {9 \over 14}+\left(4-{p+q \over 2}\right) \cdot {5 \over 14}={p+q+10 \over 7}$$
否则,期望为
$${p+q-1 \over 2} \cdot {9 \over 14}+\left(4-{p+q+1 \over 2}\right) \cdot {5 \over 14}+{1 \over 2}={p+q+10 \over 7}$$

Meeting

题目描述

Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between $X$ o’clock and $Y$ o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than $Z$ minutes for the other one (they calculated that, if the other one will not come within $Z$ minutes from the arrival of the first of them, then it is very probable that he will not show up at all).
Knowing that, in the end, both of them will show up at some time between $X$ o’clock and $Y$ o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet.

题意概述

给定整数$X, Y$和实数$Z$,在$X$时到$Y$时之间任选两个时刻,求时刻之差不超过$Z$分钟的概率。
数据范围:$0 \le X \lt Y \le 24, \; 0 \lt Z \le 60(Y-X)$。

算法分析

在平面直角坐标系内以第一个时刻为$x$轴、第二个时刻满足要求的概率为$y$轴画出一个封闭图形,那么答案就是这个图形的面积除以$X$时与$Y$时之差。分两种情况讨论:$2Z \le 60(Y-X)$和$2Z \gt 60(Y-X)$。两种情况得到的封闭图形均为一个${Z \over 60(Y-X)} \times 60(Y-X)$的矩形加上一个下底长$60(Y-X)$的梯形(上底可为$0$)。前者上底加下底为$2(60(Y-X)-Z)$,高为${Z \over 60(Y-X)}$;后者上底加下底为$2Z$,高为$(1-{Z \over 60(Y-X)})$。

代码

#include <cstdio>

using namespace std;

struct Solver {
private:
  int x, y; double z;
  void input() { scanf(" %d %d %lf", &x, &y, &z); }
  void process() {
    int all = (y - x) * 60;
    double sum = 0;
    if (2 * z <= all) sum = z + 2 * (all - z) * (z / all) / 2;
    else sum = z + 2 * z * (1 - z / all) / 2;
    printf("%.8lf\n", sum / all);
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

Petya and Tree

题目描述

One night, having had a hard day at work, Petya saw a nightmare. There was a binary search tree in the dream. But it was not the actual tree that scared Petya. The horrifying thing was that Petya couldn’t search for elements in this tree. Petya tried many times to choose key and look for it in the tree, and each time he arrived at a wrong place. Petya has been racking his brains for long, choosing keys many times, but the result was no better. But the moment before Petya would start to despair, he had an epiphany: every time he was looking for keys, the tree didn’t have the key, and occured exactly one mistake. “That’s not a problem!”, thought Petya. “Why not count the expectation value of an element, which is found when I search for the key”. The moment he was about to do just that, however, Petya suddenly woke up.
Thus, you are given a binary search tree, that is a tree containing some number written in the node. This number is called the node key. The number of children of every node of the tree is equal either to $0$ or to $2$. The nodes that have $0$ children are called leaves and the nodes that have $2$ children, are called inner. An inner node has the left child, that is the child whose key is less than the current node’s key, and the right child, whose key is more than the current node’s key. Also, a key of any node is strictly larger than all the keys of the left subtree of the node and strictly smaller than all the keys of the right subtree of the node.
Also you are given a set of search keys, all of which are distinct and differ from the node keys contained in the tree. For each key from the set its search in the tree is realised. The search is arranged like this: initially we are located in the tree root, if the key of the current node is larger that our search key, then we move to the left child of the node, otherwise we go to the right child of the node and the process is repeated. As it is guaranteed that the search key is not contained in the tree, the search will always finish in some leaf. The key lying in the leaf is declared the search result.
It is known for sure that during the search we make a mistake in comparing exactly once, that is we go the wrong way, but we won’t make any mistakes later. All possible mistakes are equiprobable, that is we should consider all such searches where exactly one mistake occurs. Your task is to find the expectation (the average value) of the search result for every search key, considering that exactly one mistake occurs in the search. That is, for a set of paths containing exactly one mistake in the given key search, you should count the average value of keys containing in the leaves of those paths.

题意概述

给定一棵包含$n$个节点的二叉搜索树,每个节点都有$0$个或$2$个儿子。如果一个节点有儿子,那么它左子树中的所有节点的值都严格小于这个节点,它右子树中的所有节点的值都严格大于这个节点。由于一些差错,这棵搜索树在查找一个值时总是会犯恰好一次错误——应该往左查找时却往右查找,应该往右查找时却往左查找。现有$k$个树中不存在的值待查找,求每一次查找得到的数的期望。
数据范围:$3 \le n \lt 10^5, \; 1 \le k \le 10^5$。

算法分析

很容易想到暴力的方法:先DFS预处理出每棵子树中的最大值和最小值,接着对于每一个待查找的值,直接在树中查找;若应该往左子树走,则将答案加上右子树中的最小值,否则加上左子树中的最大值,然后往正确的方向走。由于这并不是一棵平衡树,因此最坏情况的时间复杂度为$O(n^2)$。
搜索树中的数将数字划分成了$(n+1)$个区间。对于每一个区间而言,其答案都是一样的。因此,我们可以再进行一次DFS,处理出每个区间的答案。处理方法类似于暴力,但是搜索完一棵子树后需要回溯。最后查找$k$个数时,只需对每个数二分查找属于哪个区间,并输出那个区间的答案。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct node_type {
  long long val, min, max, child[2];
} node[100001];
long long n, k, cnt, times, root, top, id[100001];
double ans[100001];
void dfs(long long t) {
  if (!node[t].child[0]) {
    node[t].min = node[t].max = node[t].val; return;
  }
  dfs(node[t].child[0]), dfs(node[t].child[1]);
  node[t].min = node[node[t].child[0]].min, node[t].max = node[node[t].child[1]].max;
}
void find(long long t) {
  if (!node[t].child[0]) {
    id[top] = node[t].val, ans[top++] = 1.0 * cnt / times; return;
  }
  cnt += node[node[t].child[1]].min, ++times, find(node[t].child[0]), id[top++] = node[t].val;
  cnt += node[node[t].child[0]].max - node[node[t].child[1]].min, find(node[t].child[1]);
  cnt -= node[node[t].child[0]].max, --times;
}
int main()
{
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i) {
    long long a; scanf("%lld%lld", &a, &node[i].val);
    if (a == -1) root = i;
    else if (!node[a].child[0]) node[a].child[0] = i;
      else {
        node[a].child[1] = i;
        if (node[node[a].child[0]].val > node[node[a].child[1]].val)
          node[a].child[0] ^= node[a].child[1] ^= node[a].child[0] ^= node[a].child[1];
      }
  }
  dfs(root), find(root), scanf("%lld", &k);
  for (int i = top - 2; i >= 0; --i) if (!ans[i]) ans[i] = ans[i + 1];
  while (k--) {
    long long a, l = 0, r = top; scanf("%lld", &a);
    while (l + 1 < r) {
      long long mid = l + r >> 1; if (id[mid] < a) l = mid; else r = mid;
    }
    printf("%.10lf\n", ans[l]);
  }
  return 0;
}

Coupons

题意概述

一共有$n$种不同的优惠券,每次得到每种优惠券的概率相同。问期望多少次可以得到所有种类的优惠券,以带分数形式输出。
数据范围:$1 \le n \le 33$。

算法分析

假设当前已经有$k$种优惠券,那么获得新优惠券的概率是${n-k \over n}$,所以需要步数的期望是${n \over n-k}$。求和得到总步数的期望是${n \over n}+{n \over n-1}+{n \over n-2}+…+{n \over 1}=n\sum_{i=1}^n{1 \over i}$。