XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Korea

这场没罚时的。

Problem A

Solved by zerol. 02:43 (+)

Solved by ultmaster. 02:57 (+4)

题意：A 到 B 有很多桥，每座桥上有若干个点。一座桥上只要有一个点挂了，整座桥就挂了。每个点有一定概率会挂，现在要求用最少的期望次数检测 A 到 B 之间有无通路。

题解：

首先计算每座桥挂了的概率：$s_i$。
其次计算检测第 $i$ 座桥需要的时间：$t_i$（把点按照挂的概率从高到低排个序，然后用期望公式依次算过去就好）。
最后答案等于 $f_i = s_i f_{i+1} + t_i$。我们要找某个排列使得 $f_1$ 最小。你要相信这个东西排个序贪心一下就好了，于是列一个 $n=2$ 的方程解一解。
很怀疑精度不行，正准备把乘法改成 log 加，突然就过了。

Solved by kblack. 03:29 (+13)

盲人签到，听取 WA 声一片。

Solved by zerol. 04:53 (+8)

Unsolved. (-3)