spoj
Състезание
Задача
G
Наименование
Trends

Условие

Задача G. Тенденция
---
Тенденция (Trend) на пазара е обективна промяна на финансовите пазари, която определя движение с течение на времето, в определена посока, на цената на финансов актив (валута, акция, стока и др.). Търговците идентифицират тенденциите на пазара, използвайки технически анализ, основан на оценки, които ги характеризират - т.н. предсказуеми ценови тенденции в рамките на пазара. Това са случаите, при които цената достига нива на "дъно" и "таван", които се променят във времето. Една тенденция може да се определи само върху исторически данни, тъй като цените им в бъдеще време не са известни.

Термините "Пазар на бика" и "Пазар на мечката" описват положителна и отрицателна тенденция на пазара. Тя може да се използва, за да опише пазара като цяло или отделни сектори от него най-общо. Имената им отговарят на факта, че бикът атакува с вдигане на рогата си нагоре, а мечката напада с ноктите си в низходяща посока.

Фирма за IT е направила анализи на "Пазар на бика" на валутните курсове на отношението EUR/USD за различни времеви интервали и ги е съхранила на твърд носител. Вследствие на хардуерен проблем във фирмата е настъпило смесване на историческите серии, което се състои в обединяване на всички съхранени данни в обща числова смесица. Вие сте софтуерен специалист във фирмата и трябва от получената съвкупност от числа да възстановите техните оригинални нарастващи пазарни тенденции. Създателите на данните ви помагат като възстановяват предполагаемия техен общ брой. Необходимо е да се създаде бърза програма, с помощта на която да може да се определи колко на брой са "Пазарите на бика" от дадените пазарни данни. "Биковете" не се бият помежду си на пазара, затова условието е всеки "Пазар на бика" да не пресича кой да е друг такъв.

Примерна ситуация е показана на фигурата. По вертикала са пазарните стойности, получени след смесването на данните. По хоризонтала са времевите точки на получената стойност. Двете са обозначени с цели числа от 1 до N. На фигурата е показана графиката, съответстваща на примерен вход 1. Всички нарастващи тенденции започват от нулевата начална точка, която не е включена в данните.

Вход
---
На първия ред има едно цяло число 1<=T<=20, определящо броя на тестовете. Всеки тест започва с ред, на който има цяло положително число 1<=N<=50000, определящо максималната стойност по двете координатни оси и число 1<=L<=50000 - броя на нарастващите тенденции, които би трябвало да има в текущия тест. Следва последователнoст от N цели числа, определящи стойностите на финансовия актив. Всяко i-то число от реда определя числовата стойност на i-та позиция по оста x. Данните на реда са разделени помежду си с интервал.

Изход
---
За всеки от тестовете да се изведе един ред с изчисления минимален брой нарастващи тенденции (помалък или равен на L). Ако броят им се изчисли на по-голям от L, да се изведе текст impossible.

Примерен вход 
---
2
6 3
4 2 6 3 1 5
8 3
8 7 6 5 4 3 2 1

Примерен изход
---
3
impossible

« Предходна страница Решение Въпрос