#P18621. Testing Subjects Usually Die
Testing Subjects Usually Die
Testing Subjects Usually Die
“你好,再次欢迎来到光圈科技拓展中心。”
你在一个陌生的房间里醒来,一个机械声音向你打招呼。你正在参与一系列不太符合伦理的实验。
本次实验中,人工智能从 到 中选取一个整数。它选择整数 的概率为
你需要猜出这个整数。如果猜错,你会再次被催眠,记忆被清除,然后重新接受同一个实验。此时,以 的概率,人工智能会按照上述分布重新选取一个整数;以 的概率,选中的整数保持不变。
你不知道自己已经参加过多少次实验,也不知道此前猜过哪些数。因此,你将选择一个固定的概率分布 ,并在每次猜测时以概率 回答整数 。
你希望尽早完成实验。求在最优选择该分布时,直到猜对为止所需猜测次数的最小期望。猜对的那一次也计入猜测次数。
概率分布要求 ,且 。允许某些 。
输入格式
第一行包含两个整数 ,其中 ,。 是以百分数表示的整数。
第二行包含 个整数 ,其中 。
输入只有一组数据。
输出格式
输出一个浮点数,表示所求的最小期望猜测次数。
如果答案的绝对误差或相对误差不超过 ,则认为正确。等价地,设标准答案为 、提交答案为 ,要求
样例输入 1
4 100
25 25 25 25
样例输出 1
4
样例输入 2
2 0
1 4
样例输出 2
1.800000000