TopCoder Statistics - 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.

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

4

{100}

Returns: 4.0

Since every party needs only 1 table, you will always fill the restaurant before turning someone away.
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.
5

{0,0,0,0,0,50,50}

Returns: 0.0

You have 5 tables, but every party needs 6 or 7 tables.
12

{9,9,9,9,9,9,9,9,9,9,10}

Returns: 7.871087929710551
12

{50,50}

Returns: 10.481925778559631
12

{13,12,11,10,9,8,7,6,5,4,15}

Returns: 7.808255233597771
12

{9,13,12,11,10,9,8,7,6,5,10}

Returns: 7.845338058149987
1

{50, 50}

Returns: 0.5
12

{10,10,10,10,10,10,10,10,10,5,5}

Returns: 7.791471890555719
12

{0,0,0,0,0,0,0,100}

Returns: 8.0
12

{0,0,0,0,0,0,0,0,0,0,100}

Returns: 11.0
11

{0,0,0,0,0,0,0,0,0,0,100}

Returns: 11.0
12

{0,0,0,0,0,0,0,0,0,0,0,100}

Returns: 12.0
11

{0,0,0,0,0,0,0,0,0,0,0,100}

Returns: 0.0
11

{0,0,0,100,0,0,0,0}

Returns: 8.0
12

{5,11,9,8,14,9,13,8,7,5,7,4}

Returns: 7.936797412852827
12

{7,11,3,10,7,8,10,6,10,9,9,10}

Returns: 8.126028036598123
12

{7,8,10,6,11,3,11,8,12,4,9,11}

Returns: 8.118801968504272
12

{5,7,8,5,9,12,10,10,11,6,10,7}

Returns: 8.11048707258796
12

{10,8,6,6,13,9,7,9,7,6,8,11}

Returns: 8.049878648612912
12

{8,8,8,5,8,15,13,10,2,5,12,6}

Returns: 7.986177114965399
12

{5,10,6,6,7,10,9,4,8,7,12,16}

Returns: 8.348414551784307
12

{7,8,12,9,12,7,6,8,10,3,7,11}

Returns: 8.052738612235387
12

{9,6,16,9,11,9,3,7,8,9,8,5}

Returns: 7.943718551056782
12

{2,9,9,13,6,7,6,11,10,11,8,8}

Returns: 8.161556462174529
12

{6,13,6,11,4,7,14,8,5,8,9,9}

Returns: 8.047133841306092
12

{9,4,11,5,9,8,6,7,11,13,10,7}

Returns: 8.125227737892228
12

{10,8,10,4,4,9,6,12,12,6,7,12}

Returns: 8.097772321164507
12

{9,9,6,7,10,5,3,14,4,10,8,15}

Returns: 8.186352110757422
12

{10,8,5,8,11,7,5,9,8,8,8,13}

Returns: 8.12341030346038
12

{10,4,11,10,4,5,9,10,9,10,7,11}

Returns: 8.105897639599036
10

{7,8,7,7,11,7,13,9,8,7,9,7}

Returns: 5.548077404403071
11

{8,13,8,6,9,7,14,11,4,9,7,4}

Returns: 6.984070937897883
8

{8,7,13,10,5,5,7,8,9,15,4,9}

Returns: 3.170253495666273
12

{3,12,8,6,10,8,7,12,11,11,6,6}

Returns: 8.060610638818153
10

{9,10,9,6,8,11,9,9,8,7,8,6}

Returns: 5.613740874240573
12

{7,9,10,10,10,13,7,10,7,6,5,6}

Returns: 7.943149442547289
8

{6,10,6,10,5,10,8,13,5,5,11,11}

Returns: 3.66637571605075
7

{7,10,9,9,8,5,7,7,9,12,9,8}

Returns: 2.4022283271035416
11

{9,6,8,9,9,11,13,8,4,5,11,7}

Returns: 6.7768584160555685
5

{8,7,12,11,11,8,9,9,10,5,7,3}

Returns: 1.6879347114666667
10

{9,9,9,12,14,8,6,7,9,5,4,8}

Returns: 5.721093711587419
11

{8,8,6,7,10,7,10,14,5,14,9,2}

Returns: 7.358124714950001
7

{6,7,8,7,6,7,7,12,6,8,10,16}

Returns: 2.128593734551208
5

{3,6,12,14,5,7,6,9,7,11,7,13}

Returns: 1.3779074283
7

{8,5,3,10,10,9,10,8,12,10,8,7}

Returns: 2.5979698571289807
5

{13,6,9,12,13,9,7,7,5,4,8,7}

Returns: 1.8054801732999999
5

{8,10,6,9,7,13,6,10,7,5,8,11}

Returns: 1.2790011434666668
6

{10,14,7,5,8,8,4,11,16,4,7,6}

Returns: 1.9294564666666671
12

{9,8,9,9,6,3,13,7,8,8,7,13}

Returns: 8.108452413294861
11

{4,6,9,3,11,16,10,8,7,11,5,10}

Returns: 6.598011997184336
7

{10,5,8,10,7,8,4,10,6,6,11,15}

Returns: 2.2223947250000005
8

{11,14,9,10,7,6,12,3,9,10,4,5}

Returns: 3.5731237470027617
10

{9,5,9,8,10,4,4,12,8,10,9,12}

Returns: 5.202158770327831
6

{9,8,9,5,6,12,4,12,11,6,9,9}

Returns: 1.9160604429810002
12

{8,8,8,8,8,8,8,8,8,8,8,12}

Returns: 8.1265900083746
4

{100 }

Returns: 4.0
12

{9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10 }

Returns: 7.871087929710551
3

{50, 50, 0 }

Returns: 2.458333333333333
12

{7, 10, 11, 31, 0, 12, 13, 3, 5, 5, 2, 1 }

Returns: 7.953231954425785
12

{9, 7, 9, 11, 9, 9, 9, 9, 9, 9, 10 }

Returns: 7.884999908970048
11

{12, 38, 40, 1, 2, 3, 4 }

Returns: 8.294557818072061
4

{40, 10, 0, 30, 20 }

Returns: 2.2309333333333337
1

{14, 69, 1, 15, 1 }

Returns: 0.14
11

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 45 }

Returns: 4.487326183089735
12

{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 5 }

Returns: 7.9400870030448685
12

{8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 12 }

Returns: 8.1265900083746
12

{10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5 }

Returns: 7.867716233990063
12

{9, 9, 9, 9, 9, 9, 9, 9, 9, 11, 8 }

Returns: 7.859750293346915
10

{5, 10, 15, 5, 10, 15, 5, 10, 15, 10 }

Returns: 6.904985901014728
12

{5, 25, 50, 15, 5 }

Returns: 9.220460327135862

Statistics

Problem Statement for "TableSeating"

Problem Statement

Definition

Notes

Constraints

Examples