A9107 | 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.

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.

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}$ .