← 返回题目列表

Codeforces · 618/G

G. 结合史莱姆

中文机器翻译题面 查看原题

你的朋友最近送给你一些史莱姆作为你的生日礼物。您有大量价值为 1 和 2 的史莱姆,并且您决定使用这些史莱姆发明一款游戏。

您用 n 个空格初始化一行。您还可以选择要在游戏中使用的数字 p。然后,您将在最后一个空格为空时执行以下步骤。

1. 以 $${ \frac { p } { 1 0 ^ { 9 } } }$$ 的概率,您将选择值为 1 的史莱姆,以 $$1 - \frac{p}{10^9}$$ 的概率,您将选择值为 2 的史莱姆。您将所选史莱姆放在棋盘的最后一个空格上。
2. 您将把史莱姆推到尽可能远的地方。如果它遇到另一个史莱姆,并且它们具有相同的值 v,则将这些史莱姆合并在一起以创建值为 v + 1 的单个史莱姆。这样一直持续到该史莱姆到达板的末端,或者遇到与其值不同的史莱姆。

您已经玩过该游戏几次,但已经厌倦了。您现在想知道,完成游戏后,棋盘上所有史莱姆值的预期总和是多少。

输入

输入的第一行将包含两个整数 n, p (1 ≤ n ≤ 109, 1 ≤ p < 109)。

输出

游戏结束后打印板上所有史莱姆的预期总和。如果您的答案的绝对或相对误差不超过 10 - 4,则视为正确。

也就是说,假设您的答案是 a,陪审团的答案是 b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-4}$$,检查程序将认为您的答案正确。

示例

输入 #1

2 500000000

输出 #1

3.562500000000000

输入 #2

10 1

输出 #2

64.999983360007620

输入 #3

100 123456789

输出 #3

269.825611298854770

注意

在第一个样本中,我们有一个有两个方块的棋盘,出现 1 的概率为 0.5,出现 2 的概率为 0.5。

我们的最终棋盘状态可以是 1 2(概率为 0.25)、2 1(概率为 0.375)、3 2(概率为 0.1875)、3 1(概率为 0.1875)。因此,预期值为 (1 + 2)·0.25 + (2 + 1)·0.375 + (3 + 2)·0.1875 + (3 + 1)·0.1875 = 3.5625。