TopCoder problem "CalculationCards" used in TCO10 Wildcard (Division I Level Two)



Problem Statement

    There are some cards in a box which are specified by a String[] cards. One of the operators '+', '-' or '*' is written on the left half of each card and a digit is written on the right half of each card. You draw all cards from the box randomly, one by one. At each step each of the remaining cards has the same probability of being drawn. Then you align the cards from left to right in the order you have drawn them. Finally, add a zero at the left of the cards and calculate the value of this expression. For example, if you have drawn "+1", "-2" and "*3" (in this order), the expression is "0 + 1 - 2 * 3", whose value is -5. Return the expected value.
 

Definition

    
Class:CalculationCards
Method:getExpected
Parameters:String[]
Returns:double
Method signature:double getExpected(String[] cards)
(be sure your method is public)
    
 

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-cards will contain between 1 and 50 elements, inclusive.
-Each element of cards will contain exactly 2 characters.
-The first character in each element of cards will be either '+', '-' or '*'.
-The second character in each element of cards will be a digit ('0' - '9').
 

Examples

0)
    
{ "+1", "-2", "*3" }
Returns: -1.6666666666666667
One of the following expressions will be made with equal probability:
  • 0 + 1 - 2 * 3 = -5
  • 0 + 1 * 3 - 2 = 1
  • 0 - 2 + 1 * 3 = 1
  • 0 - 2 * 3 + 1 = -5
  • 0 * 3 + 1 - 2 = -1
  • 0 * 3 - 2 + 1 = -1
1)
    
{ "+1", "+2", "+3" }
Returns: 6.0
The value will always be 6.
2)
    
{ "+3", "-7", "*4", "+6" }
Returns: 3.5
3)
    
{ "+1", "*2", "*3" }
Returns: 3.1666666666666665
4)
    
{ "*7", "-2", "*0", "+3", "*8" }
Returns: 5.633333333333334
5)
    
{ "+1", "*9", "*9", "*9", "*9", "*9", "*9", "*9", "*9", "*9", "*9" }
Returns: 3.5660295009090906E8

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11040

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14286&pm=11040

Writer:

lyrically

Testers:

SnapDragon , Rustyoldman , marek.cygan , timmac , ivan_metelsky , Egor

Problem categories:

Dynamic Programming, Math