PROBLEM STATEMENT
To better estimate contest expenses, TopCoder has called upon you to determine
the average award for a contest, given a room assignment. Each room has one or
more awards to be assigned and at least as many coders assigned to it. In line
with existing contests, awards are only given to coders that have a positive
score. Thus, under some circumstances, not all awards will be distributed.
Given the awards for each room, and the (independent) probabilities a coder has
a positive score, determine the expected cost of a contest.
Each award and probability is expressed as an integer, with units dollars and
percent respectively. Each input string corresponds to one room, and is of the
form: "Award_1 Award_2 ... Award_m: Prob_1 Prob_2 ... Prob_n". For example,
"150 25 75: 90 80 70 60 50 40 30 20" would represent a room with $150 for first
place, $25 for second place, and $75 for third place, with eight coders with
different chances (from 90% to 20%) of having a positive score. Notice that
award amounts are not necessarily in decreasing order. In this example, if
only 2 coders have a positive score, they would receive $175 total (150 + 25),
not $225.
Return the expected award (sum for all rooms) for the contest in dollars,
truncating any decimal part.
DEFINITION
Class name: Expense
Method name: calculate
Parameters: String[]
Returns: int
Here is the method signature (be sure your method is public): int
calculate(String[] rooms)
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
* There are at most 50 rooms (0 to 50 input strings, inclusive)
* Each element of the String[] has no more than 50 characters
* Each subelement of each element of the String[] is separated by one space,
except that one colon and one space separates the last award from the first
probability
* All rooms will have at least one award
* All rooms will have at least as many coders as awards
* All awards will be integers in the range 0 to 1000, inclusive
* All probabilities will be in the range 0 to 100, inclusive
* Awards and probabilities will not have a leading zero or a decimal point
* Finally, to prevent rounding errors, any inputs that would produce an
unrounded result less than one millionth (0.000001) from an integer are
prohibited, unless equal to that integer exactly. For example, "4 0 0 0 7: 100
1 1 1 1" -> 4.00000007, so that input is prohibited. However, "20: 30" -> 6,
so that input is allowed.
EXAMPLES
["100 50: 100 0",
"100 50: 50 50"]
In room 1, $100 will always be awarded. In room 2, $150 will be awarded 25% of
the time, $100 will be awarded 50% of the time, and $0 will be awarded 25% of
the time. $100 + ($150 * 0.25) + ($100 * 0.50) = $100 + $37.5 + $50 = $187.5,
so calculate should return 187.
["150 75 25: 20 50 80"]
Chance everyone scores = 0.2*0.5*0.8 = 0.08 * $250 = $20
Chance two people score = 0.2*0.5*(1-0.8) + 0.2*(1-0.5)*0.8 + (1-0.2)*0.5*0.8 =
0.02 + 0.08 + 0.32 = 0.42 * $225 = $94.5 Chance one person scores =
0.2*(1-0.5)*(1-0.8) + (1-0.2)*0.5*(1-0.8) + (1-0.2)*(1-0.5)*0.8 = 0.02 + 0.08 +
0.32 = 0.42 * $150 = $63 Chance noone scores = (1-0.2)*(1-0.5)*(1-0.8) = 0.08 *
$0 = $0
$20 + $94.5 + $63 = $177.5, so calculate should return 177. Note that the
probabilities for all cases sum to one (0.08 + 0.42 + 0.42 + 0.08), as we
should expect.
["300 150 75: 60 88 0 77 19 100"], calculate should return 514.
["300 150 75: 60 88 0 77 19 100",
"150 75 25: 30 30 40 40 50 50 60 60"], calculate should return 753.
["300 150 75: 60 88 0 77 19 100",
"150 75 25: 30 30 40 40 50 50 60 60",
"75 40 15: 0 10 0 50 30 22 33 44"], calculate should return 851.