Connection Status:
Competition Arena > ClapLight

ClapLight

SRM 196 · 2004-05-27 · by dgoodman

SRM 196 · 2004-05-27 · by dgoodman · Brute Force
Class Name: ClapLight
Return Type: int
Method Name: threshold
Arg Types: (vector<int>)
Problem Statement

Problem Statement

I have a light that changes from on to off or from off to on when I clap twice. The light's sensor samples the noise level in the room at short intervals and it triggers the light to change whenever it detects a low noise level followed by exactly 2 high noise levels followed by a low noise level.

"High" or "low" is based on a threshold noise level. When the sampled noise level is as high or higher than the threshold level, the noise level is classified as "high"; otherwise it is classified as "low". I have a int[] background that is a typical sequence of sensor readings when normal activity is taking place. I want software that will choose the threshold value so that it has the following properties:

  1. 1) It causes more than 50% of all the values in background to be classified "low".
  2. 2) It is the lowest possible threshold value that satisfies the 50% rule and that does not cause background to trigger the light to change.

Create a class ClapLight that contains a method threshold that is given the int[] background and that returns the desired threshold value.

Constraints

  • background will contain between 4 and 50 elements inclusive.
  • Each element of background will be between 0 and 1000 inclusive.
Examples
0)
{6,6,6,6,6}
Returns: 7

The threshold must be at least 7 to exceed more than 50% of the samples, and with the threshold set at 7 every reading will be classified "low" and the light will not be triggered.

1)
{ 5,8,7,6,12,8,4,3,2,6 }
Returns: 9

The threshold must exceed at least 6 of these values to satisfy the 50% rule. So it must be at least 7. But with the threshold set at 7 the sequence 5, 8, 7, 6 would trigger the light. A threshold of 8 will allow the sequence 6,12,8,4 to trigger the light. A threshold of 9 will never cause this sequence to trigger the light.

2)
{8,8,8,1,1,1,1,1,1,1,1,1,1,1,2,1}
Returns: 2

Remember that the high noise levels must be both preceded and followed by low noise levels to trigger the light.

3)
{921,1,5,900,8,813,3,3,3,3,3,3,3,813,813}
Returns: 4
4)
{921,1,5,900,8,813,3,3,3,3,3,3,3,813,813,4}
Returns: 814

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

Coding Area

Language: C++17 · define a public class ClapLight with a public method int threshold(vector<int> background) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous