Problem Statement |
| | Your restaurant has numTables tables to seat customers. The tables are all arranged in a line. If a large party of customers comes in, a group of adjacent tables will be used. Which group of tables is entirely up to the customer. Since you cannot predict this, assume all possible choices occur with equal probability. What you can predict is the size of each group of customers that arrives. Element i of probs gives the probability, in percent, that an entering party will need i+1 tables.
Assuming nobody leaves, return the expected number of tables you will use before a party must be turned away. This only occurs if there is no place to seat them. |
| |
Definition |
| | | Class: | TableSeating | | Method: | getExpected | | Parameters: | int, int[] | | Returns: | double | | Method signature: | double getExpected(int numTables, int[] probs) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Return values must be accurate to 1e-9, relative or absolute. |
| |
Constraints |
| - | numTables will be between 1 and 12 inclusive. |
| - | probs will contain between 1 and 12 elements inclusive. |
| - | Each element of probs will be between 0 and 100 inclusive. |
| - | The elements of probs will sum to 100. |
| |
Examples |
| 0) | |
| | | Returns: 4.0 | | Since every party needs only 1 table, you will always fill the restaurant before turning someone away. |
|
|
| 1) | |
| | | Returns: 3.3333333333333335 | | Now every party wants 2 tables. One third of the time, the first party will choose the middle 2 tables blocking anyone else from being seated. Two thirds of the time, the first party will choose 2 tables on the end allowing the restaurant to become full. Thus, the returned value is (1/3)*2 + (2/3)*4 = 10/3. |
|
|
| 2) | |
| | | Returns: 0.0 | | You have 5 tables, but every party needs 6 or 7 tables. |
|
|
| 3) | |
| | 12 | {9,9,9,9,9,9,9,9,9,9,10} |
| Returns: 7.871087929710551 | |
|