#1743. $N$ 门问题

    ID: 1743 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1088来源:qoj.ac数据:公开样例数学

$N$ 门问题

NN 门问题

题目描述

标题: NN 门问题 - Problem - QOJ.ac

#5377. N 门问题

Statistics

The problem was used in the following contests:

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

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

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

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

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

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

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

输入格式

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

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

接下来 T 行,每行两个整数,ai,bi(0≤ai<bi),代表 N≡ai(modbi)。

输出格式

如果这样的 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,ai≤4。

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

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

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

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

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

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

对于全部数据,T≤5×104,lcm⁡(b1,b2,⋯,bn)≤1018。

提示

贝叶斯公式:假设 B1,B2,⋯,Bn 是 n 个互不相交的事件,且 ∑i=1nP(Bi)=1,则

P(Bi∣A)=P(Bi)P(A∣Bi)∑j=1nP(Bj)P(A∣Bj)

其中,P(Bi∣A) 表示在事件 A 发生的前提下,Bi 事件发生的概率。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
2 1000000007
0.500000

样例 2

1
3 1000000007
0.666667