贪吃蛇

题目描述:

CD很喜欢玩贪吃蛇游戏，这个游戏就是很普通的贪吃蛇游戏。

你可以在一个地图中操纵一条蛇，每次可以让蛇头选择其相邻的格子移动，然后蛇身的每一格沿蛇身往前移动一格。游戏的目标就是让蛇吃尽量多的食物，蛇头碰到障碍或自身则游戏结束。

         无论任何时候地图上只有一个食物，食物一被吃掉就会在蛇身没有占据的地方等概率随机出现一个食物。

         而CD喜欢玩简单的贪吃蛇游戏，他喜欢在1*(N+1)的方格图中玩贪吃蛇，地图方格从左到右从0到N编号，这时蛇只能从左到右移动，蛇头一开始在最左端的0号格子。蛇头每移动一个，蛇的长度+1。即当蛇移动到i号格点，0~i号点均不会出现食物。

         现在游戏开始，请作为游戏达人的你在知道地图规模的情况下估计一下CD期望可以用贪吃蛇吃到多少食物。

输入格式:

第一行两个整数N,P。

输出格式:

仅一个实数表示答案，答案保留P位小数。

样例输入:

样例1:
2 6

样例2：
10 6

样例输出:

样例1:
1.500000

样例2：
2.928968

提示:

【数据范围】

其中50%的数据，N<=200,P=1

其中50%的数据，N<=25

以上有30%的数据同时拥有以上两种特点。

对于100%的数据，N<=10000000,P<=8

【样例解释】

         对于样例一，游戏开始时食物会随机出现在1号点或2号点。

         有1/2的概率出现在1号店，此时蛇移动到1号点，只有2号点可以出现食物，于是2号点必定出现食物。则蛇有1/2的概率吃到2个食物，另1/2的概率吃到1个食物。所以期望为1*(1/2)+2*(1/2)=1.5。

         期望等于所有情况出现的概率p乘其得分x的积的和。

时间限制: 1000ms
空间限制: 256MB

---