QOJ.ac

QOJ

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

#5377. $N$ 门问题

الإحصائيات

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

现在她的面前有 $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$ 事件发生的概率。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.