QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 5377. $N$ 门问题

Statistics

瑞丝参加了一个抽(猜)奖活动。

现在她的面前有 $N$($N>2$)扇门,只有 $1$ 扇门的背后有大奖,其余的门后都是空的。 活动有一个主持人,她事先知道哪扇门后有大奖。每次当瑞丝选择一扇门(不打开)后, 主持人会从剩下的没有打开的且不是对应大奖的门中,等概率地随机挑选一扇门打开,然后再给瑞丝一次选择门的机会(瑞丝可以选择保持之前的选择不变或者换成任意一扇 她想要的门),直到只剩两扇门为止,此时瑞丝的选择就是她的最终选择。

瑞丝想获得大奖,但她不知道任何信息,于是她决定每次在“所有可选的门”中挑选一个“在她的视角中背后有奖的概率最大”的门,如果这样的门有多个,则她会在其中等概率地随机挑选一个。(显然第一次选门时,她的视角中每扇门背后有大奖的概率都是 $\displaystyle\frac{1}{N}$,所以她会随机在 $N$ 扇门中选一扇)

换言之.瑞丝选门的过程可以抽象为以下过程:

while (剩余门的数址 ≥ 2):
    瑞丝按照上文所述选定一扇门,不打开
    if (剩余门的数卅==2):
        这扇门是瑞丝的最终选择;break;
    主持人按照上文所述打开一瑚门(同时意味着剩余门的数量-1)
    瑞丝重新计算每扇门后有奖的概率

现在活动主办方安排你作为主持人,并要求你暗箱操作一手,换言之你每次可以在剩下的门中(除了瑞丝选择的和最终大奖的门之外)主动选择某扇门(而非随机地)来打开,目的就是让瑞丝最终选择到大奖门的概率最小。现在给你 $N$,求这个最小的概率。

注意:瑞丝并不知道你的存在。换言之,她依然认为主持人是正常的而不会去揣测他的用意。

输入格式

由于一些原因,输入由一系列同余方程构成,题中 $N$ 为该同余方程的最小非负整数解。

第一行,一个正整数 $T$,代表同余方程的个数。

接下来 $T$ 行,每行两个整数,$a_i, b_i$($0 \leq a_i < b_i$),代表 $N \equiv a_i \pmod {b_i}$。

输出格式

如果这样的 $N$ 不存在,或者 $N < 2$,输出一行“error”(不含引号),否则输出一个六位小数,代表问题的答案。评测采用全文比较

样例数据

样例 1 输入

1
2 1000000007

样例 1 输出

0.500000

样例 2 输入

1
3 1000000007

样例 2 输出

0.666667

样例 2 解释

这是经典的三门问题。

初始时瑞丝有 $1/3$ 的概率选到正确的门,此时无论你的选择如何,瑞丝都会选择换门导致最终选择错误。

另 $2/3$ 的情况下,你没有选择的余地,只能为瑞丝排除错误选项后目送她换到正确的门上。

子任务

子任务 1(5 分):$T = 1$,$a_i \leq 4$。

子任务 2(10 分):$T \leq 10$,如果 $N$ 存在,则 $N \leq 6$。

子任务 3(10 分):$T \leq 10$,如果 $N$ 存在,则 $N \leq 8$。

子任务 4(10 分):$T \leq 10$,如果 $N$ 存在,则 $N \leq 10$。

子任务 5(5 分):如果 $N$ 存在,则 $N \leq 200$。

子任务 6(25 分):保证 $b_i$ 两两互素。

子任务 7(35 分):无特殊性质。

对于全部数据,$T \leq 5 \times 10^4$,$\operatorname{lcm}(b_1, b_2, \cdots, b_n) \leq 10^{18}$。

提示

贝叶斯公式:假设 $B_1, B_2, \cdots, B_n$ 是 $n$ 个互不相交的事件,且 $\displaystyle \sum_{i=1}^n P(B_i) = 1$,则

$$P(B_i \mid A) = \frac{P(B_i)P(A \mid B_i)}{\sum_{j=1}^n P(B_j)P(A \mid B_j)}$$

其中,$P(B_i \mid A)$ 表示在事件 $A$ 发生的前提下,$B_i$ 事件发生的概率。