CF335E.Counting Skyscrapers

A number of skyscrapers have been built in a line. The number of skyscrapers was chosen uniformly at random between 2 and 314! (314 factorial, a very large number). The height of each skyscraper was chosen randomly and independently, with height i having probability 2 - i for all positive integers i. The floors of a skyscraper with height i are numbered 0 through i - 1.

To speed up transit times, a number of zip lines were installed between skyscrapers. Specifically, there is a zip line connecting the i-th floor of one skyscraper with the i-th floor of another skyscraper if and only if there are no skyscrapers between them that have an i-th floor.

Alice and Bob decide to count the number of skyscrapers.

Alice is thorough, and wants to know exactly how many skyscrapers there are. She begins at the leftmost skyscraper, with a counter at 1. She then moves to the right, one skyscraper at a time, adding 1 to her counter each time she moves. She continues until she reaches the rightmost skyscraper.

Bob is impatient, and wants to finish as fast as possible. He begins at the leftmost skyscraper, with a counter at 1. He moves from building to building using zip lines. At each stage Bob uses the highest available zip line to the right, but ignores floors with a height greater than h due to fear of heights. When Bob uses a zip line, he travels too fast to count how many skyscrapers he passed. Instead, he just adds 2_i_ to his counter, where i is the number of the floor he's currently on. He continues until he reaches the rightmost skyscraper.

Consider the following example. There are 6 buildings, with heights 1, 4, 3, 4, 1, 2 from left to right, and h = 2. Alice begins with her counter at 1 and then adds 1 five times for a result of 6. Bob begins with his counter at 1, then he adds 1, 4, 4, and 2, in order, for a result of 12. Note that Bob ignores the highest zip line because of his fear of heights (h = 2).

Bob's counter is at the top of the image, and Alice's counter at the bottom. All zip lines are shown. Bob's path is shown by the green dashed line and Alice's by the pink dashed line. The floors of the skyscrapers are numbered, and the zip lines Bob uses are marked with the amount he adds to his counter.

When Alice and Bob reach the right-most skyscraper, they compare counters. You will be given either the value of Alice's counter or the value of Bob's counter, and must compute the expected value of the other's counter.

若干摩天大楼排成一行。摩天大楼的数量在 $2$ 到 $314!$（即 $314$ 的阶乘，一个非常大的数）之间均匀随机选取。每座摩天大楼的高度独立地随机选取：对任意正整数 $i$，高度为 $i$ 的概率为 $2^{-i}$。一座高度为 $i$ 的摩天大楼的楼层编号为 $0$ 至 $i-1$。

为加快通行速度，大楼之间安装了若干条缆索（zip line）。具体而言：当且仅当两座摩天大楼之间不存在任何拥有第 $i$ 层楼的摩天大楼时，才存在一条连接它们各自第 $i$ 层楼的缆索。

爱丽丝（Alice）与鲍勃（Bob）决定统计摩天大楼的数量。

爱丽丝做事细致，希望精确得知摩天大楼的总数。她从最左侧的摩天大楼出发，计数器初始值为 $1$；然后逐栋向右移动，每移动一栋楼，计数器加 $1$；如此继续，直至抵达最右侧的摩天大楼。

鲍勃性子急躁，希望尽快完成任务。他同样从最左侧的摩天大楼出发，计数器初始值也为 $1$；但他借助缆索在楼栋之间移动。在每一步中，鲍勃总是选择当前可到达的、最高的向右延伸的缆索；但出于恐高，他会忽略所有楼层编号大于 $h$ 的缆索（即仅考虑楼层编号 $\le h$ 的缆索）。当鲍勃使用一条缆索时，他移动过快，无法清点途中经过的大楼数量；取而代之的是，他将其计数器增加 $2^i$，其中 $i$ 为其所处楼层的编号。他持续此过程，直至抵达最右侧的摩天大楼。

考虑如下示例：共有 $6$ 座大楼，从左至右高度依次为 $1, 4, 3, 4, 1, 2$，且 $h = 2$。爱丽丝从计数器值 $1$ 开始，随后五次各加 $1$，最终结果为 $6$。鲍勃从计数器值 $1$ 开始，接着依次加上 $1, 4, 4, 2$，最终结果为 $12$。注意：由于恐高（$h = 2$），鲍勃忽略了最高的那条缆索。

图中顶部显示鲍勃的计数器，底部显示爱丽丝的计数器。所有缆索均已标出。鲍勃的路径以绿色虚线表示，爱丽丝的路径以粉色虚线表示。各摩天大楼的楼层已编号，鲍勃所使用的缆索旁标注了其对应计入计数器的数值。

当爱丽丝与鲍勃均抵达最右侧摩天大楼后，他们将比较各自的计数器读数。本题将给出爱丽丝或鲍勃其中一人的计数器值，要求你计算另一人计数器值的期望值。

The first line of input will be a name, either string "Alice" or "Bob". The second line of input contains two integers n and h (2 ≤ n ≤ 30000, 0 ≤ h ≤ 30). If the name is "Alice", then n represents the value of Alice's counter when she reaches the rightmost skyscraper, otherwise n represents the value of Bob's counter when he reaches the rightmost skyscraper; h represents the highest floor number Bob is willing to use.

输入的第一行是一个名字，为字符串 "Alice" 或 "Bob"。第二行输入包含两个整数 $n$ 和 $h$（$2 \le n \le 30000$，$0 \le h \le 30$）。如果名字是 "Alice"，则 $n$ 表示 Alice 到达最右侧摩天大楼时其计数器的值；否则（即名字为 "Bob"），$n$ 表示 Bob 到达最右侧摩天大楼时其计数器的值；$h$ 表示 Bob 愿意使用的最高楼层编号。

Output a single real value giving the expected value of the Alice's counter if you were given Bob's counter, or Bob's counter if you were given Alice's counter.

You answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

输出一个实数值，表示在已知 Bob 的计数器值时 Alice 计数器的期望值，或在已知 Alice 的计数器值时 Bob 计数器的期望值。

若你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

In the first example, Bob's counter has a 62.5% chance of being 3, a 25% chance of being 4, and a 12.5% chance of being 5.

在第一个例子中，Bob 的计数器有 62.5% 的概率为 3，25% 的概率为 4，12.5% 的概率为 5。