Statistics

Problem Statement for "RedPaint"

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

  1. 0

    Returns: 1.0

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

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

  3. 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. 4

    Returns: 3.375

  5. 3

    Returns: 3.0

  6. 5

    Returns: 3.75

  7. 6

    Returns: 4.0625

  8. 7

    Returns: 4.375

  9. 500

    Returns: 35.70031019890119

  10. 499

    Returns: 35.66464555334774

  11. 498

    Returns: 35.62890943555973

  12. 456

    Returns: 34.094970407115

  13. 301

    Returns: 27.708563680258436

  14. 77

    Returns: 14.04835350757413

  15. 379

    Returns: 31.086808347141655

  16. 397

    Returns: 31.815503120981134

  17. 273

    Returns: 26.390589133251336

  18. 485

    Returns: 35.16128913406542

  19. 141

    Returns: 18.982334962714216

  20. 223

    Returns: 23.85664479104023

  21. 226

    Returns: 24.016163483000092

  22. 40

    Returns: 10.15502569718592

  23. 366

    Returns: 30.54969259718733

  24. 14

    Returns: 6.07470703125

  25. 467

    Returns: 34.50332817573229

  26. 47

    Returns: 10.998384260494731

  27. 420

    Returns: 32.72298427933507

  28. 357

    Returns: 30.172291342538323

  29. 404

    Returns: 32.09439210784611

  30. 124

    Returns: 17.805451132912207

  31. 120

    Returns: 17.517079917337895

  32. 227

    Returns: 24.069179296428636

  33. 241

    Returns: 24.79871000975108

  34. 270

    Returns: 26.245407540490227

  35. 181

    Returns: 21.498551311248736

  36. 295

    Returns: 27.43147185483054

  37. 309

    Returns: 28.073765451928708

  38. 471

    Returns: 34.650621434312015

  39. 90

    Returns: 15.180673260956578

  40. 265

    Returns: 26.001757578134757

  41. 433

    Returns: 33.224981859468095

  42. 284

    Returns: 26.91602091922468

  43. 438

    Returns: 33.41601943423373

  44. 235

    Returns: 24.488715302989895

  45. 282

    Returns: 26.821245609113927

  46. 85

    Returns: 14.755598421818503

  47. 215

    Returns: 23.42579178681059

  48. 19

    Returns: 7.047882080078125

  49. 333

    Returns: 29.141923937618248

  50. 490

    Returns: 35.34186390722941

  51. 112

    Returns: 16.925603927123923

  52. 398

    Returns: 31.85547234600768

  53. 150

    Returns: 19.576592860189148

  54. 494

    Returns: 35.48567691399364

  55. 475

    Returns: 34.79729122306567

  56. 258

    Returns: 25.65664851978682

  57. 210

    Returns: 23.152372150516026

  58. 313

    Returns: 28.254596261239854

  59. 237

    Returns: 24.592481045798927

  60. 290

    Returns: 27.198365387812444

  61. 344

    Returns: 29.618594199445372

  62. 444

    Returns: 33.643858862567264

  63. 470

    Returns: 34.613837335124984

  64. 15

    Returns: 6.2841796875

  65. 8

    Returns: 4.6484375

  66. 497

    Returns: 35.59317331777052

  67. 496

    Returns: 35.557365296324576

  68. 489

    Returns: 35.30583754239021

  69. 22

    Returns: 7.568464279174805

  70. 100

    Returns: 15.997436714822918

  71. 431

    Returns: 33.148249799746885

  72. 473

    Returns: 34.724033767859204

  73. 493

    Returns: 35.449796553110524

  74. 43

    Returns: 10.525167727300868

  75. 200

    Returns: 22.59574008271144

  76. 487

    Returns: 35.23363746561626

  77. 50

    Returns: 11.339792438580922

  78. 400

    Returns: 31.935310872997473

  79. 20

    Returns: 7.224079132080078

  80. 478

    Returns: 34.90687008439841

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.
This problem was used for: