|
questo è il testo del problema!!
Il problema
Il dottore ordina a Poldo di seguire una dieta. Ad ogni pasto non può mai mangiare un panino che abbia un peso maggiore o uguale a quello appena mangiato. Quando Poldo passeggia per la via del suo paese da ogni ristorante esce un cameriere proponendo il menù del giorno. Ciascun menù è composto da una serie di panini, che verranno serviti in un ordine ben definito, e dal peso di ciascun panino. Poldo, per non violare la regola della sua dieta, una volta scelto un menù, può decidere di mangiare o rifiutare un panino; se lo rifiuta il cameriere gli servirà il successivo e quello rifiutato non gli sarà più servito.
Si deve scrivere un programma che permetta a Poldo, leggendo un menù, di capire qual è il numero massimo di panini che può mangiare per quel menù senza violare la regola della sua dieta.
Riassumendo, Poldo può mangiare un panino se e solo se soddisfa una delle due condizioni:
1) il panino è il primo che mangia in un determinato pasto;
2) il panino non ha un peso maggiore o uguale all’ultimo panino che ha mangiato in un determinato pasto.
Dati in input
La prima linea del file input.txt contiene il numero m di panini proposti nel menu. Le successive m linee contengono un numero intero non negativo che rappresenta il peso del panino che verrà servito. I panini verranno serviti nell’ordine in cui compaiono nell’input.
Dati in output
Il file output.txt contiene il massimo numero di panini che Poldo può mangiare rispettando la dieta.
Assunzioni
I pesi di panini sono espressi in grammi, un panino pesa al massimo 10 Kg.
Un menù contiene al massimo 100 panini.
Esempi di input e output
Esempio 1
File input.txt
8
389
207
155
300
299
170
158
65
File output.txt
6
Esempio 2
File input.txt
3
22
23
27
File output.txt
1
Esempio 3
File input.txt
22
15
14
15
389
201
405
204
130
12
50
13
26
190
305
25
409
3011
43
909
987
1002
900
File output.txt
6
| 
