Zigzag2

zigzag2

== include(page="template/taskheader" task_id="zigzag2") ==

Se dă un vector $a$ cu $N$ numere întregi şi un număr natural $K$.

Se dă un vector a cu N numere întregi şi un număr natural K.

O subsecvenţă $a[i], a[i+1], ..., a[j]$ se numeşte zig-zag dacă $a[i] > a[i+1] < a[i+2] > …$ sau $a[i] < a[i+1] > a[i+2] < …$ . O secvenţă aproape-zig-zag de ordin $K$ este o secvenţă care conţine cel mult $K$ greşeli. O greşeală se defineşte ca fiind un triplet format din elemente cu indici consecutivi ale secvenţei care nu este zig-zag.

O subsecvenţă a[i], a[i+1], ..., a[j] se numeşte zig-zag dacă a[i] > a[i+1] < a[i+2] > … sau a[i] < a[i+1] > a[i+2] < … . O secvenţă aproape-zig-zag de ordin K  este o secvenţă care conţine cel mult K greşeli. O greşeală se defineşte ca fiind un triplet format din elemente cu indici consecutivi ale secvenţei care nu este zig-zag.

Să se găsească toate subsecvenţele aproape zig-zag de ordin $K$ de lungime mai mare sau egală cu $3$.

Să se găsească toate subsecvenţele aproape zig-zag de ordin K de lungime mai mare sau egală cu 3.

h2. Date de intrare

Fişierul de intrare $zigzag2.in$ conţine pe prima linie două numere întregi $N$ şi $K$ cu semnificaţia din enunţ. Următoarea linie conţine $N$ numere întregi care reprezintă elementele vectorului $a$.

Fişierul de intrare zigzag.in conţine pe prima linie două numere întregi N şi K cu semnificaţia din enunţ. Următoarea linie conţine N numere întregi care reprezintă elementele vectorului a.

h2. Date de ieşire

Fişierul de ieşire $zigzag2.out$ trebuie să conţină un număr întreg reprezentând numărul de subsecvenţe aproape zig-zag de ordin $K$ de lungime mai mare sau egală cu $3$.

Fişierul de ieşire zigzag.out trebuie să conţină un număr întreg reprezentând numărul de subsecvenţe aproape zig-zag de ordin K de lungime mai mare sau egală cu 3.
 

h2. Restricţii

* Pentru unele teste în valoare de $10$ puncte, se garantează că $2 ≤ N ≤ 300$.
* Pentru alte teste în valoare de $10$ puncte, se garantează că $2 ≤ N ≤ 2 000$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.

* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".

* Se vor acorda $10$ puncte din oficiu (ultimele 2 teste sunt exemplele).

h2. Exemplu

h3. Explicaţie

În primul exemplu vectorul are $4$ elemente. Se cere numărul subsecvenţelor aproape zig-zag de ordin $1$ ale vectorului dat. Avem $3$ subsecvenţe de lungime mai mare sau egală cu $3$:

În primul exemplu vectorul are 4 elemente. Se cere numărul subsecvenţelor aproape zig-zag de ordin 1 ale vectorului dat. Avem 3 subsecvenţe de lungime mai mare sau egală cu 3:

* $+2 1 1+ 2$ : subsecvenţa subliniată are o singură greşeală, deoarece tripletul $(2,1,1)$ nu este zig-zag
* $2 +1 1 2+$ : subsecvenţa subliniată are o singură greşeală, deoarece tripletul $(1,1,2)$ nu este zig-zag
* $+2 1 1 2+$ : subsecvenţa subliniată are doua greşeli, deoarece tripletele $(2,1,1)$ şi $(1,1,2)$ nu sunt zig-zag

* +2 1 1+ 2 : subsecvenţa subliniată are o singură greşeală, deoarece tripletul (2,1,1) nu este zig-zag
* 2 +1 1 2+ : subsecvenţa subliniată are o singură greşeală, deoarece tripletul (1,1,2) nu este zig-zag
* +2 1 1 2+ : subsecvenţa subliniată are doua greşeli, deoarece tripletele (2,1,1) şi (1,1,2) nu sunt zig-zag

== include(page="template/taskfooter" task_id="zigzag2") ==