Baltic OI '07 P3 - Sound

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Baltic Olympiad in Informatics: 2007 Day 1, Problem 3

In digital recording, sound is described by a sequence of numbers representing the air pressure, measured at a rapid rate with a fixed time interval between successive measurements. Each value in the sequence is called a sample.

An important step in many voice-processing tasks is breaking the recorded sound into chunks of non-silence separated by silence. To avoid accidentally breaking the recording into too few or too many pieces, the silence is often defined as a sequence of m samples where the difference between the lowest and the highest value does not exceed a certain threshold c.

Write a program to detect silence in a given recording of n samples according to the given parameter values m and c.

Input Specification

The first line of the file contains three integers: n (1 \le n \le 1\,000\,000), the number of samples in the recording; m (1 \le m \le 10\,000), the required length of the silence; and c (0 \le c \le 10\,000), the maximal noise level allowed within silence.

The second line of the file contains n integers a_i (0 \le a_i \le 1\,000\,000 for 1 \le i \le n), separated by single spaces: the samples in the recording.

Output Specification

The output should list all values of i such that \max(a[i \dots i + m - 1]) - \min(a[i \dots i + m - 1]) \le c. The values should be listed in increasing order, each on a separate line.

If there is no silence in the input, write NONE on the first and only line of the output.

Sample Input

7 2 0
0 1 1 2 3 2 2

Sample Output



There are no comments at the moment.