多座摩天大楼排成一排。摩天大楼的数量是在2到314之间统一随机选择的! (314 的阶乘,一个非常大的数字)。每座摩天大楼的高度都是随机且独立选择的,对于所有正整数 i,高度 i 的概率为 2 - i。高度为 i 的摩天大楼的楼层编号为 0 到 i - 1。
为了加快运输时间,摩天大楼之间安装了许多高空滑索。具体来说,当且仅当一座摩天大楼的第 i 层与另一座摩天大楼的第 i 层之间不存在具有第 i 层的摩天大楼时,存在一条连接该摩天大楼的第 i 层的滑索。
Alice 和 Bob 决定计算摩天大楼的数量。
Alice 很彻底,想知道到底有多少座摩天大楼。她从最左边的摩天大楼开始,计数器为 1。然后她向右移动,一次一座摩天大楼,每次移动时计数器都会加 1。她继续前进,直到到达最右边的摩天大楼。
Bob 不耐烦,想要尽快完成。他从最左边的摩天大楼开始,柜台位于 1。他使用滑索从一栋楼移动到另一栋楼。在每个阶段,鲍勃都会使用右侧最高的可用滑索,但由于恐高而忽略高度大于 h 的楼层。当鲍勃使用滑索时,他的速度太快,以至于无法数清他经过了多少座摩天大楼。相反,他只是将 2i 添加到他的计数器中,其中 i 是他当前所在的楼层的编号。他继续前进,直到到达最右边的摩天大楼。
考虑以下示例。有 6 栋建筑物,从左到右高度为 1、4、3、4、1、2,h = 2。Alice 从 1 开始计数,然后将 1 加五次,结果为 6。Bob 从 1 开始计数,然后按顺序添加 1、4、4 和 2,结果为 12。请注意,Bob 由于恐高而忽略了最高的滑索(h = 2)。
Bob 的计数器位于图像的顶部,Alice 的计数器位于底部。显示所有高空滑索。鲍勃的路径由绿色虚线显示,爱丽丝的路径由粉红色虚线显示。摩天大楼的楼层都有编号,鲍勃使用的滑索也标有他在柜台上添加的数量。
当爱丽丝和鲍勃到达最右边的摩天大楼时,他们比较计数器。您将获得 Alice 计数器的值或 Bob 计数器的值,并且必须计算对方计数器的期望值。
输入
输入的第一行是一个名字,可以是字符串“Alice”或“Bob”。输入的第二行包含两个整数 n 和 h (2 ≤ n ≤ 30000, 0 ≤ h ≤ 30)。如果名字是“Alice”,那么n代表Alice到达最右边摩天大楼时计数器的值,否则n代表Bob到达最右边摩天大楼时计数器的值; h 代表 Bob 愿意使用的最高楼层号。
输出
输出一个实数值,如果给你的是鲍勃的计数器,则给出爱丽丝计数器的预期值;如果给你的是爱丽丝的计数器,则输出鲍勃的计数器的预期值。
如果您的答案的绝对或相对误差不超过 10 - 9,则视为正确。
示例
输入 #1
Alice 3 1
输出 #1
3.500000000
输入 #2
Bob 2 30
输出 #2
2
输入 #3
Alice 2572 10
输出 #3
3439.031415943
注意
在第一个示例中,Bob 的计数器有 62.5% 的机会为 3,有 25% 的机会为 4,有 12.5% 的机会为 5。