- Описание
- Отправленные решения
245. Детекция сигнала
Инженер Игорь обрабатывает показания прибора. Его задача — найти момент первого выброса в сигнале.
Известно, что первые $K$ точек в данных «калибровочные», то есть в них выброса точно нет. Поэтому Игорь придумал алгоритм: пропустить первые $K$ точек, а затем взять первую точку, в которой сигнал строго больше, чем не менее 90% предыдущих точек.
Напишите алгоритм такого поиска.
Формат ввода
В первой строке записано число количества точек $N$ ($1 \le N \le 10^5$).
Во второй строке записано число количества калибровочных точек $K$ ($1 \le K \le N$).
Далее следует $N$ строк целых чисел от $-10^6$ до $10^6$ со значениями сигналов.
Формат вывода
Необходимо вывести целое число больше или равное $K$ — индекс первой точки, в которой сигнал строго больше, чем 90% предыдущих точек.
Если такой точки нет, необходимо вывести $-1$.
Ограничения
Ограничение времени
5 с
Ограничение памяти
256 МБ
Пример 1
12
5
1
5
2
3
4
1
3
2
7
2
3
48Пример 2
11
10
2
2
2
2
1
1
3
1
1
1
310
Пример 3
11
10
2
2
2
3
1
1
3
1
1
1
3-1