#1743. $N$ 门问题
$N$ 门问题
门问题
题目描述
标题: 门问题 - Problem - QOJ.ac
#5377. N 门问题
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