Problem L
Noise Reduction
Monique is a climatologist who is analyzing the effects of
climate change on weather patterns in Antarctica. She has
compiled a set of
Unfortunately, there is a lot of noise in the data because the other scientists keep having snowball fights near Monique’s equipment, and penguins waddle past and peck at the sensor. Monique has since moved the system to a better location, but she would like to recover as much climate data as possible from her original readings.
She has hired you to write a program that will reduce the noise level in her data while she builds an even better thermal energy measurement system.
The noise level of the dataset varies depending on the
group size you choose. Given a group
size
-
Partition consecutive readings into groups of size
. Discard any readings at the end of the dataset that would not form a group of size . -
Compute the average temperature for each of the groups. Round down to the nearest integer less than or equal to the average (the floor of the average).
-
Calculate the noise level by determining the maximum difference between the averages of two adjacent groups. If there is only a single group, the noise level is
.
Your task is to determine the smallest
group size that causes the noise level of Monique’s dataset to
be less than or equal to the threshold
Input
The first line contains two space-separated integers,
The next
Output
Output a single integer, the smallest group size that
ensures that the noise level of Monique’s dataset is less than
or equal to the threshold
Sample Explanation
In Sample Input
In Sample Input
Sample Input 1 | Sample Output 1 |
---|---|
7 1 1 3 4 2 8 1 4 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
7 1 1 3 4 2 1 1 4 |
3 |