Popcorn

SRM 118 · 2002-10-29 · by dgoodman

Class Name: Popcorn

Return Type: int

Method Name: quietTime

Arg Types: (vector<int>)

Problem Statement

"Place popcorn bag into microwave and start at full power. After at least 3 kernels have popped, listen until more than T seconds have passed without popping. Remove bag from microwave oven."

We plan to put these instructions on our popcorn bag, with the T replaced by a number. We want to choose T so that at least 75% of the kernels will have popped if the user follows the instructions. A popcorn sample has been tested and we have recorded the time that it took for each kernel to pop. Create a class Popcorn that contains the method quietTime that takes the popTimes of the kernels in the sample as input and returns the smallest T that will yield at least 75%.

Notes

popTimes are already sorted into non-descending order.
If exactly T seconds pass between pops, the user will continue popping.

Constraints

popTimes contains between 3 and 50 elements, inclusive.
Each element in popTimes is between 1 and 10,000, inclusive.
popTimes is in non-descending order.

Examples

{3,4,9,12,13,14,14,18,19,25,27}
Returns: 4

The intervals after the 3rd kernel has popped are 3,1,1,0,4,1,6,2. If T were 3, the user would stop at time 17, popping 7 of the 11 kernels which is less than 75%. So make T be 4. The user will stop at time 23, popping 9 of the 11 kernels.

{2,5,19}
Returns: 0

The user will stop at time 19, yielding 3 of 3.

{2,5,19,29,30}
Returns: 10

{2,5,19,29,30,42}
Returns: 10

{1000,5000,5000,5001}
Returns: 0

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

Coding Area

Language: C++17 · define a public class Popcorn with a public method int quietTime(vector<int> popTimes) · 35 test cases · 2 s / 256 MB per case