RedPaint | Topcoder Archive

Problem Statement

We have an infinite strip of paper divided into a sequence of cells. All of the cells are initially white. We place a robot onto one of the cells. Each time the robot stands on a cell, it paints the cell red.

You are given an int N. The robot will now make N steps. In each step, the robot will move either one cell to the left or one cell to the right, with equal probability. All random choices made by the robot are mutually independent.

Compute and return the expected number of red cells at the end.

Definition

Class:: RedPaint
Method:: expectedCells
Parameters:: int
Returns:: double
Method signature:: double expectedCells(int N)
(be sure your method is public)

Notes

Your return value must have an absolute or a relative error at most 10^(-9).

Constraints

N will be between 0 and 500, inclusive.

Examples

```
0
```
```
Returns: 1.0
```
No movement. At the end there is a single red cell: the one with the robot.
```
1
```
```
Returns: 2.0
```
One step. The robot will choose a random direction and move. There will be exactly two red cells: the one where it started and the one where it ended.
```
2
```
```
Returns: 2.5
```
In the third step the robot will color a third cell red with probability 1/2. Hence, the expected number of red cells is 0.5*2 + 0.5*3 = 2.5.
```
4
```
```
Returns: 3.375
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.