1994 ACM Student Programming Contest

Pacific Region

Problem A: Robot Random Walk

  
Imagine a robot which can only move in steps of +-1 along
the x axis. It starts at X=0 and then takes N steps, each
having equal probability of being +1 or -1.  One sequence of
N steps in this fashion is called a trial run.  During any
one trial run the robot will achieve some maximum X position
(maximum displacement to the right of the origin).  After
each trial run the robot is repositioned at X=0 and
restarted; it once again takes the same number of steps N,
each having equal probability of being +1 or -1.

After any one trial run the maximum X value achieved for
that particular trial run will be an integer in the range
(0<=MaxX<=N).  However, taking in to account the
probabilities associated with each step, the Expected Value
of MaxX after making many trial runs of a given length N is
a rational number which, typically, is not an integer.  For
example, if N=1 (i.e,. the robot takes only one step in each
trial run), then the possible final positions are X=-1 and
X=+1; the corresponding values of MaxX are 0 and 1
respectively, and the Expected Value of MaxX for trial runs
of length 1 is 0.5 (since the two possible outcomes for MaxX
of O and 1 are equally likely).

You are to write a program to compute and print Expected
Values for the Maximum X position of the robot, given N (the
number of steps in each run). The input to your program is a
file containing non-negative integers N, one value per line.
You may assume N is in the range (0<=N<=16).

For each input value N, your program should print a message
similar to the output shown below, containing the value of N
and the Expected Value of MaxX when the robot makes N-step
runs. The Expected MaxX values must be displayed rounded to
6 decimal place accuracy.

Sample Input:

0
1

Corresponding Output:

0 Random Step(s): Expected MaxX of 0.000000
1 Random Step(s): Expected MaxX of 0.500000