Connection Status:
Competition Arena > RedPaint

RedPaint

TCO14 Round 1C · 2014-03-26 · by misof

TCO14 Round 1C · 2014-03-26 · by misof · Dynamic Programming, Simple Search, Iteration, Simulation
Class Name: RedPaint
Return Type: double
Method Name: expectedCells
Arg Types: (int)
Problem Statement

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.

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)
0
Returns: 1.0

No movement. At the end there is a single red cell: the one with the robot.

1)
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)
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.

3)
4
Returns: 3.375
4)
3
Returns: 3.0

Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RedPaint with a public method double expectedCells(int N) · 80 test cases · 2 s / 256 MB per case

Submitting as anonymous