| Fişierul intrare/ieşire: | zigzag2.in, zigzag2.out | Sursă | Grigore Moisil 2018, 10 |
| Autor | Hasmasan Dragos, Tudor Cozma | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | zigzag2.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
