Fişierul intrare/ieşire:zigzag2.in, zigzag2.outSursăGrigore Moisil 2018, 10
AutorHasmasan Dragos, Tudor CozmaAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zigzag2

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.

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

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.

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.

Restricţii

  • 3 ≤ N ≤ 1 000 000
  • 0 ≤ K ≤ 1 000 000
  • Elementele vectorului sunt numere întregi cu semn care încap pe 32 de biţi.
  • 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".

Exemplu

zigzag2.inzigzag2.out
4 1
2 1 1 2
2
18 5
-2 1 7 -5 -8 9 10 3 2 9 4 6 -9 -7 -8 -1 -3 0
136

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:

  • 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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?