题目描述

你变成了地狱里的亡灵。哈迪斯让所有亡灵在刻耳柏洛斯面前从左往右排成一排，而你正好排在第999个，当三头犬咬了它面前的亡灵的时候，该亡灵就能顺利回到他生活的土地上。 三头犬的三个头分别会咬面前的左，中，右三个位置的亡灵，每次只会伸出一个头，每个头咬亡灵的概率是相等的。当亡灵被咬后则会消失，其左侧的亡灵将永远留在地狱，其右侧的亡灵将依序补位。（即被咬到的人得救，而他左侧的人将进入地狱） 突然，时间静止了，赫尔墨斯说他可以马上将你排入队伍里，但是现在哈迪斯很生气，为了防止吸引到哈迪斯的注意，你不能直接排到三头犬的面前，只能在第4~999位之间挑选。现在需要你计算出第n个位置的存活概率是多少？

输入格式

输入一个整数n表示在队伍中的位置（4≤n≤999）

输出格式

输出一个double类型的数字表示第n位的存活概率（保留小数点后10位）

4
100

0.4567901235
0.5000000000

提示

典型的动态规划题，要用到状态转移方程。

第1个位置的存活率为0.3333333333333333


第2个位置的存活率为0.4444444444444444


第3个位置的存活率为0.5925925925925926