Statistics

Problem Statement for "MuddyRoad"

Problem Statement

Fox Ciel is going to walk through an unpaved road to meet her friend. The road is one-dimensional. It is separated into N parts numbered from 0 to N-1, where part 0 is Ciel's current part and part N-1 is her destination part.

Ciel will perform her trip tomorrow. Unfortunately today it is raining, so tomorrow some parts of the road will be muddy. You are given a int[] road containing N elements. The probability that the i-th part of the road will be muddy tomorrow is road[i]/100.

Ciel can walk along the road using any combination of strides with lengths 1 and 2. If she is at part i, a stride of length 1 will move her to part i+1 and a stride of length 2 will move her to part i+2 (skipping part i+1). If there are many ways to reach part N-1 from part 0, Ciel will choose the one among them where the number of visited muddy parts is minimal.

Return the expected number of muddy parts that she will visit tomorrow.

Definition

Class:
MuddyRoad
Method:
getExpectedValue
Parameters:
int[]
Returns:
double
Method signature:
double getExpectedValue(int[] road)
(be sure your method is public)

Notes

  • Assume that events "i-th part of the road will be muddy tomorrow" are totally independent.
  • Ciel has very good sight, so when starting her trip at part 0, she is already able to see for each part whether it is muddy or not.

Constraints

  • road will contain between 2 and 50 elements, inclusive.
  • Each element of road will be between 0 and 100, inclusive.
  • The first element and the last element of road will be 0.

Examples

  1. {0, 60, 60, 0}

    Returns: 0.36

    There can be four different states of the road tomorrow: .... with probability = 0.16, 0 steps to muddy parts .M.. with probability = 0.24, 0 steps to muddy parts ..M. with probability = 0.24, 0 steps to muddy parts .MM. with probability = 0.36, 1 step to muddy parts (Here, '.' represents a non-muddy part and 'M' represents a muddy part.) Thus, the expected number of steps is 0*0.16+0*0.24+0*0.24+1*0.36=0.36.

  2. {0, 50, 50, 50, 50, 0}

    Returns: 0.5625

  3. {0, 0, 100, 100, 100, 100, 100, 100, 0, 0, 100, 0}

    Returns: 3.0

  4. {0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0}

    Returns: 1.7352539420031923

  5. {0, 50, 50, 100, 50, 100, 50, 50, 100, 66, 0}

    Returns: 2.288125

  6. {0,0}

    Returns: 0.0

  7. {0,52,0}

    Returns: 0.0

  8. {0,79,0}

    Returns: 0.0

  9. {0,48,38,0}

    Returns: 0.1824

  10. {0,80,40,0}

    Returns: 0.32000000000000006

  11. {0,39,69,25,0}

    Returns: 0.374325

  12. {0,75,67,43,0}

    Returns: 0.5745250000000001

  13. {0,45,48,24,71,0}

    Returns: 0.40477440000000003

  14. {0,32,27,73,27,0}

    Returns: 0.38134044

  15. {0,43,41,71,25,26,0}

    Returns: 0.5078805049999999

  16. {0,40,70,66,66,45,0}

    Returns: 0.9931563999999999

  17. {0,21,13,95,39,59,38,54,39,0}

    Returns: 0.9687372665520181

  18. {0,84,100,100,98,87,99,81,87,0}

    Returns: 3.4183372287519997

  19. {0,4,17,1,1,8,20,9,19,0}

    Returns: 0.05567549087564801

  20. {0,52,7,47,79,76,31,59,0}

    Returns: 0.97655599081472

  21. {0,70,95,56,46,52,83,93,0}

    Returns: 1.945987367008

  22. {0,6,11,11,19,11,24,24,0}

    Returns: 0.12977947469215997

  23. {0,24,18,86,54,12,63,0}

    Returns: 0.6434954484480001

  24. {0,89,48,42,60,53,72,0}

    Returns: 1.1232881510400001

  25. {0,0,23,34,10,10,8,0}

    Returns: 0.11917143999999999

  26. {0,15,24,47,64,5,80,94,48,34,71,23,14,16,1,76,32,59,28,44,85,17,79,49,21,94,10,39,60,0}

    Returns: 3.540283173723101

  27. {0,76,86,96,68,82,88,71,70,85,100,89,81,77,95,97,86,80,92,90,92,86,95,75,89,100,70,95,93,0}

    Returns: 10.93297940465888

  28. {0,24,21,38,43,29,45,24,8,7,31,49,46,5,28,33,0,45,49,16,30,18,35,19,40,4,44,41,0,0}

    Returns: 1.6690995472693175

  29. {0,92,29,31,88,37,79,97,59,84,83,28,41,91,91,15,0,38,24,18,57,57,82,71,11,81,19,59,0}

    Returns: 4.96996544401987

  30. {0,97,60,90,87,95,69,59,60,93,67,63,86,90,65,84,62,58,95,75,90,63,65,57,85,61,94,76,0}

    Returns: 8.524017185811585

  31. {0,17,15,10,38,5,33,23,26,34,28,17,22,11,16,15,9,1,25,8,34,13,1,28,36,20,28,12,0}

    Returns: 0.8059083234974578

  32. {0,93,52,29,73,7,75,53,94,72,99,2,61,5,37,53,21,50,77,71,85,98,6,59,36,35,75,0}

    Returns: 4.40044218365283

  33. {0,80,93,75,98,92,91,74,74,81,73,74,81,100,100,96,83,91,76,91,74,100,99,83,88,78,100,0}

    Returns: 10.234299293787886

  34. {0,21,9,21,11,19,14,1,2,5,11,5,1,6,8,17,13,8,15,8,15,5,9,4,12,14,10,0}

    Returns: 0.23648500990010496

  35. {0,77,76,39,14,20,27,60,42,63,70,83,12,52,74,35,81,20,0,85,60,89,42,24,3,19,27,11,89,79,58,89,11,78,66,63,40,39,0,59,35,100,31,2,5,49,9,99,94,0}

    Returns: 7.637288831373241

  36. {0,78,75,99,75,55,72,43,50,54,76,47,62,65,73,99,94,93,76,70,75,98,60,82,100,72,81,100,82,72,64,47,56,56,92,99,67,90,45,64,46,73,62,71,95,91,64,74,92,0}

    Returns: 14.84140932880513

  37. {0,29,38,21,29,4,38,36,24,19,13,3,35,21,4,32,4,8,10,30,38,19,25,33,10,0,13,12,14,37,18,7,25,38,22,35,13,36,16,1,17,1,12,13,2,29,26,25,33,0}

    Returns: 1.6194768265626827

  38. {0,69,66,39,74,78,1,23,87,9,19,82,21,65,67,46,24,46,51,70,58,58,20,15,70,55,97,82,3,59,17,3,96,38,32,18,25,9,84,49,48,59,67,98,97,85,74,15,0}

    Returns: 8.016533722471278

  39. {0,97,98,94,96,87,90,87,97,80,83,78,86,93,86,80,90,99,81,83,78,86,82,86,85,80,80,97,80,78,93,84,88,79,96,95,96,92,81,83,99,87,83,88,92,79,100,79,0}

    Returns: 19.067508253278863

  40. {0,0,7,20,20,20,13,12,9,13,19,18,14,9,20,3,15,20,2,10,20,8,19,20,1,11,15,6,8,6,3,14,8,0,2,20,9,19,12,1,11,12,13,1,1,19,0,9,0}

    Returns: 0.5053686081460953

  41. {0,45,58,12,57,43,86,9,40,88,81,77,52,56,59,32,52,48,77,30,66,37,33,82,53,99,85,85,36,30,59,9,23,80,4,49,43,39,25,45,13,91,59,41,46,17,51,0}

    Returns: 7.3402264604498155

  42. {0,57,80,52,49,95,81,62,67,57,89,89,100,90,72,69,79,88,53,72,53,99,44,95,67,85,51,49,65,95,68,82,90,46,86,47,51,64,45,61,51,68,65,75,51,93,70,0}

    Returns: 13.059106362085638

  43. {0,19,17,15,0,27,5,30,24,31,1,33,0,21,1,9,5,26,26,6,35,37,8,28,28,5,16,23,16,13,23,27,20,4,30,20,20,18,5,9,28,25,30,28,37,36,16,0}

    Returns: 1.3558346573734885

  44. {0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,0}

    Returns: 0.0

  45. {0,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,0}

    Returns: 0.6884620550511376

  46. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 0.0

  47. {0,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,0}

    Returns: 23.0

  48. {0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0}

    Returns: 0.0

  49. {0,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,0}

    Returns: 0.689361220773663

  50. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 0.0

  51. {0,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,0}

    Returns: 23.0

  52. {0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,100,0,0}

    Returns: 0.0

  53. {0,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,97,3,0}

    Returns: 0.7184342458019871

  54. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 0.0

  55. {0,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,0}

    Returns: 24.0

  56. {0, 13, 43, 50, 100, 47, 99, 3, 50, 25, 93, 1, 68, 44, 0, 66, 33, 33, 100, 100, 2, 4, 9, 25, 0, 0, 32, 100, 100, 100, 85, 15, 99, 23, 46, 0 }

    Returns: 5.149999338709421

  57. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }

    Returns: 0.11725653165494321

  58. {0, 85, 1, 69, 50, 66, 35, 57, 3, 41, 87, 81, 44, 30, 11, 52, 50, 84, 40, 33, 56, 74, 85, 68, 22, 19, 92, 70, 66, 84, 89, 20, 37, 9, 19, 35, 82, 41, 67, 88, 14, 62, 28, 35, 68, 1, 88, 42, 69, 0 }

    Returns: 7.719977717522379

  59. {0, 50, 0, 50, 0, 50, 0, 50, 50, 50, 50, 0, 0, 0, 50, 0, 0, 50, 0, 50, 0, 50, 0, 50, 0, 50, 0, 50, 0, 50, 50, 50, 50, 0, 0, 0, 50, 0, 0, 50, 0, 50, 0, 50, 50, 0, 50, 0, 50, 0 }

    Returns: 1.375

  60. {0, 18, 84, 42, 90, 21, 26, 96, 61, 10, 27, 68, 61, 54, 49, 96, 96, 78, 0, 60, 44, 50, 96, 54, 86, 38, 78, 16, 56, 88, 88, 9, 47, 88, 18, 4, 3, 7, 17, 4, 34, 20, 88, 33, 75, 0, 52, 13, 82, 0 }

    Returns: 7.233998055454088

  61. {0, 0 }

    Returns: 0.0

  62. {0, 1, 21, 33, 4, 17, 41, 48, 46, 10, 47, 92, 31, 61, 16, 30, 87, 55, 71, 91, 56, 98, 24, 49, 5, 56, 53, 73, 31, 77, 56, 99, 94, 84, 95, 10, 92, 24, 73, 18, 8, 97, 32, 11, 9, 88, 63, 13, 32, 0 }

    Returns: 7.646293946971668

  63. {0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0 }

    Returns: 1.7352539420031923

  64. {0, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 0 }

    Returns: 0.05236196296155354

  65. {0, 12, 34, 56, 78, 91, 23, 45, 67, 89, 0, 100, 100, 12, 31, 0, 23, 1, 1, 1, 1, 1, 1, 1, 1, 12, 100, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }

    Returns: 2.906230042385507

  66. {0, 51, 25, 12, 16, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 99, 100, 0, 4, 5, 6, 7, 5, 4, 1, 2, 33, 3, 55, 99, 85, 5, 1, 2, 3, 5, 1, 2, 3, 4, 1, 0 }

    Returns: 2.2891459457642203

  67. {0, 74, 52, 13, 82, 52, 23, 43, 11, 97, 48, 77, 77, 23, 48, 34, 41, 1, 25, 38, 18, 11, 35, 18, 95, 61, 55, 51, 30, 57, 56, 16, 85, 70, 44, 52, 18, 38, 5, 11, 21, 62, 65, 6, 63, 40, 23, 74, 33, 0 }

    Returns: 6.318442250044223

  68. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 0 }

    Returns: 2.597575017932373

  69. {0, 50, 50, 100, 50, 100, 50, 50, 100, 66, 0 }

    Returns: 2.288125

  70. {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 0 }

    Returns: 2.9080493946880632

  71. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 0.0

  72. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 0.0

  73. {0, 23, 48, 45, 56, 7, 78, 89, 90, 100, 12, 23, 30, 45, 56, 67, 78, 89, 90, 11, 12, 23, 34, 45, 56, 97, 78, 0, 90, 21, 92, 23, 42, 45, 56, 67, 8, 89, 0, 100, 12, 23, 34, 45, 5, 67, 78, 89, 90, 0 }

    Returns: 7.986602233777721

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: