Una sequenza viene detta una sequenza a zig-zag se i valori delle differenze tra numeri successivi si alterna tra valori positivi e valori negativi. La prima differenza può essere negativa 0 positiva, se è negativa quella dopo deve essere positiva, se è positiva quella dopo deve essere negativa e così via. Una sequenza con meno di due elementi è anche una sequenza a zigzag. Ti viene data una sequenza di numeri, tu puoi decidere di eliminare quanti numeri vuoi dalla sequenza in modo che i numeri rimanenti formino una sequenza a zigzag. Trovare la sequenza a zigzag più lunga che è possibile ottenere e stampare la sua lunghezza.
Input
Il programma deve leggere dal file : la prima riga contiene un intero N. La seconda riga contiene N valori positivi, i valori della sequenza di partenza.
Output
Il programma deve scrivere nel file la risposta al problema.
Assunzioni
1 ≤ N ≤ 800
Esempio
input output
10 7
1 17 5 10 13 15 10 5 16 8
Basta sfogliare la sringa ed eliminare tutti gli “errori” che si incontrano:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <cstdlib> #include <iostream> #include<fstream> using namespace std; ifstream in; ofstream out; int n; int iz(int *c, int n){ bool positive; int nc=n; positive= (c[0]-c[1] < 0); for (int i=0;i<n-1;i++){ int d=c[i]-c[i+1]; if (d==0||(d<0 && !positive)||(d>0 && positive)) nc--; else positive= (d > 0); } return nc; } int main() { in.open("input.txt"); out.open("output.txt"); in>>n; int c [n]; for (int i=0;i<n;i++) in>>c[i]; if (n<2) out<<1; else out << iz(c,n); return 0; } |
