Connection Status:
Competition Arena > TableSeating

TableSeating

SRM 249 · 2005-06-29 · by AdminBrett

SRM 249 · 2005-06-29 · by AdminBrett · Dynamic Programming, Math, Recursion
Class Name: TableSeating
Return Type: double
Method Name: getExpected
Arg Types: (int, vector<int>)
Problem Statement

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.

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)
4
{100}
Returns: 4.0

Since every party needs only 1 table, you will always fill the restaurant before turning someone away.

1)
4
{0,100}
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)
5
{0,0,0,0,0,50,50}
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
4)
12
{50,50}
Returns: 10.481925778559631

Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TableSeating with a public method double getExpected(int numTables, vector<int> probs) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous