Problem Statement
Each inspector n starts at the box numbered first[n] and then proceeds to box first[n]+period[n] and continues inspecting boxes until reaching the end of the boxes (boxes begin numbering at zero). If an inspector were to see a total of 30 berries in the 20 boxes looked at, and if there were 25 boxes altogether, that inspector would give an estimate of 30*25/20=37.5 berries for the entire shipment. If an inspector does not open any boxes, that inspector will estimate that there are zero berries in the shipment. More than one inspector may look at the same box. You will be paid based on the average estimate of the inspectors.
Since you know which boxes each inspector will look at, it is in your best interest to put more berries in those boxes and to choose a number of boxes that will make your shipment seem as large as possible. Assuming that you do so, what is the maximum number of berries you will be paid for?
Definition
- Class:
- BerryPacker
- Method:
- bestPacking
- Parameters:
- int[], int[], int
- Returns:
- double
- Method signature:
- double bestPacking(int[] first, int[] period, int berries)
- (be sure your method is public)
Constraints
- first and period will each contain between 1 and 5 elements, inclusive.
- first and period will contain the same number of elements.
- Each element of first will be between 0 and 100,000 inclusive.
- Each element of period will be between 1 and 100,000 inclusive.
- berries will be between 1 and 100,000 inclusive.
Examples
{2}
{500}
6
Returns: 12.0
There's only one inspector, and he's only going to see one box - box 2 (you don't have nearly enough berries to think about box 502). One way to maximize your payment is to use 4 boxes, put 3 berries in box 2 and 1 berry in each of the other 3 boxes. Inspector sees 3 berries in one box and assumes there are 12 in shipment.
{0,1}
{2,2}
7
Returns: 9.0
Between the two inspectors, each box is going to get looked at once (inspector 0 looks at even boxes, inspector 1 at odd boxes). Your best bet is to put 5 berries in box 1 and 1 berry in boxes 0 and 2. That way inspector 1 sees 5 berries and assumes there's 15. Inspector 0 sees 2 berries in 2 boxes, and estimates a shipment of 3. (15+3)/2=9
{500}
{1}
499
Returns: 0.0
Inspectors that don't see anything will assume there's no berries.
{0,1,2,3,4}
{2,2,2,2,2}
5
Returns: 5.0
We don't have any leeway to game system here.
{1,2,3,4,549}
{3,5,9,11,1}
550
Returns: 969.6
It's not worth trying to show anything to last inspector.
{1,2,3,4,5}
{1,1,1,1,1}
100000
Returns: 100023.99604073784
We can't game much here - all we can do is stiff the first few boxes a bit
{0,0,0,0,0}
{1,3,5,7,11}
100000
Returns: 197695.29425500863
{1}
{1}
1000
Returns: 1007.9999999999999
1000 = (111*9) + 1 9*112/111=1008
{2,5,9,25}
{1,3,11,7}
100
Returns: 251.50649350649354
{3892,4897,2872,8711,7191}
{1,298,47872,2992,19871}
100000
Returns: 720091.816755946
{0,0,0,0,0}
{1,1,1,1,1}
100000
Returns: 100000.0
{5,3,6782,2,80000}
{5001,5002,5003,5004,1}
100000
Returns: 739511.9999999999
{78,292,29922,4774,27171}
{928,2817,88,1,992}
500
Returns: 1742.4
{27,68,51,44,41}
{18,94,73,70,76}
92171
Returns: 488756.91014572454
{9293,18855,7046,9972,9138}
{25028,12090,13554,22805,25799}
91791
Returns: 824247.0
{39618,7642,30532,82562,15014}
{3,3,2,2,2}
91737
Returns: 235544.93287874284
{1200,901,4447,3051,2951}
{1,1,1,1,1}
90799
Returns: 108747.10794387218
{6,1,3,1,6}
{1001,1000,1003,1002,9003}
18001
Returns: 156897.0
{0,0,1,1,1000}
{1,2,1,2,500}
15000
Returns: 38596.8030321489
{0, 1, 2, 3, 4 }
{1, 2, 3, 5, 7 }
100000
Returns: 171703.9315824347
{1000 }
{1 }
100000
Returns: 108000.0
{1, 2, 3, 4, 5 }
{2, 3, 5, 7, 11 }
100000
Returns: 197899.17731785311
{1, 2, 3, 4, 5 }
{1, 2, 3, 4, 5 }
100000
Returns: 166288.75076498027
{1, 2, 3, 4, 55 }
{101, 72, 202, 1024, 303 }
100000
Returns: 712512.0
{0, 3, 3, 3, 3 }
{100, 100, 100, 100, 100 }
4
Returns: 4.0
{2, 5, 9, 25, 29 }
{1, 3, 11, 7, 13 }
100000
Returns: 217813.74814447263
{0, 0, 0, 0, 0 }
{1, 1, 1, 1, 1 }
100000
Returns: 100000.0
{0, 10, 20, 30, 40 }
{99999, 99989, 99799, 99999, 99999 }
100000
Returns: 899568.0
{1, 2, 3, 3, 4 }
{2, 3, 4, 5, 6 }
100000
Returns: 161719.2685123893