Fişierul intrare/ieşire:mmsir.in, mmsir.outSursăAutumn Warmup 2007, Runda 2
AutorTiberiu SavinAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.45 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

MMsir

Se da un sir cu N elemente intregi. Definim gradul unui sir ca fiind numarul de schimbari de monotonie ale acestuia. Numarul de schimbari de monotonie ale unui sir cu N elemente reprezinta numarul de pozitii i (1 < i < N) cu propietatea ca a[i-1] < a[i] > a[i+1] sau a[i-1] > a[i] < a[i+1]. Se cere sa se gaseasca numarul de subsecvente ale sirului cu gradul K.

Date de intrare

Pe prima linie a fisierului mmsir.in se vor afla 2 numere reprezentand numerele N si K. Pe a doua linie se vor afla N numere reprezentand sirul.

Date de iesire

In fisierul mmsir.out se va afla un singur numar, rezultatul cerut in enunt.

Restrictii

  • 1 ≤ N ≤ 1 000 000
  • 0 ≤ K ≤ N
  • numerele din sir vor fi mai mici sau egale decat 230

Exemplu

mmsir.inmmsir.out
6 2
1 2 0 4 6 5
3

Explicatie

Cele trei subsecvente au capetele pe pozitiile 1 4, 1 5 si 2 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content