CalculationCards
TCO10 Wildcard · 2010-04-11 · by lyrically
TCO10 Wildcard · 2010-04-11 · by lyrically · Dynamic Programming, Math
Problem Statement
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.
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
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CalculationCards with a public method double getExpected(vector<string> cards) · 57 test cases · 2 s / 256 MB per case